Вы можете думать о своем лабиринте как о дереве.
A
/ \
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
/ \
L M
/ \
** O
(which could possibly represent)
START
+ +---+---+
| A C G |
+---+ + + +
| D B | F | J |
+---+---+ +---+---+
| L H E I |
+---+ +---+---+
| M O |
+ +---+
FINISH
(ignoring left-right ordering on the tree)
Где каждый узел является соединением путей. D, I, J, L и O - тупики, а ** - цель.
Конечно, в вашем реальном дереве каждый узел может иметь до трех дочерних элементов.
Ваша цель теперь просто найти, к каким узлам пройти, чтобы найти финиш. Подойдет любой алгоритм поиска по дереву.
Глядя на дерево, довольно легко увидеть ваше правильное решение, просто "проследив" от ** в самой глубокой части дерева:
A B E H M **
Обратите внимание, что этот подход становится лишь немного более сложным, когда у вас есть "петли" в вашем лабиринте (т. Е. Когда это возможно, без возврата назад, вы повторно входите в проход, через который вы уже прошли ). Проверьте комментарии для одного хорошего решения.
Теперь давайте посмотрим на ваше первое упомянутое решение, примененное к этому дереву.
Ваше первое решение - это, по сути, Поиск в глубину , что на самом деле не так уж и плохо. На самом деле это довольно хороший рекурсивный поиск. По сути, он гласит: «Всегда сначала выбирай самый правый подход. Если там ничего нет, возвращайся назад до первого места, куда ты можешь идти прямо или налево, а затем повтори».
Поиск в глубину будет искать вышеупомянутое дерево в следующем порядке:
A B D (backtrack) E H L (backtrack) M ** (backtrack) O (backtrack thrice) I
(backtrack thrice) C F (backtrack) G J
Обратите внимание, что вы можете остановиться, как только найдете **.
Однако, когда вы на самом деле кодируете поиск в глубину, использование рекурсивного программирования делает все намного проще. Даже итерационные методы тоже работают, и вам никогда не придется явно программировать, как откатываться назад. Проверьте связанную статью для реализаций.
Другим способом поиска дерева является решение Breadth-First , которое ищет по деревьям по глубине. Он будет искать через указанное дерево в следующем порядке:
A (next level) B C (next level) D E F G (next level)
H I J (next level) L M (next level) ** O
Обратите внимание, что из-за характера лабиринта ширина в ширину имеет гораздо большее среднее количество узлов, которые он проверяет. В ширину легко реализовать, имея очередь путей для поиска, и каждая итерация выталкивает путь из очереди, «взрывая» его, получая все пути, в которые он может превратиться после одного шага, и помещая эти новые пути в конце очереди. В коде нет явных команд «следующего уровня», и они просто были там, чтобы помочь в понимании.
Фактически, существует целый обширный список способов поиска дерева . Я только что упомянул два самых простых, самых простых способа.
Если ваш лабиринт очень, очень длинный и глубокий, имеет петли и сумасшествия, и является сложным, я предлагаю алгоритм A *, который является стандартным алгоритмом поиска пути который объединяет поиск по ширине с эвристикой ... вроде как «интеллектуальный поиск по ширине».
В основном это работает так:
- Поместите один путь в очередь (путь, по которому вы идете только один шаг прямо в лабиринт). У пути есть «вес», определяемый его текущей длиной + прямолинейным расстоянием от конца (которое может быть вычислено математически)
- Выведите путь с наименьшим весом из очереди.
- «Взрывайте» путь на каждом пути, каким он может быть после одного шага. (т. е. если ваш путь - справа налево, слева направо, то ваши разнесенные пути - это R L L R R и R L L R L, не считая нелегальных, проходящих через стены)
- Если у одного из этих путей есть цель, тогда Победа! В противном случае:
- Рассчитайте вес взорванных путей и поместите все их обратно в очередь (не включая исходный путь)
- Сортировка очереди по весу, сначала самая низкая. Затем повторите с шага № 2
И это A *, который я представляю специально выделенным, потому что это более или менее стандартный отраслевой алгоритм поиска путей для всех приложений поиска путей, включая перемещение от одного края карты другому, избегая бездорожья или гор, и т. д. Он работает так хорошо, потому что использует эвристический алгоритм кратчайшего расстояния , который придает ему «интеллект». A * настолько универсален, потому что, учитывая любую проблему, если у вас есть эвристика минимально возможного расстояния (у нас это просто - прямая линия), вы можете применить ее.
НО очень важно отметить, что A * является не вашим единственным вариантом.
Фактически, категория алгоритмов обхода дерева содержит только 97! (лучшее все еще будет на этой странице ссылка ранее)
Извините за длину = P (я склонен бродить)