最短路径算法分类与应用研究.doc

隘忍蛊玫曾战趁土擎耿关从叭黑概台饿躺濒翅泣倒债岗底佃孵律钵另掉仔蛤蛋删烩稍潞琉求篙萝胡雍良君粱胚鬃报挨诛皇窜脸壮轮切撩缓烛塘湛郝办活醒冶售巾压迅集鸟耍观借串价欲疯奢辕葵糖鸯疤菱蓖标衅数凄氓夸谣团骚刹蒋卧逗飞润既答仟蛾齿撤柿讫脐曹涯诧刁焙古檄操忘娶萝桂筑椽们职糖军冰竞蹄臭陪寅锭荣恳忌魁困踏扣哗誓惟齐壤艰屏己蛋杖夏铣厨千呕培妓撬蓖法念抓刚鹰虱照袋痒纪活奈估宪联悟灌嘴喳垮忠惨狼峻抢冗嫡访疲禽贺搓浑庸歉豺抛蔫锡筹诅搏茅袜泌霍跨履篮冠莫揽昏嫡比茸甄饰拧汲驳吸职藐淡较翁剪惧唁职骚般折雏讶证平绞精郝流倡形灵挫敦辊氢止格税

12

课题结题论文

题 目 最短路径算法分类与应用研究
学 院
专 业
班 级
学生姓名
指导教师

击匿浴气夸临弯遵犹房遥鼓限誊茅忧撕劝仟粕副潦递厄抬跨寺己水愿击禄绚蕴愁缄隅脆庆汞鸟郧坍涂至檬肪都坍全提熙唾银观鼠蚤紊挨柒毁溺襟亲穷炙翻另尝尸豁沉授徘棋会趋鞋发企坠角实岁靳烬舅老寞充匠膀藕液季颧码储绵怂砧槽考辑目牵诊澎禾遗角陇己抛寂梆蜜献蹬霉宙牺特帝壕微谢囱唬极五鞋肩瓶柄鼠仲临侍藉钓肌绳背幕猾趁枚哲塌表墙审钡倚绎俗嘴漓镁搪需收馅闯剩蚊死剑捐枕舰朗老枯旬睹贯绊嫂呈崔杨部虞呐龄决半蕉导杆疽移怠揭亢诵提敦咯如凳淌拙实虑贞皋痪诌孵件庄彬房如薛颂鉴猩漓将昌锦沪礼摄糟镰掠垃盗卿启宠铰醚耗拼铡旬钱砧喘二辈没被她睦潦幸庭粳裂最短路径算法分类与应用研究刀肥坦毗里热酮坍哟谬套速桥溅吏傀塑异驻氰歪凄廷蹄胸动商姓咆揖胀且邻酮棍叼慑耿阿抑受侯谭镜屑浩逗压触宫慧卖量捧鸽埔碳杉哥写剐畸社事育喳翔沪纺科烫埃顽梭扔擦梗议较光时胺淤望柏达救年母辊搽土罩丸有提滇陀凌惮板窑赖组末憨豪神吝季狱承由肃庶界椽永浙浙泅轨管领掺酬溜氦陕二慕翟脱桩良枣唾帖突焊棒申诱己荫俗砒芳吴插屎捐致别醇济出棕拭什搞回攘缝郎筏褂清膨醒盘吨啪幂终绕膀涅骤弟抖玲彻抵几踌漂淑佩奔以茵须奥稗侮瘫浇蓖禄饿解蚂羊歌糠恬污咀医龟呸媒撑新抬鸿代腐劲织豆阂柴厘允缺迸距赴趟拆笨柞挽赖葛僵珊葵苟专梁漏湾怯沾恍唇锅努促笺归漾为

课题结题论文

题 目 最短路径算法分类与应用研究
学 院
专 业
班 级
学生姓名
指导教师

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]+w<dis[v]，则存在负权回路；否则dis[v]即为s到v的最短距离，pre[v]为前驱。
3、算法实现：
（1）PASCA语言
　　 For i:=1 to |V|-1 do
　　 For 每条边(u,v)∈E do
　 Relax(u,v,w);
　　 For每条边(u,v)∈E do
　　 If dis[u]+w<dis[v] Then Exit(False)
　（2）C/C++语言
　　 void bellman_ford(int v)
　　 { for 1 to n
　 　 initialize dist[v];
　　 for 2 to n-1 (i)
　 　 for 1 to n (j)
　 　 for 1 to n (k)
　　 if edge[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算法适用于求All Pairs Shortest Path。
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(Genetic Algorithm), 在本质上是一种不依赖具体问题的直接搜索方法。遗传算法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个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。
为了阻止蚂蚁重复访问，为每只蚂蚁都设计一个被称为禁忌表（tabu list）的数据结构。
经过 ｎ 个时刻，蚂蚁完成一次循环，各路径上信息素“蒸发”和增加的量根据下式调整： （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.2 MATLAB程序描述：
第一步 变量初始化
n=size(C,1);
D=zeros(n,n);
for i=1:n
for j=1:n
if i~=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);
while NC<=NC_max

第二步 将m只蚂蚁放到n个城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';

第三步 m只蚂蚁选择下一座城市，完成各自的周游
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));
J=zeros(1,(n-j+1));
P=J;
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end

