基於棧的迷宮算法背後的邏輯

我對C++編程相當陌生，而且我正在研究迷宮求解算法。我需要使用一個顯式堆棧來跟蹤完成的移動，而不是遞歸。基於棧的迷宮算法背後的邏輯

基本上我對「解算器」算法負責，我可以檢查移動是否可用或被阻止，或者我可以撤消移動。這些舉動是左，右和前進。已經有代碼負責繪製和更新迷宮。

我可以使用的只是幫助理解穿越迷宮的基本算法。我已經看過很多不同的程序，但我似乎無法弄清楚。我正在解決的迷宮是隨機生成的，沒有循環。

以下是我無法將自己的想法包括在內：比如說我有一段直的牆，但是牆上也有一個分支。假設我決定走下另一條支路，但最終導致死路一條。我把所有的動作都推到了堆棧上。基本上，我怎麼知道我需要從堆棧中彈出多少動作才能知道我回到原始路口，因此我可以使用另一個分支而不是被阻止的分支？

感謝您的幫助！

來源

2013-04-20 user2302335

「我需要一個堆棧...所以沒有遞歸」 - 這是沒有意義的。謹慎解釋？ – 2013-04-20 14:47:15

[迷宮問題和遞歸回溯算法]（http：// stackoverflow。com/questions/4402846/maze-problem-and-recursive-backtracker-algorithm） – 2013-04-20 14:47:53

@ Moo-Juice這不是一個好的重複。這是一個迷宮解決的問題，但具體問題是完全不同的。 – 2013-04-20 14:50:48

這是我無法控制的想法：說我決定走下另一條支路，但最終導致死路一條。我把所有的動作都推到了堆棧上。基本上，我怎麼知道我需要從堆棧中彈出多少動作才能知道我回到原始路口，因此我可以使用另一個分支而不是被阻止的分支？

您只需按照預定義的順序進行選擇即可。

這些動作是左，右和前進。

如果你總是按照這個順序做出這些選擇，你就會知道你在回溯時已經做了什麼。

你的每一步回溯，再次檢查這些舉動。如果你撤消權的選擇，你就會知道，你已經嘗試離開和右，但還沒有嘗試過向前。

來源

2013-04-20 14:49:33

這是一個很好的解決方案，佔用最少的內存。但我覺得使用堆棧是問題的一部分。 – Agentlien 2013-04-20 15:19:06

@Agentlien：這裏有一個堆棧。要撤消選擇，你必須記住它。你做出了很多選擇來達到你的要求。 – 2013-04-20 15:30:03

@MathieuM。讓我澄清一下：雖然這確實解釋了需要完成的邏輯，並且應該使用堆棧來實現，但我覺得它會跳過堆棧如何以及爲什麼會出現在圖片中。我覺得這是OP想要澄清的一個組成部分。 – Agentlien 2013-04-20 18:11:57

首先，從起始位置添加所有可能的移動。然後，只需遵循以下算法：

在每次迭代中，嘗試從堆棧彈出單個幀。如果堆棧爲空，則嘗試了所有可能的移動。

現在，看看你從棧中彈出的位置。這是你現在的位置。

添加從彈出的位置導致未探索位置到堆疊的所有移動。如果他們中的任何一個是目標位置，那麼你就完成了。

其餘的將自己照顧自己。給它一些想法，在紙上試幾個例子，你會看到。:)

來源

2013-04-20 14:53:59 Agentlien

基本上，我怎麼知道我需要從堆棧彈出多少動作才能知道我回到了原始路口，所以我可以用另一個分支而不是被阻止的分支？

你不 - 你總是回到一個一步。然後檢查所有（剩餘的）替代品，然後再往後一步......等等。這叫做backtracking。

順便說一句，無論您是否使用遞歸，這都是相同的。使用遞歸只是使堆棧隱含，並且堆棧自動處理。

來源

2013-04-20 14:54:35

你沒有太多的解決方案：基本上，探索無環迷宮是像做了深度優先搜索在覆蓋樹，每個路口是一個節點。

您可以隨時構建樹，並使用該信息來瀏覽它，但這會很單調乏味效率不高。

深度優先搜索的常用方法是推動堆棧中的所有節點進行檢查，拉動一個並再次推動，直到達到目標。但是你會得到很多節點堆積起來，一旦找到目標節點，就不能使用堆棧來知道你遵循的是哪條路徑，這意味着你需要在其他地方存儲這些信息。

這可能是更好的保持棧解決方案和標籤節點在你的籌碼來表示一個分支，和方向（即其子樹）的分支已經探索（或路徑剩下）。如果您在相同的順序做的探索始終，該標籤可以簡單地將一個數字：

0左
1前
2右
3原路返回

或更好的是枚舉。

當找到死角時，只需展開堆棧直到找到其中一個節點，然後嘗試新的方向。如果所有方向都已經嘗試過，換句話說，如果沒有方向，請再次放鬆。

enum Branch { 
    LEFT, 
    FORWARD, 
    RIGHT, 
    BACKTRACK 
}; 

struct BacktrackException{ 
}; 

template <typename MazeMove> 
struct StackNode { 
    MazeMove move; 
    Branch branch; 
    StackNode(MazeMove m): move(m), branch(LEFT) {} 
    MazeMove nextBranch(){ 
     switch(branch){ 
      case LEFT: 
       if (move.can_left()){ 
        branch = FORWARD; 
        return move.left(); 
       } 
      case FORWARD: 
       if (move.can_forward()){ 
        branch = RIGHT; 
        return move.forward(); 
       } 
      case RIGHT: 
       if (move.can_right()){ 
        branch = BACKTRACK; 
        return move.right(); 
       } 
      default: 
       throw BacktrackException(); 
     } 
    } 
};

上面的代碼提供與棧使用的可能的「MazeMove」類，它保持跟蹤所嘗試的方向的一個包裝。 nextBranch方法返回下一個可能的移動，或者引發異常。

好處是你的堆棧不會被未經測試的移動破壞。每當你到達一個新的位置時，你推動一個StackNode，當它的選項全部被測試出來時，將其展開。當你到達迷宮出口時，你的堆棧只包含需要的移動。

來源

2013-04-20 14:55:27 didierc

基於棧的迷宮算法背後的邏輯

回答

相關問題