最短路径算法分类与应用研究论文.docx
《最短路径算法分类与应用研究论文.docx》由会员分享，可在线阅读，更多相关《最短路径算法分类与应用研究论文.docx（25页珍藏版）》请在冰点文库上搜索。
最短路径算法分类与应用研究论文
课题结题论文
2008年10月
最短路径算法分类与应用研究
摘要
本文研究目的在于收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。
同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。
最后应用蚁群算法来解决浙江旅行商问题。
通过应用最短路径算法中的蚁群算法来解决浙江旅行商问题，以各城市经纬度作为初始条件，通过MATLAB程序计算最短路径，并画出最短路线图。
关键词
最短路径算法，最短路径应用，蚁群算法，浙江旅行商
目录
摘要I
关键词I
第一章绪论2
第二章最短路径算法2
一、Dijkstra算法2
1、适用条件和范围2
2、算法描述2
3、算法实现2
二、A*算法2
1、适用条件和范围3
2、算法原理3
3、算法描述3
三、Bellman-Ford算法3
1、适用条件和范围3
2、算法描述4
3、算法实现4
四、Topological Sort（拓扑排序）算法4
1、适用条件和范围4
2、算法描述4
3、算法实现4
五、SSSP On DAG算法4
1、适用条件和范围4
2、算法描述5
3、算法实现5
六、Floyd算法5
1、适用范围5
2、算法描述5
3、算法小结5
七、Prim算法5
1、适用范围5
2、算法描述5
3、算法实现5
八、Kruskal算法6
1、适用范围6
2、算法描述6
3、算法实现6
九、Johnson算法6
1、适用范围6
2、算法实现6
第三章最短路径算法应用6
一、TSP问题的介绍6
二、TSP问题算法的介绍6
1、贪心算法6
2、模拟退火算法7
3、遗传序列算法7
4、蚁群算法8
三、算法应用8
1、解决浙江旅行商问题时算法描述8
2、蚁群算法的MATLAB程序描述9
3、蚁群算法解决浙江旅行商问题11
第四章总结12
致谢12
参考文献13
第一章绪论
随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。
也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：
确定起点的最短路径问题—即已知起始结点，求最短路径的问题；确定终点的最短路径问题—与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；确定起点终点的最短路径问题—即已知起点和终点，求两结点之间的最短路径；全局最短路径问题—求图中所有的最短路径。
用于解决最短路径问题的算法被称作最短路径算法。
本文研究目的在于收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。
同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。
最后应用蚁群算法来解决浙江旅行商问题。
第二章最短路径算法
本课题旨在总结归纳最短路径的普遍算法，经收集资料发现最短路径算法主要有：
Dijkstra算法、A*算法、Bellman-Ford算法、Topological Sort（拓扑排序）算法、SSSP On DAG算法、Floyd算法、Prim算法、Kruskal算法及Johnson算法。
其中最常用的路径算法有：
Dijkstra算法、A*算法、Bellman-Ford算法及Floyd算法。
一、Dijkstra算法
1、适用条件和范围：
（1）单源最短路径（从源点s到其它所有顶点v）；
（2）有向图和无向图（无向图可以看作
，
同属于边集E的有向图）；
（3）所有边权非负（任取
都有
）。
2、算法描述：
如果v1→v2→v3→v4是v1→v4的最短路径，则v1→v2→v3一定是v1→v3的最短路径。
v2→v3→v4一定是v2→v4的最短路径。
3、算法实现：
（1）初始化：
dis[v]=maxint
；dis[s]=0；pre[s]=s;S={s}；
（2）For i:
=1 to n
①取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}
②S=S+{u}
③For V-S中每个顶点v do Relax
（3）算法结束：
dis[i]为s到i的最短距离；pre[i]为i的前驱节点。
程序见参考文献[8]。
二、A*算法
1、适用条件和范围：
A*算法属于一种启发式搜索。
它扩展结点的次序类似于广度优先搜索，但不同的是每生成一个子结点需要计算估价函数F，以估算起始结点到该结点的代价及它到达目标结点的代价的和；每当扩展结点时，总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象，以便使搜索尽量沿最有希望的方向进行。
因此，A*算法只要求产生问题的全部状态空间的部分结点，就可以求解问题了，搜索效率较高。
确定估价函数方法通常是：
搜索到该结点的深度+距离目标最近的程度。
2、算法原理：
如图有如下的状态空间：
（起始位置是A，目标位置是P，字母后的数字表示节点的估价值）
状态空间图
搜索过程中设置两个表：
OPEN和CLOSED。
OPEN表保存了所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
算法中有一步是根据估价函数重排OPEN表。
这样循环中的每一步只考虑OPEN表中状态最好的节点。
3、算法描述：
（1）初始状态：
OPEN=[A5];CLOSED=[];
（2）估算A5，取得搜有子节点，并放入OPEN表中；
OPEN=[B4,C4,D6];CLOSED=[A5]
（3）估算B4，取得搜有子节点，并放入OPEN表中；
OPEN=[C4,E5,F5,D6];CLOSED=[B4,A5]
（4）估算C4；取得搜有子节点，并放入OPEN表中；
OPEN=[H3,G4,E5,F5,D6];CLOSED=[C4,B4,A5]
（5）估算H3，取得搜有子节点，并放入OPEN表中；
OPEN=[O2,P3,G4,E5,F5,D6];CLOSED=H3C4,B4,A5]
（6）估算O2，取得搜有子节点，并放入OPEN表中；
OPEN=[P3,G4,E5,F5,D6];CLOSED=[O2,H3,C4,B4,A5]
（7）估算P3，已得到解。
三、Bellman-Ford算法
1、适用条件和范围：
（1）单源最短路径（从源点s到其它所有顶点v）；
（2）有向图和无向图（无向图可以看作（u,v）,（v,u）同属于边集E的有向图）；
（3）边权可正可负（如有负权回路输出错误提示）；
（4）差分约束系统。
2、算法描述：
（1）对每条边进行|V|次Relax操作；
（2）如果存在（u,v）∈E使得dis[u]+w3、算法实现：
（1）PASCA语言
Fori:
=1to|V|-1do
For每条边（u,v）∈Edo
Relax（u,v,w）;
For每条边（u,v）∈Edo
Ifdis[u]+w
（2）C/C++语言
voidbellman_ford（intv）
{for1ton
initializedist[v];
for2ton-1（i）
for1ton（j）
for1ton（k）
ifedge[k][j]>0&&dist[k]>edge[k][j]+dist[j]
更新当前值}
四、Topological Sort（拓扑排序）算法
1、适用条件和范围：
（1）AOV网（Activity On Vertex Network）；
（2）有向图；
（3）作为某些算法的预处理过程（如DP）。
2、算法描述：
（1）每次挑选入度为0的顶点输出（不计次序）；
（2）如果最后发现输出的顶点数小于|V|，则表明有回路存在。
3、算法实现：
（1）数据结构：
adj:
邻接表;有4个域{u,v,w,next}；
indgr[i]:
顶点i的入度；
stack[]:
栈；
（2）初始化:
top=0 （栈顶指针）；
（3）将初始状态所有入度为0的顶点压栈；
（4）I=0 （计数器）；
（5）While栈非空（top>0） do
①顶点v出栈；输出v；计数器增1；
②For与v邻接的顶点u do
a. dec（indgr[u]）；
b. If indgr[u]=0 then顶点u入栈；
（6）EXIT（I=|V|）。
五、SSSP On DAG算法
1、适用条件和范围：
（1）DAG（Directed Acyclic Graph,有向无环图）；
（2）边权可正可负。
2、算法描述：
（1）Toposort；
（2）If Toposort=False Then HALT（Not a DAG）；
（3）For拓扑序的每个顶点u do
For u的每个邻接点v do
Relax（u,v,w）；
（4）算法结束后：
如有环则输出错误信息；否则dis[i]为s到i的最短距离，pre[i]为前驱顶点。
3、算法实现：
此算法时间复杂度O（V+E），时间和编程复杂度低，如遇到符合条件的题目（DAG），推荐使用。
还有，此算法的步骤（3）可以在toposort中实现，这样即减小了此算法复杂度的一个系数。
六、Floyd算法
1、适用范围：
（1）APSP（All Pairs Shortest Paths）；
（2）稠密图效果最佳；
（3）边权可正可负。
2、算法描述：
（1）初始化：
dis[u,v]=w[u,v]。
（2）For k=1 to n
For i=1 to n
For j=1 to n
If dis[i,j]>dis[i,k]+dis[k,j] Then
Dis[i,j]=dis[i,k]+dis[k,j]。
（3）算法结束：
dis即为所有点对的最短路径矩阵。
3、算法小结：
此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。
4、算法实现：
见参考文献[11]。
七、Prim算法
1、适用范围：
（1）用于求无向图的最小生成树；
（2）无向图（有向图的是最小树形图）；
（3）多用于稠密图。
2、算法描述：
设图G=（V，E），其生成树的顶点集合为U。
（1）把v0放入U；
（2）在所有u∈U，v∈V-U的边（u，v）∈E中找一条最小权值的边，加入生成树；
（3）把
（2）找到的边的v加入U集合。
如果U集合已有n个元素，则结束，否则继续执行
（2）。
3、算法实现：
（1）集合：
设置一个数组set（i=0,1,..,n-1），初始值为0，代表对应顶点不在集合中（注意：
顶点号与下标号差1）；
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替；
（3）具体程序见参考文献[12]。
八、Kruskal算法
1、适用范围：
（1）MST（Minimum Spanning Tree,最小生成树）；
（2）无向图（有向图的是最小树形图）；
（3）多用于稀疏图；
（4）边已经按权值排好序给出。
2、算法描述：
（1）将边按非降序排列；
（2）While合并次数少于|V|-1
①取一条边（u,v）（因为已经排序，所以必为最小）
②If u,v不属于同一连通分量then
a.合并u,v所在的连通分量
b.输出边（u,v）
c.合并次数增1；tot=tot+W（u,v）
（3）算法结束：
tot为MST的总权值。
3、算法实现：
见参考文献[13]。
九、Johnson算法
1、适用范围：
Johnson算法适用于求AllPairsShortestPath。
2、算法实现：
Johnson算法应用了重标号技术
（1）先进行一次Bellman-Ford算法；
（2）然后对原图进行重标号，w'（i,j）=h[i]-h[j]+w（i,j）；
（3）然后对每个点进行一次Dijkstra。
第三章最短路径算法应用
一、TSP问题的介绍
TSP问题，即旅行商问题，是一种典型的组合最优化问题，可描述为某旅行商欲往n个城市推销货物，从某个城市出发，沿途经过各个城市一次后返回出发城市，要确定一条行走的路线，计算途径n个城市的最短距离，即给定ｎ个城市和两两城市之间的距离，确定一条经过每个城市并且仅经过一次的路线，要求总路径最短。
TSP分为2类，即对称TSP和不对称TSP。
对于城市数目为n的地图,共有n种不同的路径。
城市越多,可能的路径也越多。
而且路径的增加速度非常快且是非线形的。
当n很大时，去尝试每一种可能的路径是不可能的，所以需要设计一个有效的算法去寻找最短的路径。
二、TSP问题算法的介绍
1、贪心算法
贪心算法的主要思想是永远选择当前最短的路径。
这是解决TSP问题的最简便的算法。
贪心算法容易实现但是效率不好。
如下图所示:
有4个城市:
A，B，C和D。
距离从A到B是5公里，A到C是6公里，A到D是9公里，B到C是3公里,B到D是7公里，C到D是8公里。
假设我们一开始在A，比较A到其他点的路径长度，找出A到B是最短的路径（5公里）。
我们从A到B，然后设定A和B之间的距离无限大。
在B我们找出B到C（3公里）是最短的路径。
如此然后去C，再到D。
所以，此算法则总是选择最短的路径。
2、模拟退火算法
模拟退火算法是一种求解大规模组合优化问题的方法，对于NP-完全组合优化问题尤其有效。
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温（即退火），使之达到能量最低点。
反之，如果急速降温（即淬火）则不能达到最低点。
加温时,固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。
根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp（-E/（kT））,其中E为温度T时的内能，E为其改变量，k为Boltzman常数。
用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法:
由初始解i和控制参数初值t开始，对当前解重复产生“新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值,算法终止时的当前解即为所得近似最优解。
所以我们可以通过上面的思想写出解决TSP问题的模拟退火算法。
步骤如下:
（1）初始化:
初始温度T（充分大）,初始解状态s（随机选取一条TSP路线,算出走完此路线的长度Cost（s）作为评价函数,这是算法迭代的起点）,每个T值的迭代次数L；
（2）对k=1至k=L做第（3）至第（6）步；
（3）产生新解
（一般利用2-opt算法来产生新的路径）；
（4）计算增量Cost=Cost（
）-Cost（s），其中Cost（s）为评价函数；
（5）若
则接受
作为新的当前解,否则以概率exp（-
/T）接受
作为新当前解；
（6）如果满足终止条件则输出当前解作为最优解,结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法；
（7）T逐渐减少，且T趋于0，然后转第2步运算。
3、遗传序列算法
遗传算法简称GA（GeneticAlgorithm）,在本质上是一种不依赖具体问题的直接搜索方法。
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。
并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。
然后,把这些假设解置于问题的“环境”中,并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。
这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
步骤如下:
（1）产生一群染色体（不同的游历路径）然后计算评估每个染色体的健壮度（总路径长度）。
（2）选留健壮度较好的染色体（总路径较短的路径），剩下的作为父染色体；
（3）父染色体交换,倒转或移位产生下一代染色体（其中有5%的染色体变异的概率）；
（4）在下一代染色体的基础上回到第
（1）步骤；
（5）循环整个程序多次，记录下每代的最好的染色体；
（6）选择其中最优秀的染色体作为最优解。
4、蚁群算法
首先引入TSP中常用符号：
m为蚁群中蚂蚁数量；
为ｔ时刻位于城市ｉ的蚂蚁个数，且
；
为城市i和j之间的距离；
为边（i,j）的能见度，反映由城市i转移到城市j的启发程度；
为边（i,j）上的信息素轨迹强度；
为蚂蚁ｋ在边（i,j）上留下的单位长度轨迹信息素量；
为蚂蚁k的转移概率；
j是尚未访问的城市。
在初始时刻，各条路径上的信息素量相等，设
，（
为常数），蚂蚁
被随机放到某个城市，然后根据各条路径上的信息素量选择下一个城市。
在ｔ时刻，
（1）
式中：
表示蚂蚁ｋ下一步允许选择的城市；
α和β为2个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。
为了阻止蚂蚁重复访问，为每只蚂蚁都设计一个被称为禁忌表（tabulist）的数据结构。
经过ｎ个时刻，蚂蚁完成一次循环，各路径上信息素“蒸发”和增加的量根据下式调整：
（2）
式中：
表示信息素蒸发后的剩余，则（1-
）为衰减系数，表示信息素的减少；
表示信息素增加的量，在式
（1）中
（3）
表示第k只蚂蚁在时刻
留在路径
上的信息素量；
，Q为常数，
为第k个蚂蚁爬过路径
的长度，等于
的值。
至此，一个蚂蚁的循环过程结束，由此反复迭代多次，最终得出优化结果。
三、算法应用
1、解决浙江旅行商问题时算法描述
第一步：
初始化，将所有城市坐标列出，并计算出两两城市之间的距离。
第二步：
用蚁群算法迭代一次，得出一个最优解，由此来计算出
和
的大小。
由
得到信息素的初值，然后进行信息素更新，判断是否超出
范围，如果超出，则限制大小。
第三步：
继续迭代，直到第三次，得到
。
判断信息素是否超出
，如果超出，则限制大小。
第四步：
往复迭代计算，直到达到最大迭代次数。
每一次计算都得出新的最优解，所以每一次计算中，
和
都会重新被更新，是一个动态变化范围。
第五步：
输出最后结果。
2、蚁群算法的MATLAB程序描述
2.1蚁群算法解决TSP的主要符号说明：
n为城市个数；
C为n个城市的坐标，n×2的矩阵；
m为蚁群中蚂蚁数量；
NC_max最大迭代次数；
Alpha表征信息素重要程度的参数；
Beta表征启发式因子重要程度的参数；
Rho信息素蒸发系数；
Q信息素增加强度系数；
R_best各代最佳路线；
L_best各代最佳路线的长度；
2.2MATLAB程序描述：
第一步变量初始化
n=size（C,1）;
D=zeros（n,n）;
fori=1:
n
forj=1:
n
ifi~=j
D（i,j）=（（C（i,1）-C（j,1））^2+（C（i,2）-C（j,2））^2）^0.5;
else
D（i,j）=eps;
end
D（j,i）=D（i,j）;
end
end
Eta=1./D;
Tau=ones（n,n）;
Tabu=zeros（m,n）;
NC=1;
R_best=zeros（NC_max,n）;
L_best=inf.*ones（NC_max,1）;
L_ave=zeros（NC_max,1）;
whileNC<=NC_max
第二步将m只蚂蚁放到n个城市上
Randpos=[];
fori=1:
（ceil（m/n））
Randpos=[Randpos,randperm（n）];
end
Tabu（:
1）=（Randpos（1,1:
m））';
第三步m只蚂蚁选择下一座城市，完成各自的周游
forj=2:
n
fori=1:
m
visited=Tabu（i,1:
（j-1））;
J=zeros（1,（n-j+1））;
P=J;
Jc=1;
fork=1:
n
iflength（find（visited==k））==0
J（Jc）=k;
Jc=Jc+1;
end
end
fork=1:
length（J）
P（k）=（Tau（visited（end）,J（k））^Alpha）*（Eta（visited（end）,J（k））^Beta）;
end
P=P/（sum（P））;
Pcum=cumsum（P）;
Select=find（Pcum>=rand）;
to_visit=J（Select
（1））;
Tabu（i,j）=to_visit;
end
end
ifNC>=2
Tabu（1,:
）=R_best（NC-1,:
）;
End
第四步记录本次迭代最佳路线
L=zeros（m,1）;
fori=1:
m
R=Tabu（i,:
）;
forj=1:
（n-1）
L（i）=L（i）+D（R（j）,R（j+1））;
end
L（i）=L（i）+D（R
（1）,R（n））;
end
L_best（NC）=min（L）;
pos=find（L==L_best（NC））;
R_best（NC,:
）=Tabu（pos
（1）,:
）;
L_ave（NC）=mean（L）;
NC=NC+1
第五步更新信息素
Delta_Tau=zeros（n,n）;
fori=1:
m
forj=1:
（n-1）
Delta_Tau（Tabu（i,j）,Tabu（i,j+1））=Delta_Tau（Tabu（i,j）,Tabu（i,j+1））+Q/L（i）;
end
Delta_Tau（Tabu（i,n）,Tabu（i,1））=Delta_Tau（Tabu（i,n）,Tabu（i,1））+Q/L（i）;
end
Tau=（1-Rho）.*Tau+Delta_Tau;
Tabu=zeros（m,n）;
End
第六步输出结果
Pos=find（L_best==min（L_best））;
Shortest_Route=R_best（Pos
（1）,:
）
Shortest_Length=L_best（Pos
（1））
DrawRoute（C,Shortest_Route）
functionDrawRoute（C,R）
N=length（R）;
scatter（C（:
1）,C（:
2））;
holdon
plot（[C（R
（1）,1）,C（R（N）,1）],[C（R
（1）,2）,
升级会员 