遍历迷宫的算法-Java 学习之路

我需要一些帮助来编写一组if-then规则来遍历迷宫 . 这就是问题：

“假设迷宫是在方形细胞网格上构建的，方法是将墙壁放置在细胞的某些边缘上，使得从迷宫内的任何细胞到没有墙壁的迷宫的外边缘都有一条路径 .

一种方法是左手规则，但这种策略可以带你到周期 .

用英语编写if-then规则，用于遍历墙并检测循环 . 假设你知道网格的大小和你可能要逃离迷宫的最大距离 . “

这是我到目前为止：

开始
如果只找到一条路径（左或右或直线），请遵循路径 .
否则如果找到多个路径：

如果找到左路径，请向左转 .

否则，如果找到直线路径，请沿直线路径行驶 .

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

否则如果找到死角，请转“U” .

转到第2步

结束

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

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

回复于 2024-05-10T23:59:11+08:00

遍历迷宫的算法

1 回答

相关问题