решить лабиринт с помощью DFS, BFS, A *

Question

Хочу узнать изменение результатов, когда мы используем открытый или закрытый лабиринт для алгоритмов поиска DFS, BFS и A *?Есть ли какая-то большая разница в выходных данных, таких как увеличение числа расширенных узлов, стоимости и т. Д.?

Answer 1

Наивный DFS может зацикливаться на некоторых открытых лабиринтах, тогда как на закрытом лабиринте он всегда будет заканчиваться.Я не думаю, что BFS или A * могут попасть в эту ловушку.(Под «наивной DFS» я подразумеваю тот, который не помечает узлы как «посещенные», поскольку они их пересекают.) Редактировать: комментарий Даниэля заставил меня переосмыслить этот ответ в свете дня, а не сонных моментов, прежде чем я пошел впостель.Я признаю, что A * помечает узлы как посещенные как часть его основного функционирования.Тем не менее, я все еще думаю, что BFS может решать даже открытые лабиринты без маркировки узлов.Это не будет эффективным, но если есть решение для лабиринта, BFS найдет его.По определению, он пробует все возможные пути на определенной глубине, прежде чем перейти на следующую глубину.Таким образом, если решение существует с длиной 10, BFS найдет его, прежде чем пробовать какие-либо решения с глубиной 11.

Answer 2

Да. Существует большая разница, так как разные стратегии пересекают лабиринт в совершенно разных порядках

Answer 3

A * может быть довольно эффективным по сравнению с наивными дфс и бфс.Но вам нужно найти хорошую функцию для оценки стоимости от вашей текущей позиции до цели.