最短路径算法介绍.docx

最短路径算法介绍
据Drew所知最短路经算法现在重要的应用有计算机网络路由算法，机器人探路，交通路线导航，人工智能，游戏设计等等。美国火星探测器核心的寻路算法就是采用的D*(DStar)算法。
最短路经计算分静态最短路计算和动态最短路计典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN,CLOSE表方式，Drew为了和下面要介绍的A*算法和D*算法表述一致，这里均采用OPEN,CLOSE表的方式。
大概过程:
创建两个表，OPEN,CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
重复2，3,步。直到OPEN表为空，或找到目标点。
T.
11
inlrmlrr■*Mb-i-丄■■*Bb-i-丄：—二二二二—4—i—4—i—4—i—4—i!Ttt-'ttt:
这是在drew程序中4000个节点的随机路网上Dijkstra算法搜索最短路的演示，黑色圆圈表
示经过遍历计算过的点由图中可以看到Dijkstra算法从起始点开始向周围层层计算扩展，在计
算大量节点后，到达目标点。所以速度慢效率低。
提高Dijkstra搜索速度的方法很多，据Drew所知，常用的有数据结构采用Binaryheap的方法，和用
Dijkstra从起始点和终点同时搜索的方法。
推荐网页：http://www-CS-ecnu-edu-cn/assist/js04/ZJS045/ZJS04505/zjs045050a-htm
简明扼要介绍Dijkstra算法，有图解显示和源码下载。
A*(AStar)算法：启发式(heuristic)算法
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算法的毫无无方向的向四周搜索。
conditionsofheuristic
Optimistic(mustbelessthanorequaltotherealcost)
Asclosetotherealcostaspossible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点)break;
else
{
if(XinOPEN)比较两个X的估价值f//注意是同一个节点的两个不同路径的估价值
if(X的估价值小于OPEN表的估价值)
更新OPEN表中的估价值；〃取最小路径的估价值
if(XinCLOSE)比较两个X的估价值〃注意是同一个节点的两个不同路径的估价值
if(X的估价值小于CLOSE表的估价值)
更新CLOSE表中的估价值；把X节点放入OPEN〃取最小路径的估价值
if(Xnotinboth)
求X的估价值；
并将X插入OPEN表中；〃还没有排序
}
将n节