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