проблема лабиринта и рекурсивный алгоритм обратного отслеживания

Question

Я хочу реализовать алгоритм рекурсивного обратного отслеживания для решения проблемы лабиринта, но я не могу понять, 2.3 Команда («удалить стену между текущей ячейкой и выбранной ячейкой») мне поможет?

1. Пометить текущую ячейку как «Посещенную»
2. Если в текущей ячейке есть соседи, которые не были посещены
   1. Выбрать случайным образом одного из непосещенных соседей
   2. добавить текущую ячейкув стек
   3. удалить стенку между текущей ячейкой и выбранной ячейкой
   4. Сделать выбранную ячейку текущей ячейкой
   5. Рекурсивно вызвать эту функцию
3. else
   1. удаление последней текущей ячейки из стека
   2. Возврат к предыдущему выполнению этой функции

РедактироватьНа самом деле я хочу алгоритм для решения проблемы лабиринта с использованием стека.

Answer 1

Этот алгоритм представляет собой лабиринт генератор , а не лабиринт решатель . Идея в том, что вы хотите создать случайный лабиринт. Вы также хотите, чтобы все точки в лабиринте были доступны из всех других точек.

Если вы просто случайно удалите стены, вероятно, ваш лабиринт не будет подключен. Об этом заботится рекурсивный алгоритм обратного отслеживания, создавая случайную прогулку и удаляя стены вдоль этой случайной прогулки. Часть рекурсивного возврата позволяет вам пройти к каждой ячейке в лабиринте, даже когда вы зашли в тупик.

Answer 2

Ваш алгоритм для режима god. Обычно вы должны сделать

1. Если текущая ячейка является выходом, то завершено
2. Если в текущей ячейке есть соседи, которые не были посещены , которые не являются стенами
   
   1. Выберите случайным образом одного из непосещенных не пристенных соседей
   2. добавить текущую ячейку в стек
   3. ничего
   4. Сделать выбранную ячейку текущей ячейкой
   5. рекурсивно вызывать эту функцию
3. еще
   
   1. удалить последнюю текущую ячейку из стека
   2. Возврат к предыдущему выполнению этой функции

Answer 3

Удаление стены просто означает удаление стены! Вы начинаете с сетки ячеек, каждая из которых полностью окружена 4 стенами. Когда вы перемещаетесь случайным образом (2.1), вы удаляете стену, соединяющую ячейки.