用最小生成树解决TSP问题

湖北师范学院学报(自然科学版)

JournalofHubeiNormalUniversity(NaturalScience)

Vol124No14,2004

用最小生成树解决TSP问题

姚建华,杨成涛

(济南94534部队,山东济南　250002)

摘要:旅行商问题(TravelingSalesmanProblem,TSP问题)是组合优化领域中研究最多的问题之一,是一个经典的NP难题,也是目前优化领域里的研究热点。目前解决旅行商问题有诸多算法,神经网络、遗传算法、免疫算法等,在各种解决旅行商问题的算法中,还是存在很多问题。本文用最小化生成树来求解旅行商问题。在对题目要求进行深入分析的基础上,对原有算法进行了多方面改进,并用C语言进行了实现。采用选取排除最长路径顶点的方法降低时间复杂度、采用比较顶点次序的方法提高算法准确性、通过自动产生顶点坐标降低输入复杂性和测试的准确性,实验结果表明该算法可以取得较好的效果。关键词:TSP;最小生成树;最短路径;组合优化

中图分类号:TP301.6,TP312　　文献标识码:A　　文章编号:100922714(2004)0420052205　　旅行商问题(TravelingSalesmanProblem,TSP问题)就是一个销售商从n个城市中的某一城市出发,不重复地走完其余n-1个城市并回到原出发点,在所有可能的路径中求出路径长度最短的一条,是组合优化领域中研究最多的问题之一。从50年代中起,出版了大量关于本问题的文献。Lawler编辑的书对到当时为止的所有主要研究成果作了全面深入的综述。

对于求解旅行商问题,有许多方法和思路,目前最流行的是神经网络算法与遗传算法,在本次设计中,应用最小生成树的解题思路,来解决旅行商问题。本文中包括了对旅行商问题和最小生成树解题思路的论述,给出了解决旅行商问题的算法设计。

由题目要求可知,对于旅行商问题,城市的数目是根据用户的需求而改变的,而对于所确定数目的n个城市来说,每两个城市之间都有相互连通的路径,且路径的长度是不尽相同的。

对于所求的路径,要求销售商可从n个城市中的任意一个城市Vi出发,经过其余所有的n-1个城市,除出发点Vi外,其余n-1个城市在路径中不能重复出发,即除出发点外,其余所有城市必须经过且仅经过一次。由于每两个城市间的路径长度不完全相同,因此每条符合上述要求的路径其长度也不同,在其中选择一条路径长度最短的就为TSP问题所求的最短路径。

1　算法设计

　　对于N个城市的TSP问题,其城市的数目应为N。若N个城市中,每两个城市之间都有连通的路径,其连通路径数目应为n3(n-1)/2。而对于含有个顶点无向连接图来说,其完全图的边数也为n3(n-1)/2,因此可以用含有n个顶点的完全连通无向图来形象的描绘TSP问题的已知条件,而此完全连通无向图中每条边上的权值,可以表示TSP问题中每两个顶点之间的路径长度。因此在其后的设计中,使用带权的完全无向连通图来分析TSP问题的求解过程。1.1　最小生成树

