章几种启发式方法分析对于旅行推销员问题案例.pdfVIP

Chapter3

ANANALYSISOFSEVERALHEURISTICS

FORTHETRAVELINGSALESMANPROBLEM∗

DANIELJ.ROSENKRANTZ,RICHARDE.STEARNS

ANDPHILIPM.LEWISII

GeneralElectricResearchandDevelopmentCenter,Schenectady,NY12345,USA

Reprintedfrom:SIAMJ.Computing,Vol.6,No.3,Sept.1977,pp.563–581.

c

SIAM

Severalpolynomialtimealgorithmsfinding“good,”butnotnecessarilyopti-

mal,toursforthetravelingsalesmanproblemareconsidered.Wemeasurethe

closenessofatourbytheratiooftheobtainedtourlengthtotheminimaltour

length.Forthenearestneighbormethod,weshowtheratioisboundedaboveby

alogarithmicfunctionofthenumberofnodes.Wealsoprovidealogarithmic

lowerboundontheworstcase.Aclassofapproximationmethodswecallinser-

tionmethodsarestudied,andthesearealsoshowntohavealogarithmicupper

bound.Fortwospecificinsertionmethods,whichwecallnearestinsertionand

cheapestinsertion,theratioisshowntohaveaconstantupperboundof2,and

examplesareprovidedthatcomearbitrarilyclosetothisupperbound.Itisalso

shownthatforanyn≥8,therearetravelingsalesmanproblemswithnnodes

havingtourswhichcannotbeimprovedbymakingn/4edgechanges,butfor

whichtheratiois2(1−1/n).

Keywords:travelingsalesmanproblem,approximationalgorithm,k-optimal,minimalspan-

ningtree,triangleinequality

ReceivedbytheeditorsJuly19,1976,andinrevisedformDecember13,1976.

∗AnextendedofthispaperisintheProceedingsoftheIEEEFifteenthAnnualSymposiumon

SwitchingandAutomataTheory,1974,underthetitleApproximatealgorithmsforthetravelingsales

problem.

S.S.Ravi,S.K.Shukla(eds.),FundamentalProblemsinComputing,

c

Science+BusinessMediaB.V.2009

46

1.Introduction

Thetravelingsalesmanproblemhaslongbeenofgreatinterest.Theprob-

lemhasbeenformulatedinseveraldifferentways.Weusethefollowingfor-

mulation:

AtravelingsalesmangraphGisacompleteweightedund