资源描述：
《毕业论文外文翻译-旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Travelingsalesmanproblem1IntroductionThetravelingsalesmanproblem(TSP)isanNP-hardproblemincombinatorialoptimizationstudiedinoperationsresearchandtheoreticalcomputerscience.Givenalistofcitiesandtheirpairwisedistances,thetaskistofindtheshortestpossibletourthatvisitseachcityexactlyonce.Itisaspecialcaseo
2、ftheTravelingpurchaserproblem.Theproblemwasfirstformulatedasamathematicalproblemin1930andisoneofthemostintensivelystudiedproblemsinoptimization.Itisusedasabenchmarkformanyoptimizationmethods.Eventhoughtheproblemiscomputationallydifficult,alargenumberofheuristicsandexactmethodsareknown,sothatsomeinst
3、anceswithtensofthousandsofcitiescanbesolved.TheTSPhasseveralapplicationseveninitspurestformulation,suchasplanning,logistics,andthemanufactureofmicrochips.Slightlymodified,itappearsasasub-probleminmanyareas,suchasDNAsequencing.Intheseapplications,theconceptcityrepresents,forexample,customers,solderin
4、gpoints,orDNAfragments,andtheconceptdistancerepresentstravelingtimesorcost,orasimilaritymeasurebetweenDNAfragments.Inmanyapplications,additionalconstraintssuchaslimitedresourcesortimewindowsmaketheproblemconsiderablyharder.Inthetheoryofcomputationalcomplexity,thedecisionversionoftheTSP(where,givenal
5、engthL,thetaskistodecidewhetheranytourisshorterthanL)belongstotheclassofNP-completeproblems.Thus,itislikelythattheworstcaserunningtimeforanyalgorithmfortheTSPincreasesexponentiallywiththenumberofcities.2HistoryTheoriginsofthetravellingsalesmanproblemareunclear.Ahandbookfortravellingsalesmenfrom1832m
6、entionstheproblemandincludesexampletoursthroughGermanyandSwitzerland,butcontainsnomathematicaltreatment.WilliamRowanHamiltonThetravellingsalesmanproblemwasdefinedinthe1800sbytheIrishmathematicianW.R.HamiltonandbytheBritishmathematicianThomasKirkman.Hamilton’sIcosianGamewasarecreationalpuzzlebasedonf
7、indingaHamiltoniancycle.ThegeneralformoftheTSPappearstohavebeenfirststudiedbymathematiciansduringthe1930sinViennaandatHarvard,notablybyKarlMenger,whodefinestheproblem,considerstheobviousbrute-forcealg
