algorithm - 如何轻松知道迷宫是否有从起点到终点的道路？

Question

我使用 0,1 数组实现了一个迷宫。入口和目标在迷宫中是固定的。入口始终是迷宫的 0,0 点。目标始终是迷宫的 m-1,n-1 点。我目前使用的是广度优先搜索算法，但是速度不够好。特别适用于大型迷宫(100*100左右)。有人可以帮我解决这个算法吗？

这是我的解决方案:

queue = []
position = start_node
mark_tried(position)
queue << position
while(!queue.empty?)
  p = queue.shift  #pop the first element
  return true if maze.goal?(p)
  left = p.left
  visit(queue,left) if can_visit?(maze,left)
  right = p.right
  visit(queue,right) if can_visit?(maze,right)
  up = p.up
  visit(queue,up) if can_visit?(maze,up)
  down = p.down
  visit(queue,down) if can_visit?(maze,down)
end
return false

可以访问吗？方法检查节点是否在迷宫内，节点是否被访问，节点是否被阻塞。

Answer 1

可能的最差答案。

1)往前走，直到你不能动为止

2)向左转

3) 冲洗并重复。

如果你成功了，那就结束了。

更好的解决方案。

遍历您的迷宫，为开放节点和封闭节点保留 2 个列表。使用著名的A-Star算法 选择评估下一个节点并丢弃死胡同的节点。如果您用完了打开列表中的节点，则没有导出。