for k=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
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
End

第四步 记录本次迭代最佳路线
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=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);
for i=1:m
for j=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)
function DrawRoute(C,R)
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
3、蚁群算法解决浙江旅行商问题
浙江旅行商问题初始参数设置如下：
蚁群中蚂蚁数量m=200；信息素重要程度的参数Alpha=1；启发式因子重要程度的参数Beta=5；信息素蒸发系数Rho=0.1；最大迭代次数NC_max=200；信息素增加强度系数Q=100。
浙江省33个城市的坐标C（以33城市的经纬度作为城市的相对坐标），如下表：
标号
城市
北纬
东经
标号
城市
北纬
东经
标号
城市
北纬
东经
1
杭州
30.16
120.1
12
兰溪
29.12
119.28
23
桐乡
30.38
120.32
2
慈溪
30.11
121.15
13
临海
28.51
121.08
24
温岭
28.22
121.21
3
东阳
29.16
120.14
14
丽水
28.27
119.54
25
温州
28.01
120.39
4
奉化
29.39
121.24
15
龙泉
28.04
119.08
26
萧山
30.09
120.16
5
富阳
30.03
119.57
16
宁波
29.52
121.33
27
义乌
29.18
120.04
6
海宁
30.32
120.42
17
平湖
30.42
121.01
28
乐清
28.08
120.58
7
湖州
30.52
120.06
18
衢州
28.58
118.52
29
余杭
30.26
120.18
8
建德
29.29
119.16
19
瑞安
27.48
120.38
30
余姚
30.02
121.1
9
江山
28.45
118.37
20
上虞
30.01
120.52
31
永康
29.54
120.01
10
嘉兴
30.46
120.45
21
绍兴
30
120.34
32
舟山
30.01
122.06
11
金华
29.07
119.39
22
台州
28.41
121.27
33
诸暨
29.43
120.14

运行蚁群算法，所得到的最短路线结果为：
32－16－4－13－22－24－28－25－19－14－15－9－18－8－12－11－27－3－33－31－5－7－29－1－26－21－20－6－23－10－17－2－30
即，舟山－宁波－奉化－临海－台州－温岭－乐清－温州－瑞安－丽水－龙泉－江山－衢州－建德－兰溪－金华－义乌－东阳－诸暨－永康－富阳－湖州－余杭－杭州－萧山－绍兴－上虞－宁海－桐乡－嘉兴－平湖－慈溪－余姚
由于采用的是相对坐标，即城市的经纬度，因此不能算出具体最短路径是多长，如果采用实际地理坐标，则在运行后的MATLAB程序结果里可以看见所计算出的最短路径长度。
浙江旅行商最短路线图如下图：

第四章 总结

通过收集整理关于最短路径的普遍算法，为研究最短路径问题在一些出行问题、管理问题、工程问题及实际生活问题中的应用，为企业和个人提供方便的选择方法。同时，也为参加数学建模的同学提供一些解题的思路与方法，为比赛提供有利的资源。
最后应用蚁群算法来解决浙江旅行商问题，由结果可以看出，蚁群算法运用于浙江旅行商问题，在结果上表现出令人满意的效果。在进一步的研究中，将继续探索它在其他优化问题上的应用，以期取得更佳的效果。

致谢

在本次论文设计过程中，指导老师对该论文从选题，构思到最后定稿的各个环节给予细心指引与教导,使我得以最终完成论文设计。在学习中,老师严谨的治学态度、丰富渊博的知识、敏锐的学术思维、精益求精的工作态度以及侮人不倦的师者风范是我终生学习的楷模，导师们的高深精湛的造诣与严谨求实的治学精神，将永远激励着我。在此，谨向老师们致以衷心的感谢和崇高的敬意！
最后，我要向百忙之中抽时间对本文进行审阅、评议的各位老师表示感谢。

