《最短路径算法分类与应用研究》由会员分享,可在线阅读,更多相关《最短路径算法分类与应用研究(15页珍藏版)》请在金锄头文库上搜索。
1、课题结题论文题 目最短路径算法分类与应用研究学 院专 业班 级学生指导教师2008年10月最短路径算法分类与应用研究姓 名:班 级:指导教师 :摘要本文研究目的在于收集整理关于最短路径的普遍算法, 为研究最短路径问题在一些出行问题、 管理问题、 工程问题及实际生活问题中的应用, 为企业和个人提供方便的选择方法。 同时, 也为参加数学建模的同学提供一些解题的思路与方法, 为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。通过应用最短路径算法中的蚁群算法来解决浙江旅行商问题, 以各城市经纬度作为初始条件,通过MATLAB 程序计算最短路径,并画出最短路线图。关键词最短路径算法,最短路径应
2、用,蚁群算法,浙江旅行商摘要I关键词I第一章绪论1第二章最短路径算法1一、Dijkstra 算法 11、适用条件和范围 12、算法描述13、算法实现1二、A*算法11、适用条件和范围 12、算法原理23、算法描述2三、Bellman-Ford 算法21、适用条件和范围 22、算法描述23、算法实现3四、Topological Sort(拓扑排序)算法31、适用条件和范围 32、算法描述33、算法实现3五、SSSP On DAGi:法31、适用条件和范围 32、算法描述43、算法实现4六、Floyd算法41、适用范围42、算法描述43、算法小结4七、Prim算法41、适用范围42、算法描述43、
3、算法实现4八、Kruskal 算法51、适用范围52、算法描述53、算法实现5九、Johnson 算法51、适用范围52、算法实现5第三章最短路径算法应用5一、TSP问题的介绍5二、TSP问题算法的介绍51、贪心算法52、模拟退火算法63、遗传序列算法 64、蚁群算法7三、算法应用71、解决浙江旅行商问题时算法描述 72、蚁群算法的 MATLABi序描述 83、蚁群算法解决浙江旅行商问题 10第四章总结11致谢11参考文献12第一章 绪论随着电脑科学的发展,人们生产生活效率要求的提高,最短路径问题逐渐成为电脑科学、运筹学、 地理信息科学等学科的一个研究热点。 也正因为最短路径问题在实际生产生活
4、中应用广泛,优化该算法和提高算法的求解效率具有重大的现实意义。最短路径问题是图论研究中的一个经典算法问题,旨在寻找图由结点和路径组成的中两结点之间的最短路径。算法具体的形式包括:确定起点的最短路径问题即已知起始结点,求最短路径的问题;确定终点的最短路径问题与确定起点的问题相反,该问题是已知终结结点,求最短路径的问题;在无向图中该问题与确定起点的问题完全等同,在有向图中该问题等同于把所有路径方向反转确实定起点的问题;确定起点终点的最短路径问题即已知起点和终点,求两结点之间的最短路径;全局最短路径问题求图中所有的最短路径。用于解决最短路径问题的算法被称作最短路径算法。本文研究目的在于收集整理关于最
5、短路径的普遍算法,为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用,为企业和个人提供方便的选择方法。同时,也为参加数学建模的同学提供一些解题的思路与方法,为比赛提供有利的资源。最后应用蚁群算法来解决浙江旅行商问题。第二章 最短路径算法本课题旨在总结归纳最短路径的普遍算法,经收集资料发现最短路径算法主要有: Dijkstra 算法、A*算法、Bellman-Ford 算法、Topological Sort(拓扑排序)算法、SSSP On DA既法、 Floyd 算法 、 Prim 算法、 Kruskal 算法及 Johnson 算法。其中最常用的路径算法有: Dijks
6、tra 算法、A*算法、Bellman-Ford算法及Floyd算法。一、 Dijkstra 算法1、适用条件和范围: 1 单源最短路径从源点 s 到其它所有顶点 v ;2有向图和无向图无向图可以看作u,v , v,u 同属于边集E 的有向图 ;3所有边权非负任取i, j E 都有Wij0 。2、算法描述:如果 v1- v2f v3f v4是 v1- v4的最短路径,则 v1- v2f v3 一定是 v1f v3的 最短路径。v2f v3f v4 -一定是 v2f v4的最短路径。3、算法实现: 1 初始化: disv=maxint v V,v s ; diss=0 ; pres=s;S=s
7、; 2 For i:=1 to n取 V-S 中的一顶点 u 使得 disu=mindisv|v 6 V-S S=S+uFor V-S 中每个顶点 v do Relaxu,v,WU,v 3 算法结束: disi 为 s 到 i 的最短距离; prei 为 i 的前驱节点。程序见参考文献8 。二、A*算法1、适用条件和范围:A*算法属于一种启发式搜索。它扩展结点的次序类似于广度优先搜索,但不同的是每生成一 个子结点需要计算估价函数 F,以估算起始结点到该结点的代价及它到达目标结点的代价的和; 每当扩展结点时,总是在所有待扩展结点中选择具有最小F值的结点作为扩展对象,以便使搜索尽量沿最有希望的方向
8、进行。因此,A*算法只要求产生问题的全部状态空间的部分结点,就可以求解问题了,搜索效率较 高。确定估价函数方法通常是:搜索到该结点的深度+距离目标最近的程度。2、算法原理:如图有如下的状态空间:起始位置是A,目标位置是P,字母后的数字表示节点的估价值状态空间图搜索过程中设置两个表:OPEW口 CLOSED OPE破保存了所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。算法中有一步是根据估价函数重排OPEN表。这样循环中的每一步只考虑OPENB1中状态最好的节点。3、算法描述:1初始状态:OPEN=A5;CLOSED电2估算A5,取得搜有子节点,并放入OPEN1中;OPEN=B4,
9、 C4, D6; CLOSED=A53估算B4,取得搜有子节点,并放入OPEN1中;OPEN=C4, E5, F5, D6; CLOSED=B4, A54估算C4;取得搜有子节点,并放入OPEN1中;OPEN=H3, G4, E5, F5, D6;CLOSED=C4, B4, A55估算H3,取得搜有子节点,并放入OPEN1中;OPEN=O2, P3, G4, E5, F5, D6; CLOSED=H3c4, B4, A56估算O2,取得搜有子节点,并放入OPEN1中;OPEN=P3, G4, E5, F5, D6; CLOSED=O2, H3, C4, B4, A57估算P3,已得到解。三、
10、Bellman-Ford 算法1、适用条件和范围:1单源最短路径(从源点s到其它所有顶点V);2有向图和无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);3边权可正可负(如有负权回路输出错误提示 );4差分约束系统。2、算法描述: 1 对每条边进行|V| 次 Relax 操作;2如果存在u,vC E使得disu+wdisv,则存在负权回路;否则 disv即为s到v 的最短距离, prev 为前驱。3、算法实现:1PASCAL言For i:=1 to |V|-1 doFor 每条边(u,v) C E doRelax(u,v,w);For 每条边(u,v) C E doIf di
11、su+w 0 & distk edgekj+distj更新当前值 四、 Topological Sort( 拓扑排序 ) 算法1、适用条件和范围:1AOVO (ActivityOn Vertex Network); 2 有向图;3作为某些算法的预处理过程(如 DP)。2、算法描述: 1 每次挑选入度为 0 的顶点输出 ( 不计次序 ) ; 2 如果最后发现输出的顶点数小于|V| ,则说明有回路存在。3、算法实现: 1 数据结构: adj: 邻接表 ; 有 4 个域 u,v,w,next ; indgri: 顶点 i 的入度;stack: 栈;2初始化 :top=0 (栈顶指针 ) ; 3 将初
12、始状态所有入度为 0 的顶点压栈;4 I=0(计数器 ) ; 5 While 栈非空 (top0) do顶点v出栈;输出v;计数器增1;For与v邻接的顶点u doa. dec(indgru) ;b. If indgru=0 then 顶点 u 入栈; 6 EXIT(I=|V|) 。五、SSSP On DAGM法1、适用条件和范围: 1 DAG(Directed Acyclic Graph, 有向无环图 ) ; 2 边权可正可负。2、算法描述: 1 Toposort ; 2 If Toposort=False Then HALT(Not aDAG); 3 For 拓扑序的每个顶点 u doFo
13、r u 的每个邻接点 v doRelax(u,v,w) ; 4 算法结束后:如有环则输出错误信息;否则 disi 为 s 到 i 的最短距离, prei 为前驱 顶点。3、算法实现:此算法时间复杂度O(V+E), 时间和编程复杂度低, 如遇到符合条件的题目 (DAG), 推荐使用。还有,此算法的步骤 3 可以在 toposort 中实现,这样即减小了此算法复杂度的一个系数。六、 Floyd 算法1、适用范围: 1 APSP(All Pairs Shortest Paths) ; 2 稠密图效果最正确; 3 边权可正可负。2、算法描述: 1 初始化: disu,v=wu,v 。 2 For k=1 to nFor i=1 to nFor j=1 to nIf disi,jdisi,k+disk,jThenDisi,j=disi,k+disk,j。 3算法结束:dis 即为所有点对的最短路径矩阵。3、算法小结:此算法简单有效, 由于三重循环结构紧凑, 对于稠密图, 效率要高于执行|V| 次 Dijkstra算法。4、算法实现:见参考文献11 。七、 Prim 算法1、适用范围: 1 用于求无向图的最小生成树; 2 无向图( 有向图的是最小树形图 ) ; 3 多用于稠密图。2、算法描述:设图 G = V , E ,其生成树的顶点集合为 U。 1 把 v0 放入 U ;