资源描述：
《求解tsp问题算法综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、CN4321258/TP计算机工程与科学2008年第30卷第2期ISSN10072130XCOMPUTERENGINEERING&SCIENCEVol130,No12,2008文章编号:10072130X(2008)02200722033求解TSP问题算法综述ASurveyofSolvingtheTravelingSalesmanProblem王剑文,戴光明,谢柏桥,张全元WANGJian2wen,DAIGuang2ming,XIEBai2qiao,ZHANGQuan2yuan(中国地质大学(武汉)计算机学院,湖北武汉430
2、074)(SchoolofComputerScience,ChinaUniversityofGeosciences,Wuhan430073,China)摘要:TSP问题(旅行商问题)是一个典型的组合优化问题,具有重要实际应用价值。对于大规模TSP问题,至今尚未找到非常有效的求解方法。为此,本文讨论了传统的确定性算法和流行的智能算法,并指出各种方法的优缺点,提出了未来求解TSP问题的发展趋势。Abstract:Thetravelingsalesmanproblem(TSP)isatypicalcombinationoptimi
3、zationproblem,andpossessesapracticalapplicationvalue.However,thereisnoeffectivecorrespondingsolutiontoittoday.So,inthispaper,thetraditionallyaf2firmativemethodsandpopularmeta2heuristicmethodsarediscussed.Theadvantagesanddisadvantagesofeachmethodarediscussed.Thefutu
4、reresearchdirectionoftheTSPproblemisalsogiven.关键词:旅行商问题;动态规划法;分枝限界法;遗传算法;郭涛算法Keywords:travelingsalesmanproblem;dynamicprogram;brandandbound;geneticalgorithm;GouTaoalgorithm中图分类号:TP301.6文献标识码:A1引言2TSP问题的数学模型及其分类[2]旅行商问题(TravelingSalesmanProblem,简称TSP)TSP问题的数学模型如下:是一
5、个易于描述但难于解决的著名难题之一。TSP问题对于城市V={v1,v2,⋯,vn}的一个访问顺序为T=可描述为:已知n个城市各城市间的距离,某一旅行商从某(t1,t2,⋯,tn),其中ti=V(i=1,⋯,n),而且tn+1=t1,则问个城市出发访问每个城市一次且仅一次,最后回到出发城n题为求min∑dtt,其中Ω为这n个城市不重复排列的所ii+1T∈Ωi=1市,怎样安排才使其所走路线最短。有可能的回路。现实生活中有很多问题可以归结为旅行商问题,比如通常,TSP问题可以按照其距离矩阵分为两大类,即对邮路问题、装配线上的螺帽问
6、题和产品的生产安排问题[1]称性TSP问题和非对称性TSP问题。非对称性TSP问题等。TSP问题在电路板钻孔进度的安排、基因测序和机难于求解,本文主要针对常见的对称性TSP问题进行阐述。器人控制等方面有着重要的应用。因此,TSP问题的求解具有重要的理论意义和实际意义。3求解TSP问题的常用算法几十年前就已找到的一些指数级算法虽然能精确地求解TSP问题,但随着问题规模的变大,这些算法完全失效3.1传统的确定性算法(组合爆炸)。近似算法或启发式算法尽管不能精确求解,但能够把误差控制在可以容忍的范围内并且能够快速地得3.1.1动态
7、规划法到答案。本文将介绍一些传统的和现代流行的智能求解动态规划法DM(DynamicProgramming,简称DM)是TSP问题的方法。美国数学家BellmanRE等人在20世纪50年代初在研究3收稿日期:2007208201;修订日期:2007209219基金项目:湖北省自然科学基金资助项目(2003ABA045)作者简介:王剑文(19802),男,湖南衡南人,硕士生,研究方向为算法设计和多目标优化;戴光明,博士,教授,研究方向为算法几何、科学计算和可视化;谢柏桥,硕士生,研究方向为算法设计和多目标优化;张全元,硕士生,
8、研究方向为算法设计和图像处理。通讯地址:430074湖北省武汉市中国地质大学(武汉)计算机学院2006级硕研10班;Tel:(027)65079584;E2mail:wangjian2wen8016@126.comAddress:Class10,Graduate2006,SchoolofC
