罗密欧朱丽叶迷宫的一系列问题

Question

广度优先 分支限界法
移动方向只有上下左右四个方向吗 可以斜着吗
封闭房间是随机吗
整体思路什么样的

Answer 1

可以使用广度优先搜索和A*算法解决

• 移动方向只能是上下左右四个方向,不能斜着走。因为迷宫通道都是垂直或水平的。
• 迷宫通道可以是随机的,也可以是预定义的。随机生成可以增加问题难度,预定义可以便于测试算法。

思路
使用广度优先搜索从起点开始遍历迷宫,找到通向终点的路径。
使用A*搜索,它是广度优先搜索的扩展。在搜索过程中,不仅考虑路径的长度,也考虑路径的代价(例如通道类型)。这样可以找到最短且代价最小的路径。