最短路径算法三种算法简介

Dijkstra 算法，A*算法和D*算法 Dijkstra 算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra 算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 Dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE 表方式，Drew 为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE 表的方式。 大概过程： 创建两个表，OPEN, CLOSE。 OPEN 表保存所有已生成而未考察的节点，CLOSED 表中记录已访问过的节点。 1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。 2． 从 OPEN 表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE 表中。 3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN 表中。 4． 重复2， 3，步。直到OPEN 表为空，或找到目标点。 提高Dijkstra 搜索速度的方法很多，常用的有数据结构采用Binary heap 的方法，和用Dijkstra 从起始点和终点同时搜索的方法。 A*（ A-Star)算法是一种启发式算法，是静态路网中求解最短路最有效的方法。 公式表示为： f(n)=g(n)+h(n), 其中f(n) 是节点n 从初始点到目标点的估价函数， g(n) 是在状态空间中从初始节点到n 节点的实际代价， h(n)是从n 到目标节点最佳路径的估计代价。 保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取： 估价值h(n)<= n 到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。 如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。 估价值与实际值越接近，估价函数取得就越好。 例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即 f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))； 这样估价函数f 在 g 值一定的情况下，会或多或少的受估价值h 的制约，节点距目标点近，h 值小，f 值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra 算法的毫无无方向的向四周搜索。 conditions of heuristic Optimistic (must be ...