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

Итак, у меня есть школьный проект: мне дан лабиринт, и я должен его решить. Я думал об использовании алгоритма 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)
      }  
    }

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


search graph algorithm depth-first-search maze
person Henry    schedule 03.05.2016    source источник

Ответы (3)


arrow_upward
3
arrow_downward

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

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

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

person Sorin    schedule 03.05.2016
comment
Я не хочу публиковать новый ответ, потому что ваш имхо правильный. @Henry, кроме того, посмотрите это видео: youtube.com/watch?v=iaBEKo5sM7w и перескочить на 3:00, посмотрите на этот стек с правой стороны, это именно тот путь, по которому он прошел, чтобы добраться до узла F ... Просто для визуализации - person VRage; 03.05.2016
comment
Спасибо за Ваш ответ! Я действительно позволял алгоритму работать после того, как он окрашивал конечный узел - person Henry; 03.05.2016

arrow_upward
1
arrow_downward

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

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

person Matteo Di Napoli    schedule 03.05.2016

arrow_upward
0
arrow_downward

Проблема с такими "как мне сделать 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
      }  
    }
person Matsmath    schedule 03.05.2016