TSP问题近似算法比较研究

《TSP问题近似算法比较研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湖南理工学院毕业论文学号14133900902毕业论文题目:TSP问题近似算法比较研究作者刘珍娟届别2017届院别信息与通信工程学院专业信息工程指导教师潘理职称副教授完成时间2017年5月10日-III--湖南理工学院毕业论文摘要TravelingSalesmanProblem，简称TSP，TSP是一个NP-难问题，在组合优化问题中很经典，用语言介绍它很容易，但处理起来却非常难，一直以来它吸引了很多学者对其进行研究。它的相关知识在实际生活中的使用很广。TSP主要内容如下：假设有个旅行商要去N个城市旅行，他为了减少费用和时间，得考虑设计一条只经过每

2、个城市一次，最终回到出发的城市的全程总路径最短的线路。这个问题看似不难，但随着城市数目的增加，可考虑的线路方案数目呈指数型增长，为了找出一条路径最短的线路需要用大量的时间去计算。例如用回溯法去探索出最优路径的时间就是我们无法忍受。因此很多学者开始研究用近似算法找出一条较优的线路。最常使用的而其思想也较简单的近似算法包括：最近邻法、贪心法等。这些方法有各自的特点，算法好坏在不同情况对比下有所不同。因此需要采用多组测试数据在matlab平台上进行测试，对以上常用的两种近似算法进行分析、比较研究。关键字：TSP问题、最近邻法、贪心法、回溯法、matla

3、b-II--湖南理工学院毕业论文AbstractTravelingSalesmanProblemreferredtoasTSP,it’saNP-hardproblem,alsoisaveryclassicproblemincombinatorialoptimization,Weintroduceiteasily,butitisverydifficultifweplantohandleit.Sofarithasattractedmanyscholarstostudyit.Itsrelatedknowledgeiswidelyusedinrealli

4、fe.Themaincontentsareasfollows:TSPsaysatravelingsalesmanwhoplanstogotoNcitytravel,heinordertoreducethecostandtimeneeddesigntheshortestroute.Thisroutegothroutheverycityonlyonce,finallyreturnedtothestartingcity.Thisproblemseemseasy,butwiththenumberofcitiesincreasing,thenumberof

5、linescanbeconsideredwillbeexponentialgrowth,inordertofindtheshortestrouth,whichneedtospendalotoftimetocalculate.Forexample,thetimeweuseTheBackfittingAlgorithmtoexploretheoptimalroutewhichwecannotstand.Therefore,manyscholarsbegantostudytheuseofapproximatealgorithmtofindabetter

6、line.Theapproximationalgorithmswhoseideasarerelativelysimpleandmostcommonlyused,theyareincluding:nearestneighbormethod,greedymethod,etc..Thesemethodshavetheirowncharacteristics,thealgorithmisdifferentindifferentsituations.Therefore,itisnecessarytoanalyzeandcomparethetwoalgori

7、thmsbyusemultiplesetsoftestdatatotestontheMATLABplatform,.Keywords:TSP,Nearestneighbormethod,Greedymethod,Backtrackingmethod,matlab-II--湖南理工学院毕业论文目录摘要IAbstractII第1章绪论11.1研究背景11.2TSP问题11.3研究TSP问题近似算法的意义与目的21.4本文工作2第二章TSP问题与近似算法32.1TSP问题数学描述32.2近似算法3§2.2.1构建型算法4§2.2.2局部搜索方法4第三章

8、最近邻法63.1算法流程63.2算法实现8§3.2.1数据结构定义8§3.2.2在MATLAB上的实现过程83.3实验结果10第四章贪心