Программирование теории: Решите лабиринт

Лабиринт можно представить как дерево.

     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* , который является отраслевым стандартным алгоритмом поиска пути, сочетающим алгоритм поиска в ширину. поиск с эвристикой... что-то вроде "интеллектуального поиска в ширину".

В основном это работает следующим образом:

1. Поместите один путь в очередь (путь, по которому вы проходите только один шаг прямо в лабиринте). Путь имеет «вес», определяемый его текущей длиной + его расстояние по прямой от конца (которое может быть рассчитано математически).
2. Вытолкните путь с наименьшим весом из очереди.
3. "Взорвать" путь на каждый путь, которым он может быть после одного шага. (т.е. если ваш путь Правый Левый Левый Правый, то ваши взорванные пути будут Р Л Л Р Р и Р Л Л Р Л, не считая нелегальных, проходящих сквозь стены)
4. Если один из этих путей имеет цель, то Победа! В противном случае:
5. Вычислите веса разнесенных путей и поместите их все обратно в очередь (не включая исходный путь).
6. Отсортируйте очередь по весу, начиная с самого низкого. Затем повторите с шага № 2

И это A*, который я специально выделил, потому что это более или менее стандартный алгоритм поиска пути для всех приложений поиска пути, включая перемещение от одного края карты к другому, избегая бездорожья или гор и т. д. Он работает так хорошо, потому что использует эвристику кратчайшего возможного расстояния, которая придает ему «интеллект».A* настолько универсален, потому что, учитывая любую проблему, если у вас есть доступная эвристика кратчайшего возможного расстояния (у нас простая — прямая линия), вы можете применить ее.

НО важно отметить, что A* не ваш единственный вариант.

На самом деле, в категории алгоритмов обхода дерева Википедии перечислено только 97! (лучшее по-прежнему будет на этой странице, ссылка на которую была указана ранее)

Извините за длину =P (я склонен к бессвязности)