[收稿日期]　2004—06—10

),男,湖北武汉人,硕士生,讲师,中校军衔。[作者简介]　姚建华(1963—　

・52・

一棵生成树是连通图的一个极小连通子图,它含有连通图中的全部n个顶点,但只有足以构成一棵树的n-1条边,而一棵生成树的代价为此树上所有边的权值之和,一个连通图的最小生成树,是此图所有生成树中中代价和最小的一棵生成树.它与TSP问题所求路径有许多相同之处,它们都必须经过所有的n个顶点,n个顶点之间都是相互连通(但在TSP问题中,路径为回路),并且路径长度为最短。因此,对于TSP问题的求解,可以借助于最小生成树的求解方法。1.2　最小生成树求解

在个顶点的完全连通图中含有n3(n-1)/2条边,而要在这n3(n-1)/2条边中选择n-1条边,使其成为一棵代价和最小的生成树,这一过程为求解最小生成树,这一过程为求解最小生成树,构造最小生成树可以有多种,其中一种为普里姆(Prim)算法。

普里姆算法的描述为:在含有n(n>1)个顶点的完全连通无向图中,任意选择一个顶点Vi作为起始点,在与顶点Vi相关联的n-1条边中,选择一条权值最小的边ei,此边可连接Vi及图中另一个顶点Vj,然后在与Vi或Vj相关联除ei以外的所有边中,选择权值最小的边ej,ej又可连接另外一个顶点(边的选则还要保证树中没有环的产生)。依此求顶点的方法,依次求出所有的可连接n个顶点的n-1条边,因为在此生成树中的每一条边均为不会生成环的,且权值最小的连接顶点的边,因此这棵生成树为此含有n(n>1)个顶点的完全连通无向图的最小生成树。其普里姆生成树的过程与最小生成树过程如图1:

图1　普里姆生成树与最小生成树过程

1.3　求解TSP的最小生成树算法

TSP问题求解的路径与最小生成树虽然有许多相同之处,但它们还有不同之处。首先,对于TSP问题它的求解路径应为一条回路,而在树中是不存在回路的。其次,最小生成树是一棵树,当它

有分支点时,要从其中一个顶点访问其余顶点时,在访问过程中,一定会出现重复访问的定点,分支的数目越多重复访问的顶点就会越多,而在TSP问题的求解路径中时不允许有重复顶点出现的。

在n个顶点中选择一个顶点Vi作为出发点,在Vi所连接的n-1条边中选择权值最小的一条边ei,ei连接Vi和另一个顶点Vj,若要Vj在最短路径中只出现一次,则在以后选择连接顶点的边时,不应再选择可连接Vj的边,并且在路径中不应该出现任何一个分支点,若要实现如此要求,可在选择下一条边时以Vj作为出发点,选择Vj所连接的除了ei以外的一条权值最小的边ej,作为路径中的下一条边。如此循环查找,便可以找到一条由Vi作为出发点,经过所有n个顶点的一条最短路径。

TSP问题中,要求所求的最短路径中要从出发点经过且仅经过所有顶点后,再回到原出发点,即

其最短路径应为一条回路。按照上段所求出的路径,包括出发点,每个顶点都只经过了一次,要回到出发点只需要将最后走过的一个顶点与出发点之间的边也加入到路径中即可形成一条回路。但是由于不能够保证由最后一个顶点到出发点的这条边的权值,为从最后一点出发的所有边的权值中最小的,因此不能保证这条回路的路径长度是最短的,由此便不符合TSP问题的求解路径要求。要解决此问题,可以将从n个顶点中每个顶点出发的,由以上方法求解的n条回路路径求出,并统计出这n条回路的路径长度,比较这n个回路路径长度,其中值最小的一条便为TSP问题所求的最短回路路

・53・

径。

2　算法实现

2.1　输入设计

需要进行输入的内容有:城市的数目、以及各个城市的基本信息(基本信息应输入各个城市的坐标,在算法中通过坐标来求出每两个城市之间的距离,在输出时并通过坐标来区分各个城市)。

城市的数目用一个变量max可以表示。

对于各个城市的基本信息,因为有max个城市,因此需要用一个数组来存储,数组中各个元素的类型相同,在这个算法设计中用城市的坐标来区分各个城市,因此需要自定义一个数组array2,数组长度为max。arrar2类型定义如下:　　　　struct　　　　{intx;//用来存储横坐标　　　　inty;//用来存储纵坐标　　　　}array2[m]

在数据结构中,图的存储方式由多种。对于完全图来说,一般使用邻接矩阵对其进行存储。邻接矩阵用二维数组存储图中各条边的权值,若顶点之间没有边,其相应位置上存储数据0。如图1的邻接矩阵存储形式如下:

V1V2V3V4V5V6V10V26V31V45V50V60

605030

150564

505002

036006

004260对于完全图,它的邻接矩阵除对角线外,其余位置上的元素数据均不为0,因此采用二维数组来存储TSP问题中的各个顶点之间的路径长度,需设立一个Array1[max][max]的数组,数组中的值需要通过输入的坐标值求得。2.2　TSP路径查找设计

通过对查找方法的分析,可以采用如下方法进行最短路径的查找。

设置一个二维数组array3[max][max+2]用来存储查找的最短路径以及路径的长度,其中每一行用来存储一条路径和此条路径的路径长度。例如:array3[i][0]和array3[i][max]用来存储从第i个顶点出发的这条路径的起始点和始点,由于TSP路径是一条闭合的回路,因此array3[i][0]和ar2ray3[i][max]中的顶点应该是相同的,在array3[i][max+1]中存储的是这条闭合回路的路径长度。

对于路径中的每一个顶点(除起始点外)只能够被选一次,要判断某个顶点有没有被选过,就需要对其设置一个标志位,当标志位为0时,说明该顶点没有被选择过可以对其进行操作,但是当标志位为1时,此顶点就不能再作为可被选择的顶点对其进行其他的操作。每个顶点都需要设置标志位,因此设置一个一维数组a2[max],为每个顶点设置一个标志位。此一维数组a2[max]的初始状态应为0。由于每条路径的查找都需要用到标志位,所以在每次查找新路径以前都要对数组进行初始化。

每条路径的具体查找方法为:首先选取一个顶点作为此条路径的起始点和终点,分别将它填入到array3[i][0]和array3[i][max]中,将标志位数组a2中其相应位置上置为1。然后在存储顶点之间路径长度的数组array1中的第i行上,查找出第一个距离不为0的顶点,记录下此顶点的下标j与它的路径值a,继续在第i行中进行查找路径值小于a并且大于0还要它在a2中相应位置上值为0的顶・54・

点,此顶点便为要选择的第i条路径上的下一个顶点,将此顶点的下标p和i与p之间的距离记录下来,将距离长度累加到路径长度和sum中(sum的初始值为0),并将其填入到array3[i][k](k用来表示此顶点为路径上的第几个顶点),同时将a2[p]置为1。再以p为起始点,在array1[p]行中重复上述操作,便可以求出一条闭合的回路。此时,路径长度和sum并不包含最后回路的距离,将array3[i][max-1]到array3[i][max]之间的值求出,累加到sum中,最后将sum存储到array3[i][max+1]中,

此时一条闭合的回路路径就全部求出。

照此上述操作一共求出条路径,分别存储在到中,对到中每条路径为的值进行比较,求出路径长度最小的一条路径,记录下它的下标,这样查找工作就完成了。

3　算法改进

　　本文从以下几个方面对算法进行了改进。3.1　降低时间复杂度

对于含有n个城市的TSP问题,按照上述的路径查找方法,每条路径的查找时间复杂度为n2,一共需要进行n条路径的查找,在选择最短路径时,又要对n条路径进行比较,这样一来,在查找操作中的算法时间复杂度就为n4。当n值不大时,此算法可以方便的求出最短路径,但是如果n值变大,此算法就会呈现出许多弊端,因此需要对算法的查找路径过程进行改进。

改进方法如下:

在n个顶点中随机选取一个顶点Vi作为第一条路径的起始点,按照上述每条路径的查找算法,便会找到一条以Vi为出发点的最短回路路径Si,此路径的终点(除Vi)为Vj。如果将Vj作为下一条查找路径的起始点,便会找到一条以Vj为出发点的最短回路路径Sj。当Si与Sj的路径长度相同,并且当Si的出发点Vi在Sj中出发点为Vj的下一个顶点时,Si便满足了此算法中求解TSP问题所要查找的最短回路路径的条件,Si也就为此TSP问题的最短回路路径。当查找到此样的路径时,就无需再进行下面的路径查找和路径比较,这样就可以大大的节省算法的时间复杂度。3.2　降低输入复杂性根据输入设计,用户需要将城市的数目和各个城市的坐标录入到程序中,对于此操作,当城市的数目不大时,用户的录入工作量不大,但是当城市的数目变大时,录入工作量会大大增加,而且还容易出现错录或漏录的情况,因此在源程序中对此进行了改进。

将产生顶点坐标的工作改为机内工作,减少用户的录入工作。用户只要输入城市的数目,程序会自动产生各个城市的坐标,并将坐标输出在屏幕上,当用户满意后,可继续进行下面的操作。

使用时间函数来设置随机坐标序列的起点,使得每个时刻产生的随机坐标不相同,以便将每个顶点赋予不同的坐标值,用来区分不同的城市顶点。

4　结束语

　　本文利用最小生成树解决了TSP问题,在对题目和算法进行分析的基础上,设计了基于最小生成树的算法实现,并从降低时间复杂度、提高算法准确性、降低输入复杂性三个方面对算法进行了改进,取得了较好的效果。参考文献:

[1]谭浩强.C语言程序设计(第二版)[M].清华大学出版社,1998.[2]张基温.C/C++程序设计教程[M].高等教育出版社,1997.[3]吴伟民.数据结构(C语言版)[M].清华大学出版社,2000.

[4]靳蕃.神经网络与神经计算机(原理与应用)[M].西南交通大学出版社,1999.

・55・

ResearchontheTSPproblemwithminimumspanningtree

YAOJian2hua,YANGCheng2tao

(PLA94534,Jinan　250002,China)

Abstract:TravelingSale-manProblem(TSP)meansasale-manstartsfromacityamongncity,andpassesbyeverycityandreturntheoriginnon-repeatedly.Fromalltheroutestheshortestisselectedandisadoptedasthesolve.TSPisthemostimportantprobleminthecombinedoptimizationarea,andaNP-hardproblem.Ithasalreadyattractedmanyresearchersfromallareas,includingmathematics,operationalresearch,physics,biology,andartificialintelligence,atthesametime,itisahotspotinthecurrentoptimizationarea.Atpresent,therearelotsofalgorithmstosolveTSP,suchasneuralnetworks,geneticalgorithm,immunealgorithm.Amongallthecurrentalgorithms,lotsofproblemsstilldisturbtheresearchers.ThearticletriestoresolvetheTSPwiththeminimumspanningtree.Basedonthedeepanalysisofthesubject,someimprovementispresentedinthearticle,andatlast,itisrealizedbyClanguage.Todecreasethetimecomplexity,increasetheaccuracyanddecreasetheinputtingdifference,someskillsareadopted.Andtheresearchresultsshowsthatthealgorithminthearticlecanacquirebetterresults.

Keywords:TSP;minimumspanningtree;combinationoptimization

(上接第42页)

3)多菌灵1000倍稀释液在杀灭木霉、黑曲霉的同时,对青霉菌丝的生长也有强烈的抑制作用,

而对食用菌(华平97)菌丝的生长没有影响,所以,多菌灵可作为平菇生料栽培拌料的消毒剂使用。

4)克霉灵作500倍～1000倍稀释能抑制霉菌生长,而对食用菌菌丝的生长没有影响,所以在利用棉子皮生料栽培平菇时,应使用500倍～1000倍稀释液作防霉剂拌料来进行食用菌栽培。参考文献:

