- 当前
- 队列中
- 已确定
- 路径
- 直线估计
A* 搜索
A* 搜索像 Dijkstra 算法一样,找出从起点到终点的最短路径,但它大致知道终点在哪里。每个节点都有一个对剩余距离的估计,即到终点的直线距离,搜索总是从目前距离加估计值最小的节点继续。点击节点作为起点,选一个终点,再一步一步查看搜索如何朝终点前进,让图中整片角落都不被触及。 按“播放”观看搜索过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。点击节点可将其设为起点;把点击切换为“终点”,再点击另一个节点,即可将其设为终点。每条边上的数字是它的长度,每个节点上的数字是它目前的距离,虚线是对剩余距离的直线估计。图下方的一行是队列,得分最低的排在前面,并标出每个得分:目前的距离加上估计值。“新图”会生成另一张图;可选择节点数和边数。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 点击一个节点设为起点。把点击切换为“终点”,再点击另一个节点设为终点。
- 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到搜索中的任意位置。
- 观察队列中的得分和虚线表示的直线估计。最后,比较 A* 和 Dijkstra 算法各需要多少个节点。
A* 搜索的原理
把起点的距离设为 0 并放入队列。队列中的每个节点都有一个得分:目前的距离加上对剩余距离的估计。重复以下步骤:取出得分最低的节点,把它的距离标为确定。如果它是终点,就停止。否则,对每个尚未确定的邻居,把边的长度加到该节点的距离上;如果结果比邻居目前的距离短,就更新它,记下该节点作为来路,并把邻居连同新得分放入队列。
为什么估计值不能偏大
只要估计值从不说终点比实际更远,A* 就能找到最短路径:这样的估计叫作可采纳的估计。直线就是一种,因为两地之间没有哪条路比直线更短。估计值过大可能让 A* 错过最佳路线;处处估计为 0 则让 A* 变成 Dijkstra 算法,虽然安全,但会朝每个方向搜索。估计越好,A* 需要的节点越少。在本应用中,每条边的长度等于它画出来的长度(向上取整),所以直线是一个安全的估计。
常见问题
什么是 A* 搜索?
一种寻路算法,找出从起点到终点的最短路径。它的工作方式和 Dijkstra 算法相同,但按目前的距离加上剩余距离的估计来排列队列,因此会朝终点前进,而不是向四面八方扩散。
什么是可采纳启发式?
对到终点距离的一种估计,它从不超过真实的最短距离。有了可采纳的估计,A* 总能找到最短路径。地图上的直线距离就是经典例子。
A* 比 Dijkstra 算法快吗?
通常是的,前提是你只需要到一个终点的路线,而且有不错的估计:A* 确定的节点更少,因为远离终点的节点得分较高。估计为 0 时,它的做法和 Dijkstra 算法完全相同。如果需要到每个节点的距离,Dijkstra 算法是更好的选择。
A* 用在哪里?
电子游戏用它让角色绕过障碍物,它还用于路线规划、机器人运动规划,以及 15 数码等谜题的求解器,其中的估计计算各方块离原位有多远。
我的图会被发送到别处吗?
不会。图在你的浏览器中生成和搜索,上次的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器