旅行商问题(TSP)及其应用-安康学院毕业论文.doc

学号2010211111分类号TP273本科生毕业论文（设计）题目：旅行商问题(TSP)及其应用院（系）数学系专业班级数学与应用数学10专升本1班学生姓名王文指导教师（职称）刘铁(讲师)提交时间二〇一二年六月安康学院学位论文独创性声明本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究成果.尽我所知除文中已经注明引用的内容外论文中不包含其他个人已经发表或撰写过的研究成果也不包含为获得安康学院或其他教育机构的学位或证书而使用过的材料.对本文的研究做出重要贡献的个人和集体均已在文中作了明确说明并表示谢意.作者签名：日期：安康学院学位论文使用授权声明本人同意在校攻读学位期间论文工作的知识产权单位属安康学院.本人保证毕业离校后发表本论文或使用本论文成果时署名单位仍为安康学院.学校有权保留学位论文并向国家主管部门或其他指定机构送交论文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出版.作者签名：日期：旅行商问题(TSP)及其应用王文（安康学院数学系陕西安康725000）摘要：旅行商问题(TSP)是组合优化领域里的一个易于描述却难以处理的NP完全难题其可能的路径数目与城市数目呈指数型增长求解起来非常困难至今还没有一个完美的算法.该文首先介绍了什么是TSP接着总结了八种目前针对TSP比较有效的解决方法的基本思路及各自算法的优缺点最后通过生活中的例子展示其运用.关键词：旅行商(TSP)算法路径TravelingSalesmanProblemandItsApplicationWangWen（DepartmentofmathematicsAnkangUniversityAnkangShanxi725000)Abstract:Thetravelingsalesmanproblem(TSP)isacombinatorialoptimizationNP-completeprobleminthefieldofaneasytodescribebutdifficulttodealwithitsnumberofpossiblepathsandthenumberofcitiesgrowingexponentiallysolvingverydifficultandhasnotyetbeenanidealalgorithm.ThispaperfirstintroducestheTSPandthensummarizesthebasicideasoftheeightkindsofeffectivewaystosolveTSPtherespectiveadvantagesanddisadvantagesofthealgorithms.FinallythespecificexampleswereusedtoillustratetheapplicationsofTSP.Keywords:TravelingsalesmanproblemAlgorithmPath目录前言11TSP简介22旅行商问题(TSP)的求解方法22．1禁忌搜索法32．2改良圈算法32．3蚁群算法42．4匈牙利算法52．5分支界定法基本思想62．6最邻近法基本思想62．7最小生成树基本思想62．8破圈法基本思想73各种方法的优缺点84TSP在实际生活中的应用9致谢15参考文献16附录A文中涉及的主要程序17附录B文中涉及的数据21前言旅行商问题(TravelingSalesmanProblem简称TSP)是数学领域的著名问题之一.TSP的历史悠久最早描述的是1759年欧拉研究的骑士周游问题.即对于国际象棋棋盘中的64个方格一次且仅一次并最终回到起点.从而将该问题抽象为给定个城市和两两城市间的距离要确定一