迷宫遍历算法

Question

我需要在迷宫中编写一组if-then规则的帮助。问题如下：

“假设迷宫是通过在方格单元格上放置墙壁来构建的，以使路径从迷宫内任何单元格通向没有墙壁的迷宫外边缘。”

一种方法是左手法则，但是这种策略可能会让你陷入循环。

编写英语if-then规则以穿越墙壁并检测循环。假定您知道网格的大小和最大行程，可以逃离迷宫。”

到目前为止，我有：

1. 开始

2. 如果只找到一条路线（左、右或直），则跟随该路线。

3. 否则，如果发现多个路径：

   如果找到左侧路径，请向左转。

   否则，如果找到直接路径，请跟随直接路径。

   否则，如果找到右侧路径，请向右转。

4. 否则，如果发现死路，请掉头。

   转到步骤2

5. 结束

但是这不能解决循环问题。请问有人可以帮忙吗？

- user2303699

---

通常要记住你访问过的地方。除非你不被允许这样做（这真的可能吗？）。 - nhahtdh

如果你在一个矩形平面迷宫的边缘开始，并且出口/目标也在边缘上，那么无论是右手规则还是左手规则最终都能带你到达目的地。如果你的起点在这样的迷宫内部，那么你需要能够检测循环；在这种情况下，你需要切换到另一堵墙。仍然有可能遇到某些退化情况，例如遍历拓扑等价于八字形（lemniscate）的形状。这意味着存在多个有效的解决方案路线。从那里开始，你需要一种方法来多次切换墙壁（超过路径跟踪）。 - Jim Dennis

记住任何相邻的步骤，并在没有立即穿过第二个步骤时检测到已经遇到了较旧的步骤，将会检测到一个循环（虽然不一定高效，但最终会检测到）。 - Jim Dennis

谢谢您的解释，让我更加清楚了！ - user2303699

Answer 1

有两个通用算法用于探索图形：广度优先搜索（BFS）和深度优先搜索（DFS）。这些算法的技巧在于它们从未探测列表中开始所有路径，随着它们访问路径，将其添加到已探测列表中。当您访问每个节点时，将其从未探测列表中删除，以便不再访问。只从每种情况下的未探测列表中拉出节点，您不会有重返自己的情况。

以下是防止循环的DFS和BFS示例：

function DFS(G,v):
  label v as explored
  for all edges e in G.adjacentEdges(v) do
      if edge e is unexplored then
          w ← G.adjacentVertex(v,e)
          if vertex w is unexplored then
              label e as a discovery edge
              recursively call DFS(G,w)
          else
              label e as a back edge

现在开始BFS：

procedure BFS(G,v):
  create a queue Q
  enqueue v onto Q
  mark v
  while Q is not empty:
      t ← Q.dequeue()
      if t is what we are looking for:
          return t
      for all edges e in G.adjacentEdges(t) do
           u ← G.adjacentVertex(t,e)
           if u is not marked:
                mark u
                enqueue u onto Q
  return none

- chubbsondubs

---

也许在这里提到“回溯”会让谷歌找到你。 (-: - tripleee

谢谢！我现在对这个有了更好的理解！ - user2303699