文档介绍：该【侯祥林旅行商问题的多点优化贪心算法与程序设计 】是由【guoxiachuanyue007】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【侯祥林旅行商问题的多点优化贪心算法与程序设计 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。旅行商问题的多点优化贪心算法与程序设计
侯祥林,费烨,韦金秀沈阳建筑大学,110168
摘要:针对经典旅行商问题,从贪心算法基本思想出发,建立了分别以所有节点为起点,以总路程最小值为最优路径的一种多点贪心算法。应用VisualBasic语言编制优化路径求解程序。并针对30个节点和50个节点的算例分析。该算法具有简单实用性,能够对具体问题实现快速计算,为工程问题分析提供基础。
关键词:旅行商问题,贪心算法,多点贪心算法,程序设计
旅行商问题(TravelingSalemanProblem,TSP)属于NP难题,也称为货郎担问题,是由爱尔兰数学家SirWilliamRowanHamilton和英国数学家ThomasPenyngtonKirkman在19世纪提出的数学问题。它是指:假设有一个旅行商人要拜访n个城市,需要选择一条最优路径,每个城市只能拜访一次,而且最后要回到原来出发的城市。
如何确定最短路线。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间,搜索空间是n个点的所有排列的集合,大小为n!。路径的选择目标是要求得的路径路程为所有路径之中的最小值。由于该问题的描述简单,而其实际模型在管道铺设,线路选择等优化问题中又有着广泛的应用,故长期以来一直吸引着国内外许多研究人员进行研究,他们尝试着用各种算法来求解TSP问题。归纳起来有:近似解法、局部搜索法、神经网络、遗传算法、克隆算法、模拟退火算法、混合遗传算法等[1~10。]
在所有的算法中,贪心算法是容易理解的好算法,也可也达到问题的一个次优解。但是古典的贪心算法存在的问题的最后返回出发点可能会出现一个较大的距离。本文将在古典的贪心算法基础上,通过改进获得一个称为多点贪心算法,并给出算例分析。
设共有n点,以下称为节点,其节点号码分别为1,2,…,n。贪心算法依据下面过程:(1)从1号节点出发,分别计算1号节点余下的n-1个节点距离,与1号节点的最短距离点称为2',最小距离为d;(2)计算2'号节点与余下的n-2个节点距离,与2'号节点的最短距离点称为3',其最小
1,2'
距离为d;…;(3)计算j'号节点与余下的n-j个节点距离,与j'号节点的最短距离点称为
2',3'
(j+1)',其最小距离为d;…;(4)最后,计算(n-1)'号节点与余下的n'号节点距离,
j',(j+1)'
d。总路程:L=d+^1d+d。上面的算法,可能会导致最后返回出发点的距离
(n-1)'j',n'1,2'j',(j+1)'n',1'
j=2
很大。
为了改善贪心算法直接计算的不足,可以考虑出发节点不同情况;两个步骤:(1)确定从n个
基金项目:辽宁省自然科学基金资助项目(20072011)
2
计算第i点与余下所有点距离
比较出第i点与余下所有点的最小距离,并获得第i+1点;
文件输出,行走路线
绘制行走路线
计算从kk点为开始节点的
最小贪心路程
文件输出路程长度
节点中的每个节点出发,依据贪心算法确定总路程L=d+芒d+d,i=1,2,…,n。(2)比ii2j,(j+iyn,i
j二2
较L,i=1,2,…,n,获得最短路程:L=minL。(3)按L,给出行走路线;无论从哪个节点1min1<i<n1min
出发,都将按此行走路线方向行走;
3•算法过程的VisualBasic程序描述
1)输入节点数量与坐标;
n,xx(
kk=1
[),yy(i=,i…2,n
标记目前节点,设置kk点为开始节点;
Fori=1ton
x(i)=xx(i),y(i)=yy(i)
Nexti
temx二x(1),temy二y(1)
x(1)=x(kk),y(1)=y(kk)
x(kk)二temx,y(kk)二temy
确定以kk为开始节点的贪婪路线:包括计算、比较每步最小距离,计算路线总距离Print#1,kk
Fori=1ton-1
Forj=i+1ton
d(i,j)=(((x(i)-x(j))人2+(y(i)-y(j))人2))
Nextj
Forj=i+2Ton
Ifd(i,i+1)>d(i,j)Then
temx=x(i+1):temy=y(i+1):
x(i+1)=x(j):y(i+1)=y(j)
x(j)=temx:y(j)=temy
temd=d(i,i+1):d(i,i+1)=d(i,j)
d(i,j)=temd:Curj=j
EndIf
Nextj
Print#1,"-->",j
(x(i),y(i))-(x(i+1),y(i+1)),RGB(255,0,0)Nexti
d(n,1)=(((x(n)-x(1))A2+(y(n)-y(1))A2))(x(n),y(n))-(x(1),y(1)),RGB(0,255,0)dd(kk)=0
Fori=1ton-1
dd(kk)=dd(kk)+d(i,i+1)
Nextidd(kk)=dd(kk)+d(n,1)
Print#1,dd(kk)
当kk<n时,kkukk+1转到(2)
当kk=n时,转到(5)
比较多点贪心算法最优路程,获得最优出发点opt_kk
6
Forkk=2Ton
Ifdd⑴>dd(kk)Thentem=dd(1):dd(1)=dd(kk)dd(kk)=tem
opt_kk=kk
EndIf
Nextkk
算例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
11
21
2
12
22
3
13
23
4
14
24
5
15
25
6
16
26
7
17
27
8
18
28
9
19
29
10
20
30
多点贪婪算法的最短路程为L=。图绘制出了该情况的行走路线。起点为15号节点。其行走顺序为:
4
15_14-8_7_11->9_3_18_19_20-10-21-1-2-4-13_12-17_16_22-3_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
32
14
42
41
27
56
37
40
62
63
2
32
39
15
17
33
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
37
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
5
表4算例1不同起点贪心算法路程列表
序号
路程
序号
路程
序号
路程
序号
路程
1
14
27
40
2
15
28
41
3
16
29
42
4
17
30
43
5
18
31
44
6
19
32
45
7
20
33
46
8
21
34
47
9
22
35
48
10
23
36
49
11
24
37
50
12
25
38
13
26
39
多点贪婪算法的最短路程为L=。图绘制出了该情况的行走路线。起点为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行走路线
6
本文在贪心算法的基础上,建立了多点贪心算法。建立了从所有节点出发点的贪心算法获得路程,进行比较获得更优路程与行走路经的思想。同时,应用VB环境开发所研究算法的计算程序。给出了30个节点和50个节点的算例分析与可视化行走路线。
可见,与贪心算法相比,结果获得优化。而与复杂算法对比,该算法简单,容易实现,同时可以获得较好的结果,具有一定的实用性。
参考文献
,[M].北京:清华大学出版社,1998:117-121.
,[M].DordrechtHardbound:KluwerAcademicPublishers,2002.
[J].北京理工大学学报,1995,15(1):97-99.
4•[J].软件学报,2003,14(1):35-42.
朱文兴,[J].计算机学报,2002,25(7):701-707.
[J].西南交通大学学报,1996,31(5):550-554.
陈沐天,[J].计算机工程与科学,1998,20(1):22-27.
8•[M].北京:清华大学出版社,2001.
李敏,吴浪,张开碧求解旅行商问题的几种算法的比较研究[J].重庆邮电大学学报,2008(5).
[J].计算机工程与科学,2008,30(2):72~74,155.
Multi-pointOptimizeGreedyAlgorithmandProgramDesignAboutTSP
HouXiaing-lin,Feiye,WeiJin-xiu
ShenyangJianzhuUniversity,110168
Abstract:Tosolvewelltheclassicaltravelingsalesmanproblem(TSP),basedontheideaofgreedyalgorithm,akindofmulti-,allnodescanbefirstlymadeasstartingpointtosearchpathbygreedyalgorithm,,andprovideconditionfortheanalysisofengineeringproblems.
Keyboard:travelingsalesmanproblem(TSP),greedyalgorithm,multi-pointoptimizegreedyalgorithm,programdesign
7