基于栈的迷宫算法背后的逻辑

我对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

基于栈的迷宫算法背后的逻辑

回答

相关问题