открытый лабиринт - поиск в глубину

У меня есть открытый лабиринт с начальной и конечной точками. Я написал алгоритм поиска BFS и DFS для решения лабиринта. Мой BFS находит кратчайшее решение, но мой DFS (который идет вниз, влево, вверх, вправо) создает зигзаг в качестве решения. Это правильно? Как должен вести себя DFS в открытом лабиринте?

редактировать: http://postimg.org/image/n049oua8n/ вот путь, начиная с формы P , Конечная точка находится внизу, но середина пути мне кажется неправильной =/ Я думаю, что алгоритм пропускает столбец, верно? он должен полностью заполнять среднюю часть?


c depth-first-search maze
person Krzysiek    schedule 26.09.2013    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Да, это правильно, потому что DFS глубоко исследует граф (и не находит кратчайших путей). Учитывая источник посещения s, DFS посещает одного из своих соседей u, затем одного из соседей u, углубляясь в глубину. Когда посещаются все соседи данного узла, посещается другой сосед родительского узла и так далее.

DFS

В то время как BFS, учитывая источник посещения, s сначала посещает всех своих соседей, а затем начинает углубляться.

BFS

person pNre    schedule 26.09.2013

arrow_upward
1
arrow_downward

Звучит правильно: DFS будет идти настолько глубоко в лабиринте, насколько это возможно, в первом направлении (вниз), а когда он не сможет продвинуться дальше, он вернется к последнему перекрестку и пойдет налево, а затем снова вниз.

Существует алгоритм рисования под названием "flood fill", который заполняет пространство цветом, создавая DFS. или BFS пикселей. Анимации его работы дают хорошее графическое представление различий между двумя алгоритмами поиска по графу.

Это пищевая начинка с BFS, как вы можете видеть, она ищет пространство во всех направлениях:

Заливка с помощью BFS

Это заливка с помощью DFS, как вы можете видеть, она ищет пространство сначала в одном направлении, а затем возвращается, чтобы заполнить дыры:

введите здесь описание изображения

person Joni    schedule 26.09.2013