侯祥林旅行商问题的多点优化贪心算法与程序设计
旅行商问题的多点优化贪心算法与程序设计
侯祥林，费烨，韦金秀 沈阳建筑大学，110168
摘要：针对经典旅行商问题，从贪心算法基本思想出发，建立了分别以所有节点为起点，以总路程最小值为最优路径的一种多点贪心算法。应用Visual Basic 语言编制优化路径求解程序。并针对30个节点和50个节点的算例分析。该算法具有简单实用性，能够对具体问题实现快速计算，为工程问题分析提供基础。
关键词：旅行商问题，贪心算法，多点贪心算法，程序设计
1．引言
旅行商问题（Traveling Saleman Problem ，TSP ）属于NP 难题，也称为货郎担问题，是由爱尔兰数学家Sir William Rowan Hamilton 和英国数学家Thomas Penyngton Kirkman 在19世纪提出的数学问题。它是指：假设有一个旅行商人要拜访 n 个城市，需要选择一条最优路径，每个城市只能拜访一次，而且最后要回到原来出发的城市。
如何确定最短路线。TSP 问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n 个点的所有排列的集合，大小为n ！。路径的选择目标是要求得的路径路程为所有路径之中的最小值。由于该问题的描述简单，而其实际模型在管道铺设，线路选择等优化问题中又有着广泛的应用，故长期以来一直吸引着国内外许多研究人员进行研究，他们尝试着用各种算法来求解TSP 问题。归纳起来有：近似解法、局部搜索法、神经网络、遗传算法、克隆算法、模拟退火算法、混合遗传算法等[1~10]。
在所有的算法中，贪心算法是容易理解的好算法，也可也达到问题的一个次优解。但是古典的贪心算法存在的问题的最后返回出发点可能会出现一个较大的距离。本文将在古典的贪心算法基础上，通过改进获得一个称为多点贪心算法，并给出算例分析。
2．多点贪心算法原理
2.1 贪心算法基本原理
设共有n 点，以下称为节点，其节点号码分别为1,2,,n 。贪心算法依据下面过程：（1）从1号节点出发，分别计算1号节点余下的1n -个节点距离，与1号节点的最短距离点称为2'，最小距离为1,2d '；（2）计算2'号节点与余下的2n -个节点距离，与2'号节点的最短距离点称为3'，其最小距离为2,3d ''； ；（3）计算j '号节点与余下的n j -个节点距离，与j '号节点的最短距离点称为
(1)j '+，其最小距离为,(1)j j d ''+； ；（4）最后，计算(1)n '-号节点与余下的n '号节点距离，
(1),n j n d '''-。总路程：1
1,2,(1),12
n j j n j L d d d -'''''+==++∑。上面的算法，可能会导致最后返回出发点的距离
很大。
2.2 多点贪心算法原理
为了改善贪心算法直接计算的不足，可以考虑出发节点不同情况；两个步骤：（1）确定从n 个
节点中的每个节点出发，依据贪心算法确定总路程1
,2,(1),12
,1,2,,n i i j j n j L d d d i n -'''''+==++=∑ 。；（2）比
较,1,2,,i L i n = ，获得最短路程：min 1min i i n
L L ≤≤=。（3）按min L ，给出行走路线；无论从哪个节点
出发，都将按此行走路线方向行走；
3．算法过程的Visual Basic 程序描述
（1）输入节点数量与坐标； ,(),(),1,2,n x x i y y i i
n
= 1kk =
（2）标记目前节点，设置kk 点为开始节点；
1 ()(),()() For i to n x i xx i y i yy i Next i
=== (1),(1)(1)(),(1)()(),()temx x temy y x x kk y y kk x kk temx y kk temy
====== （3）确定以kk 为开始节点的贪婪路线：包括计算、比较每步最小距离，计算路线总距离
Pr int #1, 1 1
1 (,)(((()())^2(()())^2))^0.5
kk For i to n For j i to n
d i j x i x j y i y j Next j
=-=+=-+- 计算第i 点与余下所有点距离
2 (, 1) (, ) ( 1): ( 1):( 1) (): ( 1) ()() : () (, 1): (, 1) (, ) (, ) :For j i To n
If d i i d i j Then
temx x i temy y i x i x j y i y j x j temx y j temy
temd d i i d i i d i j d i j temd Curj j E =++>=+=++=+====++=== Pr int #1,"",1. ((), ())-(( 1), ( 1)), (255, 0, 0) (,1)(((()(1))^2(()(1))^2))^0.51. ((), ())-((1), (1)), (0, 255, 0)
nd If
Next j
j
Picture Line x i y i x i y i RGB Next i
d n x n x y n y Pictur
e Line x n y n x y RGB -->++=-+-
比较出第i 点与余下所有点的最小距离，并获得第1i +点；
文件输出，行走路线
绘制行走路线
()0
1 1()()(,1) dd kk For i to n dd kk dd kk d i i Next i
==-=++ ()()(,1)
Pr int #1,()
dd kk dd kk d n dd kk =+
计算从kk 点为开始节点的最小贪心路程
文件输出路程长度
（4） 当kk n <时，1kk kk ?+转到 （2） 当kk n =时，转到 （5）
（5）比较多点贪心算法最优路程，获得最优出发点_ opt kk
2 (1) () (1):(1) ()
() _ For kk To n
If dd dd kk Then
tem dd dd dd kk dd kk tem
opt kk kk End If Next kk
=>====
4. 算例分析
算例1： 具有30个节点TSP 问题，其节点坐标位置见表1。
表1 算例1的 节点坐标 序号 x y 序号 x y 序号 x y 1 41 94 11 64 60 21 87 76 2 37 84 12 18 54 22 18 40 3 54 67 13 22 60 23 13 40 4 25 62 14 83 46 24 82 7 5 7 64 15 91 38 25 62 32 6 2 99 16 25 38 26 58 35 7 68 58 17 24 42 27 45 21 8 71 44 18 58 69 28 41 26 9 54 62 19 71 71 29 44 35 10
83
69
20
74
78
30
4
50
下表为程序计算的从序号节点出发的路程情况。
表2 算例1不同起点贪心算法路程列表
序号 路程 序号 路程 序号 路程 1 572.9255 11 546.4583 21 534.0436 2 571.8588 12 565.6044 22 590.5583 3 539.7319 13 486.9163 23 590.1809 4 482.6496 14 488.7771 24 569.4215 5 515.4323 15 473.3292 25 577.7069 6 515.4324 16 542.6708 26 497.5285 7 523.1558 17 539.5327 27 520.0176 8 597.2203 18 536.9409 28 530.1949 9 532.7935 19 507.0815 29 532.7643 10
592.1368
20
513.0300
30
499.3936
多点贪婪算法的最短路程为 L= 473.3292。图绘制出了该情况的行走路线。起点为15号节点。其行走顺序为：
15→14→8→7→11→9→3→18→19→20→10→21→1→2→4→13→12→17→16→22→23→30→5→6→29→28→27→26→25→24→15
图1 算例1行走路线
算例2
具有50个节点的TSP问题，其节点坐标位置为表3。
表3 算例2的节点坐标
序号x y 序号x y 序号x y 序号x y
1 31 3
2 14 42 41 27 56 37 40 62 63
2 32 39 15 17 3
3 28 52 41 41 20 26
3 40 30 16 25 32 29 49 49 42 5 6
4 37 69 17
5 64 30 58 48 43 13 13
5 27 68 18 8 52 31 57 58 44 21 10
6 3
7 52 19 12 42 32 39 10 45 30 15
7 38 46 20 7 38 33 46 10 46 36 16
8 31 62 21 5 25 34 59 15 47 62 42
9 30 48 22 10 17 35 51 21 48 63 69
10 21 47 23 45 35 36 48 28 49 52 64
11 25 55 24 42 57 37 52 33 50 43 67
12 16 57 25 32 22 38 58 27
13 17 63 26 27 23 39 61 33
表4 算例1不同起点贪心算法路程列表
序号路程序号路程序号路程序号路程
1 565.0313 14 567.27 27 593.9211 40 560.0534
2 563.8102 15 570.2241 28 586.1978 41 504.2818
3 571.0603 16 539.0402 29 559.2667 42 524.3514
4 544.258
5 17 507.4037 30 576.6629 43 524.3514
5 534.962
6 18 535.7208 31 489.191
7 44 535.4759
6 512.5934 19 561.153
7 32 524.8142 45 589.0931
7 552.4794 20 558.473 33 538.1735 46 555.7452
8 539.5091 21 564.0051 34 598.4741 47 585.4095
9 511.2411 22 601.7819 35 557.8325 48 494.0723
10 510.5335 23 565.4716 36 550.5068 49 492.705
11 503.8491 24 519.5168 37 574.7575 50 492.705
12 527.7145 25 546.9865 38 576.3978
13 493.3062 26 574.9308 39 524.3655
多点贪婪算法的最短路程为L= 489.1917。图绘制出了该情况的行走路线。起点为31号节点。其行走顺序为：
31→40→48→49→50→4→8→5→13→12→11→9→6→7→14→23→3→36→37→27→28→29→3 0→47→39→38→35→34→33→32→46→45→25→26→41→15→16→1→2→10→19→20→21→22→4 3→44→42→18→17→24→31
图2 算例2行走路线
5．结论
本文在贪心算法的基础上，建立了多点贪心算法。建立了从所有节点出发点的贪心算法获得路程，进行比较获得更优路程与行走路经的思想。同时，应用VB环境开发所研究算法的计算程序。给出了30个节点和50个节点的算例分析与可视化行走路线。
可见，与贪心算法相比，结果获得优化。而与复杂算法对比，该算法简单，容易实现，同时可以获得较好的结果，具有一定的实用性。
参考文献
1．邢文训, 谢金星. 现代优化计算方法[M]. 北京: 清华大学出版社,1998: 117-121.
2．Gregory G, Abraham P. The Traveling Salesman Problem and Its Variations[M]. Dordrecht Hardbound: Kluwer Academic Publishers, 2002.
3．周培德. 求解货郎担问题的几何算法[J]. 北京理工大学学报, 1995,15(1): 97-99.
4．邹鹏. 求解TSP 问题的多级归约算法[J]. 软件学报, 2003, 14(1):35-42.
5．朱文兴, 傅清祥. 一个基于填充函数变换的对称TSP 问题的局部搜索算法[J]. 计算机学报, 2002, 25(7): 701-707.
6．孙惠文. 遗传算法求解旅行商问题[J]. 西南交通大学学报, 1996,31(5): 550-554.
7．陈沐天, 蔡和熙. 货郎担问题的几何分块算法及ChinaTSP 问题的最终解决[J]. 计算机工程与科学, 1998, 20(1): 22-27.
8．王凌. 智能优化算法及其应用[M]. 北京: 清华大学出版社, 2001.
9．李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究［J］.重庆邮电大学学报，2008（5）. 10．王剑文. 求解TSP 问题算法综述［J］．计算机工程与科学，2008，30（2）：72~74，155.
Multi-point Optimize Greedy Algorithm and Program Design About TSP
Hou Xiaing-lin, Fei ye, Wei Jin-xiu
Shenyang Jianzhu University, 110168
Abstract: To solve well the classical traveling salesman problem(TSP), based on the idea of greedy algorithm，a kind of multi-point optimize greedy algorithm is sets up. In this algorithm, all nodes can be firstly made as starting point to search path by greedy algorithm, and optimal path will be acquired by comparing with all minimum total distance. Visual Basic language is used to establish program to solve the optimal path. And models of 30 nodes and 50 nodes are used for examples in the numerical analysis. This algorithm is simple and practical. It can be used to rapidly compute specific problem, and provide condition for the analysis of engineering problems.
Keyboard: traveling salesman problem (TSP), greedy algorithm, multi-point optimize greedy algorithm, program design
旅行商问题概述_郭靖扬
旅行商问题（ＴｒａｖｅｌｉｎｇＳａｌｅｓｍａｎＰｒｏｂｌｅｍ，简称ＴＳＰ）是一个著名的组合优化问题：给定ｎ个城市，有一个旅行商从某一城市出发，访问每个城市各一次后再回到原出发城市，要求找出的巡回路径最短。如果用图论来描述，那就是已知带权图Ｇ＝ （Ｃ，Ｌ），寻出总权值最小的Ｈａｍｉｌｔｏｎ圈。其中Ｃ＝｛ｃ１，ｃ２，…，ｃｎ｝表示ｎ个城市的集合，Ｌ＝｛ｌｉｊ｜ｃｉ，ｃｊ∈Ｃ｝是集合Ｃ中元素（城市）两两连接的集合，每一条边ｌｉｊ，都存在与之对应的权值ｄｉｊ，实际应用中ｄｉｊ可以表示距离、费用、时间、油量等。 ＴＳＰ的描述虽然简单， 解决起来却很困难。最简单思路是用穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但这样只能处理很小规模的问题。旅行商问题属于 ＮＰ－ｃｏｍｐｌｅｔｅ问题， 是ＮＰ（ｎｏｎ－ｄｅｔｅｒｍｉｎｉｓｔｉｃｐｏｌｙ－ｎｏｍｉｎａｌ）问题中最难的一类，不能在多项式时间内求解。如果有ｎ座城市，那么巡游路径共有（ｎ－１）！／２条，计算的时间和（ｎ－１）！成正比。当 城市数ｎ＝２０，巡回路径有１．２×１０１８种，ｎ＝１００， 巡回路径就有多达４．６×１０１５５种，而据估计宇宙中基本粒子数“仅仅只有”１０８７个。 尽管如此，随着算法研究的逐步深入和计算机技术飞速提高，对ＴＳＰ问题的研究不断取得进展。７０年来，被征服的ＴＳＰ规模从几十个城市增加到上万个城市。目前的最高记录是在２００４年５月，找到的巡游瑞典２４９７８个城镇的最优路径 （ｓｗ２４９７８）， 花费了８４．８个ＣＰＵ年。图１展示了ＴＳＰ的研究进展，最近的二三十年时间里，被攻克的ＴＳＰ规模高速增长，差不多是每十年增加一个数量级。照这样发展下去的话，再过２０年就能解决上百万个城市的ＴＳＰ，有专家甚至已经为此准备好了数据：全球１９０，４７１１个城市的坐标。当然，能不能达到这 个目标，有赖于未来计算技术的发展。 图１ＴＳＰ的发展 字母后面的数字表示城市数，“ｓｗ２４９７８”就是瑞典的 ２４９７８个城镇。 一、应用 旅行商问题具有重要的实际意义和工程背景。它一开始 是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域，下面举几个实例。 印制电路板转孔是ＴＳＰ应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为ＴＳＰ，孔相当于城市，孔到孔之间的移动时间就是距离。 为了避免大气干扰，使光学系统达到其衍射极限分辨率，欧美发达国家提出发展空间光干涉仪和综合孔径望远镜的计划。美国航空航天局有一个卫星群组成空间天文台（Ｓｐａｃｅ－ｂａｓｅｄＯｂｓｅｒｖａｔｏｒｉｅｓ）的计划， 用来探测宇宙起源和外星智慧生命。欧洲空间局也有类似的Ｄａｒｗｉｎ计划。对天体成像的时候，需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃料最少，可以用ＴＳＰ来求解。这里把天体看作城市，距离就是卫星移动消耗的燃料。 美国国家卫生协会在人类基因排序工作中用ＴＳＰ方法绘制放射性杂交图。把ＤＮＡ片断作为城市，它们之间的相似程度作为城市间的距离。法国科学家已经用这种办法作出了老鼠的放射性杂交图。 此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是，它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题，和ＴＳＰ同属ＮＰ－ｃｏｍｐｌｅｔｅ类，它们都是同等难度的，如果其中一个能用多项式确定性算法解决，那么其他所有的ＮＰ－ｃｏｍｐｌｅｔｅ类问题也能用多项式确定性算法解决。很多方法本来是从ＴＳＰ发展起来的，后来推广到其他ＮＰ－ｃｏｍｐｌｅｔｅ类问题上去。 二、ＴＳＰ求解方法 求解旅行商问题的方法可以分为两大类，一类是精确算法，目的是要找到理论最优解；另一类是近似算法，不强求最优解，只要找到“足够好”的满意解就可以了。 （一）精确算法 如前面所述，穷举法和全局搜索算法属于精确算法，但 旅行商问题概述 郭靖扬 （电子科技大学光电信息学院， 四川成都６１００５４） 【摘要】旅行商问题是组合优化的经典问题，应用广泛，而且长期以来被作为ＮＰ－ｃｏｍｐｌｅｔｅ问题的理想研究平台。文章介绍 了旅行商问题的基础知识、应用，以及常用的求解方法。 【关键词】旅行商问题；组合优化；ＮＰ－ｃｏｍｐｌｅｔｅ；ｋ－ｏｐｔ；智能算法【中图分类号】ＴＰ１８２【文献标识码】Ａ【文章编号】１００８－１１５１（２００６）０８－０２２９－０２大众科技 ＤＡＺＨＯＮＧＫＥＪＩ２００６年第８期（总第９４期） Ｎｏ．８，２００６ （ＣｕｍｕｌａｔｉｖｅｌｙＮｏ．９４） 【收稿日期】２００６－０３－１８【作者简介】郭靖扬（１９８０－），四川宜宾人，电子科技大学光电信息学院硕士研究生。 ２２９－－
货郎担问题或旅行商问题动态规划算法
#include { /*if(mincost <= cost[cur][i]+cost[i][start]) { continue; //其作用为结束本次循环。即跳出循环体中下面尚未执行的语句。区别于break } */ visit[i] = 1; //递归调用时，防止重复调用 int value = cost[cur][i] + imin(num-1, i); if(mincost > value) { mincost = value; } visit[i] = 0;//本次递归调用完毕，让下次递归调用 } } return mincost; } int main() { int i,j; // int k,e,w; n=4; int cc[4][4]={{0,10,15,20}, {5,0,9,10}, {6,13,0,12}, {8,8,9,0}}; for(i=0; i T S P问题算法分析集团企业公司编码：（LL3698-KKI1269-TM2483-LUI12689-ITT289- 算法第二次大作业 TSP问题算法分析 021251班 王昱（02125029） 一．问题描述 “TSP问题”常被称为“旅行商问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。 TSP问题在本实验中的具体化：从A城市出发，到达每个城市并且一个城市只允许访问一次，最后又回到原来的城市，寻找一条最短距离的路径。 二．算法描述 2.1分支界限法 2.1.1算法思想 分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 2.1.2算法设计说明 设求解最大化问题，解向量为X=(x1,…,xn)，xi的取值范围为Si，|Si|=ri。在使用分支限界搜索问题的解空间树时，先根据限界函数估算目标函数的界[down,up]，然后从根结点出发，扩展根结点的r1个孩子结点，从而构成分量x1的r1种可能的取值方式。 对这r1个孩子结点分别估算可能的目标函数bound(x1)，其含义：以该结点为根的子树所有可能的取值不大于bound(x1)，即： bound(x1)≥bound(x1,x2)≥…≥bound(x1,…,xn) 若某孩子结点的目标函数值超出目标函数的下界，则将该孩子结点丢弃；否则，将该孩子结点保存在待处理结点表PT中。 再取PT表中目标函数极大值结点作为扩展的根结点，重复上述。 直到一个叶子结点时的可行解X=(x1,…,xn)，及目标函数值 bound(x1,…,xn)。 2.2A*算法 算法思想 对于某一已到达的现行状态,如已到达图中的n节点,它是否可能成为最佳路径上的一点的估价,应由估价函数f(n)值来决定。假设g*(n)函数值表示从起始节点s到任意一个节点n的一条最佳路径上的实际耗散值。h*(n)函数值表示从任意节点n到目标节点ti的最佳路径的实际耗散值。其中ti是一个可能的目标节点。f*(n)函数值表示从起始s，通过某一指定的n到达目标节点ti的一条最佳路径的实际耗散值，并有 f*(n)=g*(n)+h*(n)。 2010年第5期(总第77期) 边疆经济与文化 THE BORDER ECONOMY AND CULT URE No 1512010General 1No 177 10 B I A N J I A N G J I N G J I Y U W EN HUA 【旅游经济】 求解旅行商问题的几种解法 高春涛 (哈尔滨商业大学基础科学学院,哈尔滨150028) 摘 要:旅行商问题(TSP )是一个典型的NP 完全问题,现在还没有找到有效的解法。目前比较热门的求解TSP 问题的方法主要有四种:神经网络算法;模拟退火算法;遗传算法;蚁群算法。 关键词:旅行商问题;组合优化;解法 中图分类号:F 592 文献标志码:A 文章编号:167225409(2010)0520010202 收稿日期:2010201222作者简介:高春涛(1973 ),女,黑龙江拜泉人,讲师,硕士,主要从事混沌神经网络研究。 一、引言 旅行商问题(Traveling Sales man Pr oble m ),是指给定n 个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径。由于在很多实际问题中,如印刷电路板的铅孔路线方案、连锁店的货物配送路线等问题经过简化处理,均可建模为旅行商问题,因而对旅行商问题求解方法的研究具有重要的应用价值。旅行商问题是运筹学中有代表性的组合优化问题,也是典型的NP 完全问题。虽然它陈述起来很简单,但求解却很困难,对于具有n 个城市的TSP 问题,其可能的路径数目为(n -1)!/2,至今尚未找到有效的求解方法,在理论上枚举法可以解决这一问题,但是当n 较大时,解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短,能满足实际问题精度要求的解,成为解决该问题的主要途径。 二、TSP 求解方法 求解旅行商问题的方法可以分为两大类,一类是精确算法,目的是要找到理论最优解;另一类是近似算法,其算法简单,计算量小,大多数情况下求得的满意解能满足要求。 1.Hopfield 神经网络算法 1982年,Hopfield 开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁,提出了Hopfield 反馈神经网络模型(HNN )。Hopfield 网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数 的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。尤其是通过对TSP 问题的成功求解,开辟了神经网络模型在计算机科学应用中的新天地,动态反馈网络从而受到广泛的研究和关注,被广泛应用于优化问题中,且已 设计出了专用的硬件电路。 [1] Hopfield 网络是一种非线性动力学模型,通过引入类似Lyapunov 函数的能量函数概念,把神经网络的拓扑结构(用连接矩阵表示)与所求问题(用目标函数描述)对应起来,转换成神经网络动力学系统的演化问题。因此,在用Hopfield 网络求解优化问题之前,必须将问题映射为相应的神经网络。对TSP 问题的求解,首先将问题的合法解映射为一个置换矩阵,并给出相应的能量函数,然后将满足置换矩阵要求的能量函数的最小值与问题的最优解相对应。 2.模拟退火算法 模拟退火算法最初的思想由Metr opolis 在1953 年提出,[2] Kirkpatrick 在1983年成功地将其应用在组合最优化问题中。模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特征在解空间中随机寻找目标函数的全局最优解,即在局部优解能 概率性地跳出并最终趋于全局最优。[1] 用固体退火模拟组合优化问题,将内能E 模拟为目标函数f,温度T 演化成控制参数t,即得到解组合优化问题的模拟退火算法:有初始解i 和控制参数初值t 开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t 值,算法终止时的当前解即为所得近似最优解。 摘要 本文分析比较了tsp问题的动态规划算法，分支界限法，近似等算法。分析了旅行商问题的时间度特点，针对启发式算法求解旅行商问题中存在的一些问题提出了改进算法。此算法将群体分为若干小子集，并用启发式交叉算子，以较好利用父代个体的有效信息，达到快速收敛的效果，实验表明此算法能提高寻优速度，解得质量也有所提高。 关键词：旅行商问题TSP Abstract this paper analyzed the time complexity of traveling salesman problem,then put forward some imprivement towards the genetic algorithm for solving this problen: divding the population into some small parent individual well.so it can quickly get into convergence, the experimental result indicates the impwoved algorithm can accelerate the apeed of finding solution and improve the precision. Keywords traveling salesman problem; genetic algorithm; subset; henristic crossover operator 目录 1、摘要--------------------------------------------------------------1 2、Abstract---------------------------------------------------------1 3、Tsp问题的提法------------------------------------------------2 4、回溯法求Tsp问题--------------------------------------------3 5、分支限界法求Tsp问题--------------------------------------7 6、近似算法求解Tsp问题-------------------------------------10 7、动态规划算法解Tsp问题----------------------------------12 用遗传算法解决旅行商问题 姓名：王晓梅 学号：1301281 班级：系统工程6班 一、问题背景 有一个销售员，要到n 个城市推销商品，他要找出一个包含所有n 个城市的具有最短路程的环路。 现在假设有10个城市，他们之间的距离如下。 { 0, 107, 241, 190, 124, 80, 316, 76, 152, 157}, { 107, 0, 148, 137, 88, 127, 336, 183, 134, 95}, { 241, 148, 0, 374, 171, 259, 509, 317, 217, 232}, { 190, 137, 374, 0, 202, 234, 222, 192, 248, 42}, { 124, 88, 171, 202, 0, 61, 392, 202, 46, 160}, { 80, 127, 259, 234, 61, 0, 386, 141, 72, 167}, { 316, 336, 509, 222, 392, 386, 0, 233, 438, 254}, { 76, 183, 317, 192, 202, 141, 233, 0, 213, 188}, { 152, 134, 217, 248, 46, 72, 438, 213, 0, 206}, { 157, 95, 232, 42, 160, 167, 254, 188, 206, 0} 将这10个城市分别编码为0,1,2,3,4,5,6,7,8,9。要求走完这10个城市，目标是使走的距离最短。 二、建立模型 ),...,1,(1) ,...,1,(1. .)(min 11 11n j j i n i j i t s j i n j ij n i ij ij n i n j ij x x d x =≠==≠=≠∑∑∑∑==== 三、设计算法 1、种群初始化 （1）一条染色体的初始化 10个城市分别对应0~9这十个数，每个染色体代表一个解决方法，即0~9这十个数的一种排序方式，可随机产生一个数，用取余的方法得到一个0~9的数，依次得到与前面不重复的十个数，构成一个染色体。 （2）种群的初始化 这里假设种群有100个染色体，也就是循环100次染色体的初始化可得到一个种群。 《算法设计与课程设计》 题目： TSP问题多种算法策略 班级：计算机技术14 学号： 姓名： 指导老师： 完成日期： 成绩： 旅行商问题的求解方法 摘要 旅行商问题（TSP 问题）时是指旅行家要旅行n 个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用动态规划法、贪心法、回溯法和深度优先搜索策略求解TSP 问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。 关键字：旅行商问题；动态规划法；贪心法；回溯法；深度优先搜索策略 1引言 旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP 的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP 的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法、回溯法和深度优先搜索策略。 2正文 2.1动态规划法 2.1.1动态规划法的设计思想 动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。 2.1.2 TSP 问题的动态规划函数 假设从顶点i 出发，令'(,)d i V 表示从顶点i 出发经过'V 中各个顶点一次且仅一次，最后回到出发点i 的最短路径长度，开始时，{}'V V i =-，于是，TSP 问 旅行商问题的几种求解算法比较 作者: (xxx学校) 摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回溯法分别来实现这个题目,并比较哪种更优越,来探索这个经典的NP(Nondeterministic Polynomial)难题. 关键词:旅行商问题求解算法比较 一.引言 旅行商问题(Travelling Salesman Problem),是计算机算法中的一个经典的难解问题,已归为NP一完备问题类.围绕着这个问题有各种不同的求解方法,已有的算法如动态规划法,分支限界法,回溯法等,这些精确式方法都是指数级(2n)[2,3]的,根本无法解决目前的实际问题,贪心法是近似方法,而启发式算法不能保证得到的解是最优解,甚至是较好的解释.所以我认为很多问题有快速的算法(多项式算法),但是,也有很多问题是无法用算法解决的.事实上,已经证明很多问题不可能在多项式时间内解决出来.但是,有很多很重要的问题他们的解虽然很难求解出来,但是他们的值却是很容易求可以算出来的.这种事实导致了NP完全问题.NP表示非确定的多项式,意思是这个问题的解可以用非确定性的算法"猜"出来.如果我们有一个可以猜想的机器,我们就可以在合理的时间内找到一个比较好的解.NP-完全问题学习的简单与否,取决于问题的难易程度.因为有很多问题,它们的输出极其复杂,比如说人们早就提出的一类被称作NP-难题的问题.这类问题不像NP-完全问题那样时间有限的.因为NP-问题由上述那些特征,所以很容易想到一些简单的算法――把全部的可行解算一遍.但是这种算法太慢了(通常时间复杂度为O(2^n))在很多情况下是不可行的.现在,没有知道有没有那种精确的算法存在.证明存在或者不存在那种精确的算法这个沉重的担子就留给了新的研究者了,或许你就是成功者. 本篇论文就是想用几种方法来就一个销售商从几个城市中的某一城市出发,不重复地走完其余N—1个城市,并回到原出发点,在所有可能的路径中求出路径长度最短的一条,比较是否是最优化,哪种结果好. 二.求解策略及优化算法 动态规划法解TSP问题 我们将具有明显的阶段划分和状态转移方程的规划称为动态规划,这种动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析.在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦.一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决.所以动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的,相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略. 旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解.若存在若干个取最优值的解的话,它只取其中的一个.在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算. 关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k 个城市的可能集合,动态规划的递推关系为: 《算法设计与分析》实验报告一 学号：姓名： 日期：20161230 得分： 一、实验内容： TSP问题 二、所用算法的基本思想及复杂度分析： 1、蛮力法 1）基本思想 借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点 到自身节点的距离为无穷大。在第一行找到最小项a[1][j]，从而跳转到 第j行，再找到最小值a[j][k]，再到第k行进行查找。。。然后构造各行允 许数组row[n]={1,1…1}，各列允许数组colable[n]={0,1,1….1}，其中1 表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已经 被访问。如果改行或该列不允许访问，跳过该点访问下一节点。程序再 发问最后一个节点前，所访问的行中至少有1个允许访问的节点，依次 访问这些节点找到最小的即可；在访问最后一个节点后，再次访问，会 返回k=0，即实现访问源节点，得出一条简单回路。 2）复杂度分析 基本语句是访问下一个行列中最小的点，主要操作是求平方，假设有n 个点，则计算的次数为n^2-n。T(n)=n*(n-1)=O(n^2)。 2、动态规划法 1）基本思想 假设从顶点s出发，令d(i, V’)表示从顶点i出发经过V’(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。 推导：(分情况来讨论) ①当V’为空集，那么d(i, V’)，表示从i不经过任何点就回到s了，如上图的城市3->城 市0(0为起点城市)。此时d(i, V’)=Cis(就是城市i 到城市s 的距离)、 ②如果V’不为空，那么就是对子问题的最优求解。你必须在V’这个城市集合中，尝试每一 个，并求出最优解。 d(i, V’)=min{Cik +d(k, V’-{k})} 注：Cik表示你选择的城市和城市i的距离，d(k, V’-{k})是一个子问题。 综上所述，TSP问题的动态规划方程就出来了： 2）复杂度分析 和蛮力法相比，动态规划求解tsp问题，把原来时间复杂性O（n！）的 排列转化为组合问题，从而降低了时间复杂度，但仍需要指数时间。 3、回溯法 1）基本思想 确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以 深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成 为当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点 即成为新的活结点，并为当前扩展结点。如果在当前的扩展结点处不 能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回 移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩 旅行商问题的求解方法 摘要 旅行商问题（TSP问题）时是指旅行家要旅行n个城市然后回到出发城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。本文主要介绍用蛮力法、动态规划法、贪心法和分支限界法求解TSP问题，其中重点讨论动态规划法和贪心法，并给出相应求解程序。 关键字：旅行商问题；动态规划法；贪心法；分支限界法 1引言 旅行商问题(TSP)是组合优化问题中典型的NP-完全问题，是许多领域内复杂工程优化问题的抽象形式。研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。关于TSP的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法。归纳起来，目前主要算法可分成传统优化算法和现代优化算法。在传统优化算法中又可分为：最优解算法和近似方法。最优解算法虽然可以得到精确解，但计算时间无法忍受，因此就产生了各种近似方法，这些近似算法虽然可以较快地求得接近最优解的可行解，但其接近最优解的程度不能令人满意。但限于所学知识和时间限制，本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法，并对蛮力法做简单介绍，用以比较。 2正文 2.1蛮力法 2.1.1蛮力法的设计思想 蛮力法所依赖的基本技术是扫描技术，即采用一定的策略将待求解问题的所有元素一次处理一次，从而找出问题的解。一次处理所有元素的是蛮力法的关键，为了避免陷入重复试探，应保证处理过的元素不再被处理。在基本的数据结构中，一次处理每个元素的方法是遍历。 2.1.2算法讨论 用蛮力法解决TSP问题，可以找出所有可能的旅行路线，从中选取路径长度最短的简单回路。如对于图1，我们求解过程如下： （1）路径：1->2->3->4->1；路径长度：18； （2）路径：1->2->4->3->1；路径长度：11； （3）路径：1->3->2->4->1；路径长度：23； （4）路径：1->3->4->2->1；路径长度：11；TSP问题算法分析
求解旅行商问题的几种解法
Tsp问题的几种算法的分析
用遗传算法解决旅行商问题
算法报告-旅行商问题模板讲解
旅行商问题的几种求解算法比较
TSP问题的解决方案
算法论文：旅行商问题的求解方法(动态规划法和贪心法)