穿越迷宫的算法

Question

我需要一些帮助来编写一套用于穿越迷宫的 if-then 规则。这是问题所在:

“假设迷宫是在方形单元格的网格上构建的，方法是在单元格的某些边缘放置墙壁，这样从迷宫内的任何单元格到迷宫外边缘都有一条路径没有墙。

一种方法是左手定则，但这种策略可以让您循环往复。

用英文写 if-then 规则，用于穿墙和检测循环。假设您知道网格的大小和逃离迷宫可能需要行驶的最大距离。”

这是我目前所拥有的:

1. 开始

2. 如果只找到一条路径(左或右或直线)，则遵循该路径。

3. 否则如果找到多个路径:

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

   否则，如果找到直线路径，则遵循直线路径。

   如果找到正确的路径，则右转。

4. Else 如果发现死胡同，则掉头。

   转到第 2 步

5. 结束

但这并没有解决循环问题。有人可以帮忙吗？

Answer 1

有两种用于探索图的通用算法:广度优先搜索 (BFS) 和深度优先搜索 (DFS)。这些算法的诀窍是它们从未探索列表中的所有路径开始，并且当它们访问路径时，它们将这些路径添加到已探索列表中。当您访问每个节点时，您将其从未探索列表中删除，这样您就不会重新访问它。通过在每种情况下仅从未探索的列表中拉出节点，您就不会遇到需要加倍处理自己的情况。

以下是带有检查以防止循环和 BFS 的 DFS 示例:

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