实际工作的迷宫算法-Java 学习之路

-5

我一直在努力尝试解决迷宫并从开始到结束输出路径 . 不管我做了什么，它从来都不是100％真正有效 . 它设法像它应该的那样回避整个迷宫并找到结束......但实际上只输出它应该采取的路径是行不通的 . 它适用于一些生成的迷宫，但不是一般的 . 它还包括一些死胡同 .

问题是我可能在线尝试了10种不同的DFS算法，但它们都不起作用 . 令人非常困惑的是，许多不同的网站似乎都有不起作用的算法，我几乎实际上已经实现了它们 .

如果有人可以提供一个实际工作伪代码，如何使用显示相关路径的堆栈来编写简单的迷宫求解器，那将是非常友好的 . 经过20-25个小时的实验，我认为我不会再到任何地方了 .

1 回答

不完全是伪代码，但它应该工作

define node: {int id}
define edge: {node a , b ; int weight (default=1)}

define listNeighbours:
input: node n
output: list of neighbours

define dfs:
input: list nodes, list edges, node start, node end
output: list path

bool visited[length(nodes)]
fill(visited , false)

list stack
add(stack , start)
visited[start.id] = true

while ! isEmpty(stack)
     node c = first(stack)

     if c.id == end.id
          return stack

     list neighbours = listNeighbours(c)
     bool allVisited = true
     node next

     for node n in neighbours
          if visited[n.id]
                continue
          else
                allVisited = false
                next = n

      if allVisited
          pop(stack)
      else
          push(stack , next)

return null

注意：节点的ID总是<=图中的节点总数，并且在图中是唯一的

回复于 2024-04-28T21:22:19+08:00

实际工作的迷宫算法

1 回答

相关问题