毕业设计外文翻译.docx
- 文档编号:2319699
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:16
- 大小:29.12KB
毕业设计外文翻译.docx
《毕业设计外文翻译.docx》由会员分享,可在线阅读,更多相关《毕业设计外文翻译.docx(16页珍藏版)》请在冰点文库上搜索。
毕业设计外文翻译
毕业设计/论文
外文文献翻译
院系计算机电子系
专业班级计科0801
姓 名刘阳
原文出处http:
//en.wikipedia.org/wiki/
Travelling_salesman_problem#Description
评分
指导教师尹帆
华中科技大学武昌分校
2012年3月7日
毕业设计/论文外文文献翻译要求:
1.外文文献翻译的内容应与毕业设计/论文课题相关。
2.外文文献翻译的字数:
非英语专业学生应完成与毕业设计/论文课题内容相关的不少于2000汉字的外文文献翻译任务(其中,汉语言文学专业、艺术类专业不作要求),英语专业学生应完成不少于2000汉字的二外文献翻译任务。
格式按《华中科技大学武昌分校本科毕业设计/论文撰写规范》的要求撰写。
3.外文文献翻译附于开题报告之后:
第一部分为译文,第二部分为外文文献原文,译文与原文均需单独编制页码(底端居中)并注明出处。
本附件为封面,封面上不得出现页码。
4.外文文献翻译原文由指导教师指定,同一指导教师指导的学生不得选用相同的外文原文。
旅行商问题
1引言
在运筹学和理论计算机科学中,旅行商问题(TSP)是一个NP-困难的组合优化问题。
通过给出成对的城市间距离,找到每个城市恰好访问一次最短的周游。
它是购买者旅行问题的一个特殊情况。
问题最早是在1930年作为数学问题和优化中最深入研究的问题之一被系统地阐述。
它成为许多优化方法的一个基准。
虽然问题难以计算,但已知大量的启发式检测和确切方法,可以解决含有数以万计城市的某些情况。
TSP有许多应用,甚至基于它最本质的概念本身,如规划,物流,制造微芯片。
略作改动,在许多领域中,它作为子问题出现,如DNA测序。
在这些应用中,TSP中的城市代表的是,客户,焊接点,或DNA片段,TSP中的距离代表的是,行驶时间或成本,或DNA片段之间的相似性度量。
在许多应用中,额外的限制,如有限的资源或时间窗口使问题变得相当困难。
在计算复杂性理论中,TSP的决定版本(给定一个长度L,目标是判断是否有比L短的任何周游)属于np完全问题的一类。
因此,很可能在最坏的情况下,解决TSP的任何算法所需的运行时间随城市数量的增加而成倍增加。
2历史
旅行商问题的起源目前还不清楚。
一本1832年的手册提到了旅行推销员的问题,其中有德国和瑞士周游的例子,但书中未含数学处理。
旅行商问题在19世纪被爱尔兰数学家W.R.和英国数学家ThomasKirkman所阐述。
Hamilton的Icosian游戏就是一个基于找到哈密顿圈的休闲游戏。
一般形式的TSP,最早在1930年的维也纳和哈佛大学被数学家特别是KarlMenger所研究,KarlMenger定义了问题,考虑了显然的蛮力算法,并考察了非最近邻的启发式:
我们表示信使问题(因为在实践中,每个邮递员都要解决这个问题,许多游客也一样),它的任务是,已知有限多点及其成对距离,找到最短的连接路线。
当然,这个问题是可解的有限多个试验。
规则可使试验的次数少于给定点的排列种数,但它不为人所知。
首先从起点到最近点,然后从该点到离它最近的下一点……,这样的规则一般不构成不了最短路线。
HasslerWhitney在普林斯顿大学介绍了TSP后,这个问题很快在20世纪五六十年代的欧洲和美国科学界流行。
在圣莫尼卡,兰德公司的GeorgeDantzig,DelbertRayFulkerson和SelmerM.Johnson,为此做出了贡献,他们把TSP作为一个整数线性规划和改进的切割平面问题求解。
有了这些新的求解方法,他们构建了一个最佳周游,解决了一个含49个城市的实例,同时证明没有其它的周游可以更短。
在接下来的几十年中,问题被许多数学,计算机科学,化学,物理和其他科学的研究者做了研究。
RichardM.Karp在1972年研究表明,哈密顿圈问题是NP完全的,这意味着TSP是NP-困难的。
这提供一个数学解释,为什么找到最佳周游有明显的计算难度。
在20世纪70年代末和1980年,问题有了重大突破,Grötschel,Padberg,Rinaldi和其他人一起,采用切割平面法与分支定界,完全成功地解决最多含2392个城市的实例。
在20世纪90年代,Applegate,Bixby,Chvátal,andCook开发了“协和”程序,在最近的许多求解中被使用。
1991年,GerhardReinelt公布了TSPLIB,其搜集了不同难度的例子,被许多研究小组用于比较结果。
2005年,cook和其他人由一个芯片布局问题找到了通过33810个城市的最佳周游,这是目前TSPLIB中最大的求解实例。
对于其它含以百万计城市的许多实例,可以找到问题求解,且保证有1%是一个最佳周游。
3描述
3.1作为一个图形问题
TSP可以转化为无向带权图,如同,城市是图的顶点,路径是图的边,路径距离是边长。
这是一个最小化问题,开始和结束在一个指定的顶点,其它顶点恰好访问一次。
一个哈密顿圈是TSP的一个最佳周游则每边的距离成正比。
通常情况下,该模型是一个完全图(即每对顶点是由边相连)。
如果两个城市之间没有路径存在,增加一个任意长度不影响最佳周游的边,成为完全图。
3.2非对称和对称
在对称的TSP中,两个城市之间在每一个相反的方向的距离是一样的,形成一个无向图。
这种对称将可能的求解分半。
在不对称的TSP中,可能不存在双向路径或双向路径不同,形成一个有向图。
交通事故,单行道,不同时间和价格的机票正是破坏这种对称性的例子。
3.3相关问题
在图论中的一个等价命题是:
给定一个完全带权图(其中顶点表示城市,边表示的路径,权值表示成本或距离),找到权值最小的哈密顿环。
返回出发城市的要求,并不改变问题的计算复杂性,看哈密尔顿路径问题。
另一个相关的问题是瓶颈旅行商问题(瓶颈TSP):
在带权图中找到关键边权值最小的一个汉密尔顿环。
问题具有相当的实际意义,除了在明显的运输和物流领域,一个典型的例子是制造印刷电路调度的路线钻机在PCB上钻孔。
在机械加工或钻孔应用中,“城市”是零件或钻的孔(尺寸不同),“遍历的开销”包含为更换零件(单机作业排序问题)的时间。
广义旅行商问题涉及“州”,(一个或多个)“城市”,推销员从各个“州”拜访每个“城市”一次,也被称为“旅行政治家问题”。
令人惊讶的是,Behzad和Modarres发现,广义旅行商问题可以转化成与城市数量相同的一个标准的旅行商问题,是修改后的距离矩阵。
顺序排序问题涉及访问一系列相互存在优先关系城市的问题。
旅行商问题解决购买者购买一套产品。
他可以在几个城市购买这些产品,但价格不同,同时不是所有城市提供相同的产品。
目标是在所有城市中找到一条路径,最大限度地减少总开销(旅行开销+采购开销)。
4计算的解决方案
解决NP-困难问题的传统思路有以下几种:
1)设计算法找到确切的解决方案(只适用于小的问题,这将很快完成)。
2)制定“次优”或启发式算法,即算法看似或可能提供良好的解决方案,但它不能被证明是最佳的。
3)找出问题(子问题)的在特殊情况下的解或启发式是可能的。
4.1计算复杂性
问题已被证明是NP-困难问题(更确切地说,它是复杂类FPNP),决策问题版本(给定的开销和一个数x,判断是否有比X便宜路径)是NP完全问题。
瓶颈旅行商问题,也是NP-困难问题。
取消每个城市“只访问一次”这个条件,并不能消除Np-困难,因为很容易看到,在平面的情况下最佳的周游一定是每个城市只访问一次(否则,由三角不等式可知,一条跳过重复访问的捷径不会增加周游的长度)。
4.2近似的复杂性
在一般情况下,找到最短的旅行商问题的周游,是NPO-完全。
若距离是可度量和对称的,问题就变为APX-完全。
Christofides的算法约在1.5以内。
如果限制为1和2(但仍然是一个度量),近似比为7/6。
在不对称,计量的情况,只有对数性能可以保证,目前算法最好的实现性能为0.814logn;如果存在一个常数因子近似,则它是一个开放的问题。
相应的最大化问题找到最长的旅行商周游逼近63/38。
如果距离函数是对称的,最长周游可以通过确定性算法和随机算法近似在4/3。
4.3精确算法
最直接的办法,是尝试所有的排列(有序组合),看看哪一个是开销最小(使用蛮力搜索)。
这种方法的时间复杂度为O(n!
),城市数量的阶乘,所以这种求解,即使只有20个城市也是不切实际的。
动态规划的最早的应用之一是Held–Karp算法,解决问题时间复杂度为O(n22n)。
动态规划解决方案,需要指数的时间复杂度。
使用列入-排除,可以在2n时间和空间内解决问题。
改善这些时间效率似乎很难。
例如,尚不知道是否存在TSP的精确算法,时间复杂度为O(1.9999n)。
4.4其他方法包括
1)不同的分支定界算法,可用于40-60个城市的TSP。
2)改进的线性规划的算法,很好地处理含200个城市的TSP。
3)分支限界和具体切代,是解决大量实例的首选方法。
当前这种方法拥有解决85900个城市实例的记录(2006年)。
一个为15112个德国城镇的求解,于2001年在TSPLIB中被发现,其使用1954年,GeorgeDantzig,RayFulkerson,和SelmerM.Johnson提出的割平面法,基于线性规划。
莱斯大学和普林斯顿大学对含有110个处理器的网络进行了演算,总计算时间相当于一个500兆赫处理器工作22.6年。
在2004,旅行商问题访问所有24978个城镇在瑞典被解决,周游长度约72500公里,同时被证明了不存在更短的周游。
2005年3月,在一块电路板上的访问所有33,810点的旅行商问题通过使用协和TSP的求解器被解决:
一个长度为66048945单位的周游被发现,同时证明没有更短的周游存在。
计算了约15.7CPU年(Cook等,2006)。
2006年4月,85900点的一个实例使用协和TSP的求解器,解决时间超过136的CPU年(2006年)。
4)启发式近似算法
多种能迅速产生良好的求解的启发式近似算法,已经被制定。
现在的方法可以在合理的时间内解决非常大的问题(含以百万计的城市),且只有2–3%的概率远离最优解。
建设性启发式最近邻(神经网络)算法(或所谓的贪婪算法)让推销员选择未访问过的最近城市作为他的下一步行动目标。
该算法快速产生一个有效的短路径。
对于随机分布在一个平面上的N个城市,该算法平均产生的路径比最短的路径长的25%。
然而,存在着许多特殊分布的城市,使神经网络算法给出最坏的路径(Gutin,Yeo,andZverovich,2002)。
这是对称和非对称旅行商问题真正的问题(GutinandYeo,2007)。
Rosenkrantz等人研究表明,神经网络算法具有近似因子Θ(log |V|)的情况下满足三角不等式。
基于最小生成树的构造的近似比为2。
Christofides算法达到了1.5的比例。
Bitonic周游是一组点的最小周长构成的单调多边形,它可以通过动态规划有效地计算。
另一种建设性的启发式,两次比较合并(MTS)(Kahng,Reda2004),执行两次连续的匹配,第二次匹配在删除所有第一次匹配的边后执行。
然后合并,以产生最终的周游。
迭代改进,成对交换,或Lin–Kernighan启发式,成对交换或2-技术涉及反复删除两条边和替换那些建立一个新的和更短的周游所不需要的边。
这是一个K-OPT方法的特殊情况。
请注意,Lin–Kernighan经常是2-OPT的误称。
Lin–Kernighan实际上是一个更一般的方法。
k-opt启发式,一个给定的周游,删除k相互不相交的边。
将其余部分重新组合成一个周游,留下不相交子周游(即,不相连的一个部分的终点在一起)。
这实际上使正在考虑的TSP简化为一个简单得多的问题。
每部分端点有2K-2个其他的连接可能性:
2K总体终点可连接,则该部分是不能考虑的。
这种受约束的2K-TSP然后可以用蛮力方法解决,找到最低开销的原部分重组。
K-opt是一种特殊情况下的V-opt或variable-opt技术。
最流行的K–opt是3-opt,这些都是由贝尔实验室的ShenLin在1965年推出的。
有一个边不相交的3-OPT特殊情况(两边相邻)。
v-opt启发式,variable-opt方法与k-opt方法相关,是K-opt方法的推广。
而K-opt从原来的周游删除一个固定的数(K),variable-opt方法不删除固定大小的边集。
相反,他们搜索过程中继续成长。
在这里已知最好的方法是Lin–Kernighan的方法(上面提到作为一个2-OPT误称)。
ShenLin和BrianKernighan在1972年首次公布他们的方法,这作为最可靠的解决旅行商问题的启发式近二十年。
更先进的variable-opt方法是在贝尔实验室在80年代后期由DavidJohnson和他的研究团队发展。
这些方法(有时被称为)在Lin–Kernighan方法上,从禁忌搜索和进化计算添加了一些方法。
基本的Lin–Kernighan技术给出的结果,是保证至少3-opt。
Lin–Kernighan–Johnson方法计算的Lin–Kernighan周游,然后通过所谓移动至少四条边和以不同方式连接周游的突变打乱周游,然后以V-opt方法建立新的周游。
v-opt方法被广泛认为是解决问题的最强大启发式,并能够在特殊情况下解决问题,如汉密尔顿环问题和其他非十进制的TSP,而其他启发式做不到。
多年来,Lin-Kernighan-Johnson已经被证明是对TSP所有已经尝试过的求解中的最佳求解。
Travelingsalesmanproblem
1Introduction
Thetravelingsalesmanproblem(TSP)isanNP-hardproblemincombinatorialoptimizationstudiedinoperationsresearchandtheoreticalcomputerscience.Givenalistofcitiesandtheirpairwisedistances,thetaskistofindtheshortestpossibletourthatvisitseachcityexactlyonce.ItisaspecialcaseoftheTravelingpurchaserproblem.
Theproblemwasfirstformulatedasamathematicalproblemin1930andisoneofthemostintensivelystudiedproblemsinoptimization.Itisusedasabenchmarkformanyoptimizationmethods.Eventhoughtheproblemiscomputationallydifficult,alargenumberofheuristicsandexactmethodsareknown,sothatsomeinstanceswithtensofthousandsofcitiescanbesolved.
TheTSPhasseveralapplicationseveninitspurestformulation,suchasplanning,logistics,andthemanufactureofmicrochips.Slightlymodified,itappearsasasub-probleminmanyareas,suchasDNAsequencing.Intheseapplications,theconceptcityrepresents,forexample,customers,solderingpoints,orDNAfragments,andtheconceptdistancerepresentstravelingtimesorcost,orasimilaritymeasurebetweenDNAfragments.Inmanyapplications,additionalconstraintssuchaslimitedresourcesortimewindowsmaketheproblemconsiderablyharder.
Inthetheoryofcomputationalcomplexity,thedecisionversionoftheTSP(where,givenalengthL,thetaskistodecidewhetheranytourisshorterthanL)belongstotheclassofNP-completeproblems.Thus,itislikelythattheworstcaserunningtimeforanyalgorithmfortheTSPincreasesexponentiallywiththenumberofcities.
2History
Theoriginsofthetravellingsalesmanproblemareunclear.Ahandbookfortravellingsalesmenfrom1832mentionstheproblemandincludesexampletoursthroughGermanyandSwitzerland,butcontainsnomathematicaltreatment.
WilliamRowanHamiltonThetravellingsalesmanproblemwasdefinedinthe1800sbytheIrishmathematicianW.R.HamiltonandbytheBritishmathematicianThomasKirkman.Hamilton’sIcosianGamewasarecreationalpuzzlebasedonfindingaHamiltoniancycle.ThegeneralformoftheTSPappearstohavebeenfirststudiedbymathematiciansduringthe1930sinViennaandatHarvard,notablybyKarlMenger,whodefinestheproblem,considerstheobviousbrute-forcealgorithm,andobservesthenon-optimalityofthenearestneighbourheuristic:
Wedenotebymessengerproblem(sinceinpracticethisquestionshouldbesolvedbyeachpostman,anywayalsobymanytravelers)thetasktofind,forfinitelymanypointswhosepairwisedistancesareknown,theshortestrouteconnectingthepoints.Ofcourse,thisproblemissolvablebyfinitelymanytrials.Ruleswhichwouldpushthenumberoftrialsbelowthenumberofpermutationsofthegivenpoints,arenotknown.Therulethatonefirstshouldgofromthestartingpointtotheclosestpoint,thentothepointclosesttothis,etc.,ingeneraldoesnotyieldtheshortestroute.
HasslerWhitneyatPrincetonUniversityintroducedthenametravellingsalesmanproblemsoonafter.
Inthe1950sand1960s,theproblembecameincreasinglypopularinscientificcirclesinEuropeandtheUSA.NotablecontributionsweremadebyGeorgeDantzig,DelbertRayFulkersonandSelmerM.JohnsonattheRANDCorporationinSantaMonica,whoexpressedtheproblemasanintegerlinearprogramanddevelopedthecuttingplanemethodforitssolution.Withthesenewmethodstheysolvedaninstancewith49citiestooptimalitybyconstructingatourandprovingthatnoothertourcouldbeshorter.Inthefollowingdecades,theproblemwasstudiedbymanyresearchersfrommathematics,computerscience,chemistry,physics,andothersciences.
RichardM.Karpshowedin1972thattheHamiltoniancycleproblemwasNP-complete,whichimpliestheNP-hardnessofTSP.Thissuppliedamathematicalexplanationfortheapparentcomputationaldifficultyoffindingoptimaltours.
Great
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业设计 外文 翻译