3

我对 C++ 编程相当陌生，我正在研究迷宫求解算法。我需要使用显式堆栈来跟踪完成的移动，而不是递归。

基本上我负责“求解器”算法，我可以检查移动是否可用或被阻止并执行它，或者我可以撤消移动。移动是左，右和向前。已经有代码负责绘制和更新迷宫。

我可以使用的只是一些帮助理解穿越迷宫的基本算法。我已经看过很多不同的程序来做这件事，但我似乎无法弄清楚。我正在解决的迷宫是随机生成的，没有循环。

这是我无法理解的：假设我有一段直的墙，但也有一根树枝从墙上伸出来。假设我决定沿着另一个分支走下去，但最终它会导致死胡同。我已经把我做过的所有动作都推到了堆栈上。基本上，我怎么知道我需要从堆栈中弹出多少步才能知道我回到了原来的交叉点，所以我可以选择另一个分支而不是被阻塞的分支？

谢谢你的帮助！

4

4 回答 4

5

以下是我无法解决的问题：假设我决定沿着另一个分支走下去，但最终它会导致死胡同。我已经把我做过的所有动作都推到了堆栈上。基本上，我怎么知道我需要从堆栈中弹出多少步才能知道我回到了原来的交叉点，所以我可以选择另一个分支而不是被阻塞的分支？

您需要做的就是始终按照预定义的顺序进行选择。

移动是左，右和向前。

如果你总是按照这个顺序做出这些选择，那么当你回溯时，你就会知道你已经做了什么。

你回溯的每一步，再次检查这些动作。如果您撤消正确的选择，您会知道您已经尝试过left和right，但还没有尝试forward。

于 2013-04-20T14:49:33.927 回答
2

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

在每次迭代中，尝试从堆栈中弹出一个帧。如果堆栈是空的，你已经尝试了所有可能的动作。

现在，看看你从堆栈中弹出的位置。这是你现在的位置。

将所有从您弹出的位置导致未探索位置的移动添加到堆栈中。如果其中任何一个是目标位置，那么您就完成了。

其余的将自行处理。考虑一下，在纸上尝试几个案例，你会看到的。:)

于 2013-04-20T14:53:59.900 回答
1

您没有很多解决方案：基本上，探索没有循环的迷宫就像在覆盖树上进行深度优先搜索，每个交叉点都是一个节点。

您可以随时构建树，并使用该信息遍历它，但这将是乏味且效率不高的。

深度优先搜索的一种常见方法是将所有要检查的节点压入堆栈，拉出一个，然后再次压入，直到达到目标。但是你会得到很多节点堆叠起来，一旦你找到了目标节点，你就无法使用堆栈来知道你遵循了哪条路径，这意味着你需要将这些信息存储在其他地方。

最好保留堆栈解决方案并标记堆栈中的节点以指示分支，以及已探索分支的哪个方向（即哪个子树） （或留下哪些路径）。如果您始终以相同的顺序进行探索，则该标签可以只是一个数字：

  • 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每次到达新位置时，您都按下 a ，并在其选项全部测试完后将其平仓。当您到达迷宫出口时，您的堆栈仅包含所需的移动。

于 2013-04-20T14:55:27.763 回答
0

基本上，我怎么知道我需要从堆栈中弹出多少步才能知道我回到了原来的交叉点，所以我可以选择另一个分支而不是被阻塞的分支？

你没有——你总是准确地倒退一步。然后检查所有（剩余的）备选方案，然后再往前退一步……等等。这称为回溯。

顺便说一句，无论您是否使用递归，这都是相同的。使用递归只会使堆栈隐式，并且堆栈处理是自动的。

于 2013-04-20T14:54:35.697 回答