4

我需要一些帮助来编写一套穿越迷宫的 if-then 规则。这就是问题：

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

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

用英文写 if-then 规则，用于遍历墙壁和检测循环。假设您知道网格的大小和您可能必须经过的最大距离才能逃离迷宫。”

这是我到目前为止所拥有的：

  1. 开始

  2. 如果只找到一条路径（左、右或直），请按照该路径。

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

    如果找到左路，左转。

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

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

  4. 否则，如果发现死胡同，则转“U”形。

    转到第 2 步

  5. 结尾

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

4

1 回答 1

3

有两种用于探索图的通用算法：广度优先搜索 (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
于 2013-05-16T02:46:22.067 回答