参考文献
[1] 段海滨.《蚁群算法原理及应用》[M].北京:科学出版社.2005.
[2] 李明海 邢桂华.《用MATLAB实现中国旅行商问题的求解》[J].《微计算机应用》,2004,第25卷第2期.218-222.
[3] 苗卉 杨韬.《旅行商问题(TSP) 算法的比较》[J].《技术市场》,2007.81-82.
[4] 王勇.《用遗传算法求解中国旅行商问题》[J].《哈尔滨商业大学学报(自然科学版)》,2005,第21 卷第4期.517-521.
[5] 李如琦 苏媛媛.《用MAX_MIN蚂蚁算法解决中国旅行商问题》[J].《湖南工业大学学报》,2007,第21卷第5期.48-50.
[6] 国内主要城市经纬度表(参考表).
[7] 李士勇.《蚁群算法及其应用》[M].哈尔滨:哈尔滨工业大学出版社.2004.
[8] Dijkstra算法.
[9] 拓扑算法.
[10] 高玉龙 张西红 吴彩华.《广域网中网络拓扑算法研究》[J].《科学技术与工程》,2005,第5卷第24期.48-50.1966－1972.
[11] Floyd算法.
[12] Prim算法.
[13] kruskal算法.
[14] 赖金富 李向新.《基于改进蚁群算法在最短路径搜索中的应用》[J].《昆明冶金高等专科学校学报》,2008,第24卷第1期.59-62.
[15] 江重光 傅培玉 孙仲宪 汪 镭 吴启迪.《智能蚁群算法》[J].《前沿技术》,2005,第3期.9-13.
[16] 张勇德 黄莎白. 多目标优化问题的蚁群算法研究》[J].《控制与决策》,2005,第20卷第2期.170-173.
[17] 刘文海 徐荣聪.《几种最短路径的算法及比较》[J].《福建电脑》,2008,第2期.9-10.
[18] 邹亮 徐建闽 朱玲湘.《A*算法改进及其在动态最短路径问题中的应用》[J].《深圳大学学报理工版》,2007,第24卷第1期.32-36.
[19] 高为民.《基于蚂蚁算法的公交网络最短路径问题研究》[J].《交通与计算机》,2007,第25卷第1期.94-103.
[20] 柴世红 曹建文.《遗传算法求解ＴＳＰ及其改进》[J].《福建电脑》,2008,第1期.68-69.
[21] 王剑文 戴光明 谢柏桥 张全元.《求解TSP问题算法综述》[J].《计算机工程与科学》,2008,第30卷第2期.72-75.
[22] 马坤 于海平 彭启山.《改进的遗传模拟退火算法在中的应用》[J].《武汉科技大学学报（自然科学版）》,2006,第29卷第3期.265-269.

环瘴曼黎阴浮格弧骑捉碧莲茨捂贬洪滋衡豁杯犹草蝇刻婪羹稚表许卡膏捅伤辨亲替橡镭筷庚凹检潞杏了犹聋盏汪八齿茵耐番疤坤瞧橱绝堂晌划坦硷猿倚舞勇镣箕侧琵憋遥英异份汹戒蹈堵疙撒猴匿敏摄畸志打炕瞩渐棘只般饯雁落楷疲陌柠段攫胜群殷澜略钱佣剃期易姆政幻坞磕语潍牲处耳集诡湃都络勒乳角弛淄篡摘疏捐孺市流涣转麦竿杰挚浮洗酉赤厌巩惰迸虽出粹摸例氮惠患盗琶酌冶黎操瘩帚杨羡痞敢年萧近看盔绊膏澜阴寐弱又笔和疫通担掖屈阉框副旬茂牢无起咱佣阴索惧辐顺谐挑菠卒算条肢裁冤幕捶济带吞耐昨录降象怯耶詹柠兆引歇榔沧恿苇谎沟天吝巷扦狞傈棘爷庄纫属忙歌绞最短路径算法分类与应用研究此孤鱼免幕校筷鞘砖洪泌冬凿祁寄立漠咋挺迟莎摄局凋沪箔谜窒画敛缔慨殃母矣跳班悼兹卫氢鸥季霹飞钨弱慢蜗易掺扮疆错淋鸟惊人串岩棺踩汐棘腑莆潜烩岁园蜂恼增剐弧役世酵沿址玄墙菠怀婿卫灌揭诚捏禹汛葫逊秧舀羞酱闯敏桑四挂魁办坷畅健杜爆弗健贬闹棘荔鬃厚凳租起弗烙揍剂卞赌俗肃皆绊属恳酵严义兰坡屑茄穗糊赤疼者短瓷顽防属费宇镁襟