启发式路径搜索

06年《程序员》有一期专题策划叫做”算法的力量”,被认为是年度最佳的一个专题,最近又温习一遍,重读李开复、凌小宁等人的文章,有不少新的收获。王咏刚那篇《算法悖论》提到斯坦福博士生Amit关于路径搜索的总结,简单读后感觉该学的东西还有很多。

一般说来,最短路算法划分为静态最短路和动态最短路算法。静态路径最短路是外界条件不变,计算起点到终点的最短路径,主要有Dijkstra算法和A*算法。而动态路径最短路是外界环境不断发生变化,无法计算预测路径的情况下求最短路,典型的有D*算法,在机器人探路中常应用D*算法,美国火星探测器的关键寻路算法就是采用的D*实现。其中自己更感兴趣以A*为代表的启发式路径搜索算法。

Dijkstra是数据结构中必定会涉及的典型最短路算法,Dijkstra算法按路径长度递增顺序产生一个节点到其他所有节点最短路径,以起始点为中心向外层层扩展,直到终点为止。Dijkstra算法可以得到最短路径的最优解,但由遍历计算的节点过多而效率较低。

启发式(Heuristic)A*(A-Star)算法应该是静态路网中求解最短路时最有效的方法。启发式搜索与深度优先(DFS)和广度优先(BFS)这类盲目型搜索最大的不同,在于当前搜索结点选择下一步路径时,通过启发函数计算选择代价最少的结点,设计优秀的启发函数往往求得最优解的同时具备较低的时间复杂度。而DFS和BFS算法在运气不好时可能需要遍历完整个解空间。

A*算法公式表示为:F(n)=G(n)+H(n),其中F(n) 是节点n从初始点到目标点的估价函数,G(n) 是状态空间中从初始节点到n节点的实际代价,H(n)则是节点n到目标节点最佳路径的估计代价。当前结点到目标结点的估值函数H(n)是启发式搜索设计的核心。保证找到最短路径的充要条件是,估价函数H(n)计算的两点间距离小于等于实际距离。对于几何路网来说,可以取两节点间欧几理德直线距离做为估价值,即F(n)=G(n)+Sqrt((dx-nx)*(dx-nx)+(dy-ny) *(dy-ny)),这样估价函数F在G值一定的情况下,受估价值H制约保证路径搜索向终点的方向进行,而不是像Dijstra算法无方向的向四周延伸搜索。

最短路算法不仅在GIS的交通路线导航、路径分析领域应用广泛,在解决路径搜索相关的应用中也十分普遍,包括网络路由算法、机器人探路、人工智能、游戏设计等等。已有同学基于云风的路径搜索算法给出改进后的源代码,希望可以在理解A*算法原理方面提供一定帮助。