[1]向敏.发展有机食用菌产业应对国际贸易技术壁垒[J].中国食用菌,2003,(2):3～6.[2]张松.食用菌学[M].广州:华南理工大学出版社,2000.

[3]梁文平,张研,刘娇.食用菌杀虫剂药效的试验研究[J].食用菌,2004,(2):39～40.[4]杨新美.食用菌研究法[M].北京:中国农业出版社,1998.

Thestudyofmouldproofeffectsofseveraldisinfectantsinthemushroomculture

DONGChang2jin

(DepartmentofBiology,HubeiNormalUniversity,Huangshi　435002,China)

Abstract:Mouldproofeffectsofseveraldisinfectantsofmushroomwerestudiedonthecultureplates.Thetrialresultsshowedthatthemouldproofeffectsofformaldehydewerethebest(themouldproofeffectsof1/50～1/1000dilutedsolutionsofformaldehydewere100%),theeffectsofcarbendazimwasthenext(1/300～1/2000dilutedsolutionsofcarbendazimhadgoodmouldproofeffects).Inthemushroomculture,formaldehydewasusuallyusedasdisinfectantfortheairintheroom,andcarbendazimwasusuallyusedasantisepticintherawmaterialculture.Keywords:mushroom;mould;disinfectant;effect

・56・