如何轻松了解迷宫是否有从开始到目标的道路？

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

can_visit？方法检查节点是否在迷宫内,节点是否被访问,节点是否被阻塞.

Answer 1

最坏的答案可能.

1)走到前面,直到你无法移动

2)左转

3)冲洗并重复.

如果你做到了,就会结束.

更好的解决方案.

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