Решение лабиринта с использованием алгоритма поиска глубины

Question

Итак, у меня есть этот школьный проект: Я получаю в качестве входа лабиринт, и я должен его решить. Я думал об использовании алгоритма DFS для этого.

То, что я сделал до сих пор, превращает мой лабиринт в граф, в котором вершины являются нестационарными положениями лабиринта.

Я нашел псевдокод для DFS онлайн. Я реализовал его, но я не понимаю, как я должен выйти из него. Псевдокод алгоритма:

dfs(graph G,vertex a) 
    { 
     ColorNode(a); 
     for all vertices e adjacent to a 
     { 
     if e is endpoint 
     END 
     if e is not colored 
     dfs(G, e) 
     } 
    } 

С помощью этого алгоритма, все узлы в конечном итоге цветные .. Если кто-то может дать мне руку здесь, это было бы очень приятно!

Answer 1

Если все узлы в конечном итоге окрашены, это, должно быть, было ошибкой в ​​построении графика или в дизайне лабиринта, так как с помощью этого кода рано или поздно вы должны найти выход.

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

Answer 2

Путь состоит из узлов в трассе стека. Вы можете изменить dfs, чтобы вернуть bool, если он нашел конец, и когда он вернет true, вы будете печатать или добавлять в вершину списка a (обратите внимание, что это дает путь назад).

В качестве альтернативы может быть стек (глобальный или передать ссылку на него в вашей функции). Когда вы вызываете dfs, нажимайте vertex a на него и выталкивайте его, когда вы вернетесь. Затем, когда вы добираетесь до конечной точки, стек содержит путь.

Все доступные узлы должны окрашиваться, если END не остановит всю программу. Я подозреваю, что вы написали его так, что продолжаете идти после того, как нашли место назначения, чтобы ваша программа продолжала окрашивать узлы. Нет никакого прекрасного способа закончить рекурсию (вы можете выбросить исключение, но это просто плохой стиль), поэтому вы должны позволить вызывающим абонентам знать, что решение найдено и прекратить попытки других вещей (вы можете вернуть bool, если решение найдено , поэтому, когда вызов возвращает true, вы можете немедленно вернуть true).

Answer 3

Проблема с такими типами «как мне сделать DFS?» вопросы в том, что очень мало понимания того, что на самом деле происходит.

Как только вы спросите себя Как мне поехать в лабиринт, чтобы найти его выход? это (ну ... должно быть) более или менее просто, что делать:

Вы бы завязывать нить в исходное местоположение, а затем начинают интересоваться, вокруг, следуя этим простым правилам:

1. Всякий раз, когда вы приходите на перекресток, вы проверяете, есть ли еще какое-то место, где вы не были до, а если есть, то вы просто продолжаете двигаться в этом направлении.

2. Если вы приедете к перекрестку, от которого она уже не является возможным прогрессировать дальше, вы отмечаете, что место как посетил, пересекая две ветви на полу лабиринта. В следующий раз вы пропустите этот переход, и вы с вернетесь туда, откуда вы пришли от.

С точки зрения вашего фрагмента кода:

dfs(graph G,vertex a)//What should I do at this junction? 
    { 
     ColorNode(a);//Stretch your thread to that junction 
     for all vertices e adjacent to a//Choose a direction you haven't visited yet 
     { 
     if e is endpoint//If I found the exit of the maze 
     END//I survived 
     if e is not colored//If I haven't been in this direction earlier 
     dfs(G, e)//Let's move on to that direction 
     } 
    }