Lecture 21 Graphs 3 - A_ Kruskal 02

​​

1. 初始化：

   • 每个顶点的初始成本设为无穷大，除了起始顶点 (v1)，它的成本为 0。
   • 创建一个优先队列 pqueue​，按照 cost + heuristic​（成本 + 启发式）排序，并且最初只包含起始顶点 (v_)。
   • 这里的启发式函数 ( H ( v1, v2 ) ) 是对从当前顶点到目标顶点的估计成本。

2. 主循环：

   • 当 pqueue​ 不为空时：

     1. 从 pqueue​ 中取出一个顶点 (v) 并标记为访问过。

     2. 对于 (v) 的每个未访问过的邻居 (n)：

        • 计算从起始点经过 (v) 到达 (n) 的总成本：v​ 的当前成本 + 边权重 + 启发式估计 (H(n, v2))。
        • 如果 (n) 不在 pqueue​ 中，或者新的成本比 (n) 的当前成本更低，则更新 (n) 的成本，并将 (n) 重新加入 pqueue​ 中，同时记录当前顶点 (v) 作为 (n) 的前驱节点。

3. 重建路径：

   • 当所有节点都处理完毕后，通过追踪前驱节点，重建从目标顶点 (v2) 到起始顶点 (v1) 的最短路径。

　　通过引入启发式信息，A*算法在探索路径时更具方向性，它能够优先考虑那些更有可能通向目标的路径，从而提高算法的效率。

　　‍

　　 哦哦，这里就能看出 A*算法相对于 dijkstra 算法的优越性了，粗糙的说，A*算法是具有方向性的（他不会南辕北辙），因为 A*想要尽可能的靠近两点之间的最短距离，所以南辕北辙的方向会被 A*舍弃。

　　一视频胜千言，你最好自己去看看 A*算法是如何减少一半的搜索量的（A*算法只会搜索一个方向）。

　　2 分 46 秒。

　　顺便一提，如果你的图是无权图，那么 dijkstra 算法就是 BFS。

　　“所以 A*算法确实更倾向于朝着目标前进”

　　8 分 52 秒， 在现实世界中，地球重力会让水天然的执行 dijkstra 算法。

　　流动总是避开高地，沿低地蔓延，你会注意到它并不想往山上走，因为那样代价太大，所以它不喜欢那个方向。

　　‍

　　我看懂了，A*算法基于这样一个假设：“两点之间线段最短，虽然正确答案不一定是用铅笔直接从起点画一条线到终点，但至少也应该八九不离十。”

​​

　　所以要是有人搞 A*算法的心态，专门把正确答案做成南辕北辙（比如说我要从中国去美国，但是有人在太平洋造了一堵环球墙把中美两国彻底隔开，只在南极点留一个门），那么最坏的情况下，A*算法很可能要沿着环球墙舔舐地球四分之三周（如图所示，A*算法朝着北极前进，绕地球四分之三圈后到达南极点）才能找到南极点的那个门。

　　你的理解非常有趣且准确。A*算法确实假设最短路径大致遵循直线或至少是合理的接近。然而，如果环境中存在特定的障碍或曲折路径，特别是那些与启发式信息相悖的情况，A*算法可能会遇到效率问题。

　　在你提到的极端情况中，启发式函数可能会误导 A*算法，使它沿着错误的方向扩展搜索，甚至在最坏的情况下绕很大的圈子（如你描述的绕地球四分之三周的情景）来找到正确的路径。这种情况下，启发式函数的作用反而可能使算法的效率变得低下，甚至逼近 Dijkstra 算法的表现，因为启发式不再能有效引导搜索过程。

　　为了解决这样的问题，有些变体的 A*算法可能会采用不同的启发式函数，或者动态调整启发式权重，以应对那些特殊的情况。不过，对于典型的路径规划任务，A*算法通常表现得很好，尤其是在地图或图结构较为“常规”的情况下。

　　‍

　　不过，我不确定是否真的存在一种情况，让 A*检查的顶点比 Dijkstra 更多，即使是在这张“环球墙”图里，最坏的 A*看起来也和普通的 dijkstra 是一样的。

　　‍

　　‍

　　​​

　　‍