资源描述：
《旅行商问题外文文献翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、旅行商问题外文文献翻译(含：英文原文及中文译文)文献出处：MaskDorigo.Travelingsalesmanproblem[C]//IEEEInternationalConferenceonEvolutionaryComputation.IEEE,2013,3(1),PP:30-41.英文原文TravelingsalesmanproblemMaskDorigo1IntroductionInoperationalresearchandtheoreticalcomputerscience,theTravelingSalesmanProblem(TSP)isaNP-difficultcom
2、binatorialoptimizationproblem.Bygivingpairsofcity-to-citydistances,findeachcityexactlyoneshortesttrip.Itisaspecialcaseofbuyertravelproblems.Theproblemwasfirstelaboratedin1930asoneofthemostin-depthresearchquestionsinmathematicsproblemsandoptimization.Itbecomesabenchmarkformanyoptimizationmethods.Al
3、thoughtheproblemisdifficulttocalculate,alargenumberofheuristicdetectionsandexactmethodsareknowntosolvecertainsituationsthatcontaintensofthousandsofcities.TSPhasmanyapplications,evenbasedonitsmostessentialconceptitself,suchasplanning,logistics,andmanufacturingmicrochips.Withminorchanges,ithasemerge
4、dasasub-probleminmanyareas,suchasDNAsequencing.Intheseapplications,thecitiesintheTSPrepresentthecustomers,weldingpoints,orDNAfragments.ThedistanceintheTSPrepresentsthetraveltimeorcost,orsimilaritymeasurebetweenDNAfragments.Inmanyapplications,additionalconstraints,suchaslimitedresourcesortimewindow
5、s,maketheproblemquitedifficult.Incomputationalcomplexitytheory,thedecisionversionoftheTSP(givenalengthL,thegoalistojudgewhetherthereisanytravelshorterthanL)belongstotheclassofnpcompleteproblems.Therefore,itislikelythatintheworstcasescenario,theoperatingtimerequiredtosolveanyoftheTSP'salgorithmsinc
6、reasesexponentiallywiththenumberofcities.2HistoryTheoriginofthetravelingsalesmanproblemisstillunclear.Amanualof1832referredtotheproblemoftravelsalesmen,includingexamplesfromGermanyandSwitzerland.However,thereisnomathematicaltreatmentinthebook.Thetravelingsalesmanproblemwaselaboratedinthe19thcentur
7、ybytheIrishmathematicianW.R.andtheEnglishmathematicianThomasKirkman.Hamilton'sIcosiangameisacasualgamebasedonfindingtheHamiltonCircle.ThegeneralformofTSP,firststudiedbymathematiciansandespeciallyKarlMengerattheVi
