Le Problème du voyageur de commerce

De
Publié par

Niveau: Supérieur

  • mémoire


Le Problème du voyageur de commerce Charles Bouillaguet 26 juin 2004 Définition du problème Le problème du voyageur de commerce est un prob- lème classique d'optimisation : il s'agit de trouver la plus courte tournée perme- ttant de visiter n villes et de revenir au point de départ en ne visitant chaque ville qu'une seule fois. Ce problème se trouve généralement formulé dans le langage des graphes : on considère un graphe (S,A) où S, les sommets du graphe, représentent les villes, et A, les arêtes, représentent les routes. Un cycle à k sommets est alors un ensemble de k sommets (s0, s1, . . . , sk) tels que sk = s0 et (si, si?1) ? A pour i = 1, 2, . . . , k. La longueur d'un tel cycle est la somme des longueurs des arêtes qui le composent. Un cycle qui relie tous les sommets fois et une seule est appelé cycle Hamiltonien. Dans la suite, on notera n = |S| le nombre de sommet du graphe. Le but du problème est de déterminer le cycle Hamiltonien de plus courte longueur. Par abus de langage, nous écririons souvent cycle, pour dire cycle hamiltonien. Nous travaillerons avec certaines hypothèses : nous supposerons que la distance utilisée pour fournir la longueur des arêtes est euclidienne et qu'elle vérifie donc l'inégalité triangulaire) : d(a, c) ≤ d(a, b) + d(a, c) (

  • arbre couvrant

  • exploration de l'arbre

  • arbre

  • court cycle


Publié le : mardi 1 juin 2004
Lecture(s) : 36
Source : di.ens.fr
Nombre de pages : 11
Voir plus Voir moins

n
(S,A) S
A k
k (s ,s ,...,s ) s =s (s ,s )∈A0 1 k k 0 i i−1
i=1,2,...,k
n = |S|
3d(a,c)≤d(a,b)+d(a,c) (a,b,c)∈S
(a,b)
(b,a) {a,b}
(s ,...,s ,s )0 n 0
n
(n−1)!
2
complet,tnomlesun.routes.estUnlacyclee?oseronsrepr?sennoterasommetsqueestprobl?mealorseutunleensemparcoursbleoriendetar?tes,Enn,sommets?lesherc,desetcommercevilles,nonlescomtdetentrepr?sentelgraphe,dudulesommetsar?teslesageur,m?meo?dutelsquequehaquegrapheJustionsuncycleconsid?rel'honp:existenetjuingraphesodescycleslangageestlededanscul??formHamiltoniens,tseg?n?ralemendee:trouvdonnerpIlourNousseplusprobl?men'estCe:fois.prob-seulecommercequ'unenevilleseulehaquehose,cot.visitansupp.grapheLaquelongueurestd'unlestelemencycleplusestnouslaexistesommeoth?sedesdulongueursd'armerdeshamil-ar?tesEnquiD?nitionleBouillaguetcompageurosenestt.bleUnestcycleetquiOnreliel'?lementousminimale.lesUnesommetstr?sfoisprobl?meetlaunelesseule?estcourt.appcepel?unecycle:Hamiltonien.D?nomDansdonnerlac'estsuite,ordreonvnoteraenneLeensuppd?partdedequetgraphelepasnomt?brelesdel?mesommetunduetgraphe.deLeybutsonduqu'uneprobl?meetestcdequ'ond?terminerdonclevcycleprobl?meHamiltoniendenousplusoseronscourtelelongueur.estPc'est-?-direarcabussommetsdereli?langage,tousnousautres.?cririonsbrievsouvtenletcourtcycle,queprecourhonsdire:cycleyphamiltonien.deNouscompl?tudetragraphevermetailleronsqueacyclesvtoniensoint.teneetLecarduon2004un26donn?,Charlesreviendeauydeen?bienduL'ensemsommet,des?hamiltoniendudonc...,vide,?ilduni.Depilconsid?rerttm?melongueurparcourirExplosionbbinatoiredansapprosenshedansna?v(d'o?dudivisionconsisteraitdeux).d?terminertriangulaire)longueur:touspcyclesauetenirprendrerevplusdeOnetheurtevillesendanvisiter?dedicult?ttaillettanleurerme-bre.pbrons-lestourn?esecourteunpluscycle,laseeruntrouvdededess'agitvilles.ily:ad'optimisationProbl?meclassiqueec,certainessihconsid?reypparcoursoth?sesil:tm?menouscommencersupppartiroseronspremierqueo?lapartirdistance2?me,utilis?eouppartirourn-i?me.fournirplus,larevienlongueuraudesdear?teslaestoucleeuclidienneunetouqu'ellel'autrevla?riepardonc1l'in?galit?n=250
249! 249! 490’10
2 2
J1,nK
n (n−1)
(n−2)
250!
n
nO(n!) O(2 )
n
2O(n )
ceceuxvironobtensonus(sansparetd'autresenparticipanpts.desDansentouteunlasursuite,estnousparpmaisoseronsIldoncPVecunvtaon.doitIlauparaylea2),doncpasser?sultats18nosCescyclesde?qu'elletester.eut-?treSacnotrehanaucuntfonctionqueerscomparerLapuplusdoncproonsqu'onvcycle.,uneil?t?youraimpbiencourt.plusd'ex?cutiondebrecyclesle?ultipli?tester?quepassed'atomes?dansdel'univters...formLefonctionsoleilenauraaill?largemenaleur,talevisageabletempsvilles.d'exploserfait,afournitvtempsannomtsommeslad'appronendesatests.laOnvpseeutavprooirlesl'ensempblefournitdes(notrepcadreerm?parsutationsendeLaa?treNousest[1].onternetleinregardan,dudoncetdulavilleracineconstateestdelevironpremier3sommets,16etpuisdon2t17ladeprofondeuretestlorsqu'onde?surne.susanLesdonner?m?metrouvcomplexit?d?surd'unsemlscasdeinf?rieurelatraracinederni?resonaurionstsugg?rerlesTIPE,sommetstoutefoisquil'utiliserseron?tdevisit?sximationencedeuxi?megorithmepsolutionosition.enChacunseraitd'enolynomialetredeeuxNousatourn?sissum?thovilles,fournissan250cycle?tempslsquequionsseroneuvretdevisit?scenPtroisi?mesommet,pauosition,heetencoreainsir?it?redeUnesuite.visit?Cetduarbreau?fermerprobl?mem?thofeuilles,r?sultatquitr?srepr?sentationtenentDansdesquelquescyclesonhamiltoniens.auparaNousetatr?sv?nalit?onspasmisccupauenpemenointe,tvungure.programmeplusquiEnr?soundtexactementableauttempsledePVprogrammeCfonction(pnomourdeun(gurenomonbrequedetempsvillecalculmoendeste)menparexploranlorsqu'ontdesyst?matiquemenvillest17,l'arbreendesparplorsqu'onossibilit?sde(en?enetfaisan18t19,unennparcours10enpasseprofondeur).19Sa20.complexit?donn?esestsondoncpas?tesprioriourfactorielle.uneCepuleendanempiriquet,launeenastucedea,?t?ilinbletrotoutduite,clairquiestdimin?uevnotable-onsmenlatvlenoustempspd'?xecutionos?:vcertainesnousar...).n'esttesentr?sdelonguessurneprobl?megureron250tN?cessit?jamaism?thodansd'approdesEncycles?courts.jourL'explorationn'al-denebranclahesduenCti?resundequil'arbreuneppourraitdedoncbre?trevilleevit?e.s'ilnouss'adoncvv?redesqu'elledesconduiraitximation,?tdescourtcycleshamiltonienplusunlongraisonnable.quepremi?relenousplusycourtmisecycleod?j?estconnm?thou.desLeproprogrammehesgardeoisin.doncartanend'unm?moireonlarendlongueurplusducplusqu'oncourtpascyclevisit?,qu'ilonconnait.leLorscessus.defoisuna).tousemensommetsongraphe,oitretourne3)premierleourestleIlCettepdedesuntenseraittempsvbreftageuximpl?mend?croiser),alorsquecomplexit?s'ap-decleden,l'explorationQualitativdet,l'arbre,vsi(gurelaquesommer?sultatdesam?liorable.longueurscom-desortear?tescroisemenconduisan(qu'iltaduansommetdeactuelet?l'onlaproracineheestlaplusl'algorithmelonguerelierquesommetslequiplustcourtn?glig?stravjett,connquiu,tl'exploration?loign?s.depcettepbrancnehes'ens'arr?teo:?ellevconduiraittn?cessairemenrelativtt?ortanuncommetralejetoitquilan'est2pasintypeossibilit?sresultat0;=erformanceCut+.|->Chemin17ofcoupure_searchfloat+.*|int(Cheminlist;;fonction(*calculgmin:thenledeja_vugrapheChemin(une->matricei::parcours;desend;distances)withdepart->:Fig.letsommetvillesde35sd\'epart35(pourFig.pouvoirr?solutionyresrevenir)departactuel-.:reslewhensommet<=o\`u:=nousparcours_minsommes:=actuellement->deja_vudeja_vu.(actuel):(!trouve,un_tableau|false,precisant|false,les(g.(actuel).(depart),sommetsd\'ej\`aevisit\'esdesbornebre:empsle0,5splus4mincourtminchemin19connu10pourlesprogrammesommets3restantslet\`a=voirg*)ilet(!cout_minrecg.(actuel).(i))coupure_searchmatchgwithdepart(cout,parcours)actuelcoutdeja_vug.(actuel).(i)borne!cout_min=cout_minletg.(actuel).(i)cout_mincout;=:=reftrouvebornetrue;andCutparcours_min()=done;ref<-[]matchand!teste)trouvetrue,=->ref(!cout_min,!parcours_min))falsetrueandCuttestefalse=Cheminref[depart]);;false1inLadeja_vu.(actuel)r?cursiv<-exploran1;l'arbreforpiNom=de0Ttode(Array.length13g)15-116do03sif13deja_vu.(i)18=min065then20beginhteste2:=Ptrue;duifde!cout_minexacte>=g.(actuel).(i)(A,S)
A
2O(n ∗logn)
k k+1
H
M
L(H)≤2L(ACM)≤2L(M)
H
a b
d(a,b)=n−( a b )
d
d(a,b) a b
aacyclique,?galemenquiunam?thotousm?tholesr?sultatsommetsondear?tessous-graphebre(illongestte,couvrandest),CM).etourdonmaintm?tholatrelongueurdistance,estunminimale:(i.e.osiplusonraisonsprenddeunplusautrecettearbredescouvranlot,euiltseraaplusceslong).d'uneOnetpeneut?construireOncetIlarbre,etgr?ceraf-?tenanl'algorithmeainsideauPrimplusentunordtempstpensuiteolynomial.deNotrelaimpl?mente,tation6)deparcethesalgorithmeorne(quifourniesutilisetesdes?tascarbinaires)tsal'airunehercomplexit?rapideend'abunblec'est::et4)c(gureetgrapheth?oriquenotrepsurl'in?galit?.sesUnetfoiscouvranl'arbredoncconstruit,l'Aeecuons-enaunNousparcours,eucommeuneindiqu?onssurOnlalegure6)5.deuxC'estqueuncycle.parcoursinenourprofondeurtouto?c'estlorsqu'onquirepassemaparcommise,unilsommetuneenlongueurremoncycletandet,mani?reonr?sultatlederefaitmoinsappara?treceluidansm?tholeproparcours.oisins,Ainsi,aucunesin'existe.unLessommetles?pr?c?-(A.C.M.)tls,tesilqu'?appara?traferaitminimalcomptdescouvrandefoisondansOnlepparcours.surChaquesyst?matiquear?teourestTainsionparcourueunirdeuxcyclesfoisd?nie:distanceunecyclesfoisestdanstr?sclehaquequesens.onAinsi,unlabienlongueurledutparcours?rierobtenplusuedeest-ellear?tes.exactemenobtientalorsdeuxarbrefoist.celleestdeplusl'arbrequecouvranCM,t.onMainalorstenanallonst,n?e.supprimonspluslespsommetsid?eapparaissanttmainplusyd'unevfois,aenquelaissancylet(gurepasserestleurpirepremi?refoisolongccurenceledanscourtleCeparcours,estpuist?ressanenpsupprimandeuxt:lesd'absuiv-caranl'untes.aresLefournissenparcoursunedonn?jorationenl'erreurexempleetdeviencartdonne:tabminorationcdefgh.laRadujoutonscourtune(parolongeurc-l'AcurenceDedusurprenanpremierlesommetde?m?thola(gurenest:bonqueobtienfournittlaundecycleplushamilonien.cCevfaisanpt,laquelleonbneth?oriquefaitOptimisationquecalediminsolutionsuerparladeuxlongueurdesdudenparcours,soncarplasatisfaisandistance(onestl'impressioneuclidienne.laL'in?galit?ontriangulairemieux),nousellesgaranortentitsoitquecroisemenlasoitlongueurgrandesduquiparcourstn'augmenridicule.tevpasselorsqu'onencretireicilesunesommetsder?currenetts.pOnam?liorerasolutions.ainsioutobtenord,uvunmcyclel'ensemdondesthamiltoniensladistancearbreparindiquelafaitennomdeuxd'ar?tessatisfaisanconnexe,eudeptoutmalgr?partagenempirique,pas.hel'AapproCM.nomNotons-led'ar?tesunpremi?reConsid?ronscettemainttenancommtApr?sleestplusunecourtetcycle,seuletoinnotonsnon-imm?diatlevconstruireest.triangulaire.CoupdeonsUneunelongueurenestleinf?rieurebre?quedeuxetfoisnelatlongueur4de4Fig.:3couvran14,7321M?thoUndeminimal.des5plusFig.procarbrehestvlongueuroisins.10,40longueur:a
fb
e
c
d
g
h
l'arbrecblongueurFig.t16,348dedbaeafgfhfaFig.65M?thodeLecouvranparcoursminimal.g?n?r?:est6abS(a ,2)0
a (a ∈S)0 0
a S(a ,2)0 0
a0
a0
a0
S(a ,2)0
a0
n(n−1)
2S(a ,2) O(n )0
a S(a ,2)1 0
a1
S(a ,2) a a0 1 0
S(a ,2)0
a1
S(a ,2) a a ∈0 1 1
S(a ,2) a a0 1 0
b S(a ,2)0
x∈[0;1] b a
¡ ¢
x≤f L(a)−L(b),k
L(a) a f
x∗(ρ+kμ)
f(x,k)=e
? ? f
ρ
μ
ρ=45
μ=4,5
plesNotonsparcourstobtenprobabilit?usestentlesquid?croisandestsiseronl'explorationtsondans,croisemenladesttttienuneconr?sultatssicycle,usettilsterrompreseron,ttr?eplustoutcourtspseudo-al?atoireque?particulier,solutionEnest(enNouseet,syst?matiquemenenexemple,d?croisannoust,quiondeydegagnecourttoujours,departerrompt,cons?quencecendeonl'in?galit?tempstriangulaire).tIlcelleressortlesdeencelalongqu'ilEnyraacalculear?tes.s'appdeuxl'algorithme,lesencore.croiserherc?2?lemencycletsseuil.unenontelleutilis?sph?re.?reD?terminerpr?cedenlaclongueurVdu(parplusd?termin?courttescyclefournirdanspartirconsistedesolutionenseuled?sladeuxcycle,7)untr?,pcroisaneutcyclesdoncon?trelafaitenenTencoreasoittempsr?sultathoisirledequedans.ourUnequifoisvquecyclel'onPam?med?termin?estle2plusmani?recourtpcycleyoursph?rep,dansnomar?tes,doncdeuxLorsdieit?rationmoseral'onsiqueplus,d'unonlapdeeutyrecommencerlongueurle.profonctioncessusd?termineencconsid?ranaittvlafonctionspe?reunedeetram?thoyparonr?2danscenguretr?etationsurEmpiriquemenetvdev...lesEtetainsiblendebsuite.solutionCetestm?thol'explorationdel'onam?lioreeet,sensiblemen:t,lesqu'unsolutionsar?tespr?c?denplustesque(gure(gure9),renconetl'explorationfournittunenr?sultatobtentr?ss'inrapidemenett.commenceEndepratique,sph?receptr?eendanlest,.l'algorithmeoutefois,convv?galemenergedeauenbcoutd'ind'unel'explorationcinquanexactementainesond'it?rationst:pilcommencernedetrouvcycleseapasecde,cycled'unplusartancourt.dans,lasispcen?re.plusCettequerapidit?ondedeconpseudo-al?atoire.veet,partourts,?l?mentendefaitdeprobl?matiquela:2-Opt.ilonexisteunpbreeut-?trel'optimisationd'autresellecycles.plusdecourtk-i?mejustedeundeppr?f?r?eum?thoplusCetteloin,courtmaisseraitl'algorithmecycleesthetomrecb??cettedansautourunonpuit?tanduquellaildunerapdeeutuneplusdesortir.ElleNouslaallonsqu'undonchoixmainoptimaltenanlieu.taenonsvisageruneunedumani?reypde:limiterspcetteetd'explorerquites),limitedesladeuxqualit?unedesSugg?solutionsfournietrouvc?es.eIn[2].trooirduisons10,derepr?senl'erreurdeP.ourt,conatourneronscedesph?nom?ne,aleursnousourmoconstandionsuel'algorithmeconn2-Optsemdetlademani?reonssuiv:and'unetede:L'id?eLorsergence7esta S(a ,2)0 0
dot(List.tlt=enbidonunj?lemengain_1twithdeincroisemenArray.of_listUnn-2jtransforman(meilleure_trans)7!actuelle];Fig.|8(Trajet.rotate_untill'optimisation@=r?cursiv(*forcalculetolatmpdiff\'erenceinde1longueurletdugparcoursinp!meilleur_gainsi:=ontmp.(0),relieactuellele@premiermatchpoint->au->j-i\`eme(Trajet.connect_with_firstet(List.tllegdernierbidon]);;aula(j+1)-i\`emer?alisanen8O(1)i*)0letn-2gainletg=p!actuellejforn==tog.(p.(n-1)).(p.(j))do+.gain_1g.(p.(0)).(p.(j+1))gain-.tmp(ng.(p.(n-1)).(p.(0))if+.<g.(p.(j)).(p.(j+1))then);;meilleur_gainletgain_1;rec:=two_opttmp.(j);gdone;p:==!actuelle)let[List.hdndone;=!meilleure_transArray.length0,0gpandi,jactuellelet==refj(List.tlip)p)))andtwo_optmeilleure_trans(bidon=[List.hdrefFig.(0,0)andfonctionmeilleur_gaine=tref2-Opt0.0in1
0.8
0.6
f(L(a)-L(b), k)
0.4
0.2
0
0
–0.02
–0.04
–0.06
–0.08
L(a)-L(b) 0
–0.1 10
20–0.12
30
–0.14 40 iteration
50
Uneouslesutilis?ecroisemenFig.tslaonhestdisparus.10Longueurtation:de12,2641appliqu?evoisins.Tlo2-OptcalecOptimisationpro9plusFig.desderepr?senm?thodelafonctiondeseuilr?sultat9au11,809
0,7%
4,eu(hd'al?am?thoin?vitertroonnesduit)R?f?rencesneetpenermettenn?cessairetuns.pasd?terminedeChars'?loignerosusamenvtdansd'unplusminimt?umeclouescalenetonnet?rmediairepvillesermettenl?metvdonc1997,pasremarquesd'am?liorer:r?ele-minimmenourrait,tun,laysolution.vDeslevcroissanaleurssph?res.tropaptetitestirerralenptissendetcommlahaqueconsolutionsvA.ergence,o.algo.free.fr/de250/de_des_250_villes.hetpsiytroplille.fr/cd'al?aandestrithmiqueinettroguiseduit,nousondeuxnitPparprobl?mestroplos'?loignerondesfoisbetteinonnesunesolutions.(deSur3,laNousgurepas11id?e,ondepfortemeneutavtailleoirLescommenquetons?vtoluetroncslaplongueurdedestparcourstcdehoi-solutionssislesdanspuislaoursph?reortionexplor?e,desetlacommetAl'adesjoutttpde2000.l'al?aR.pleermetvd'obtenirdeune://elevmeilleurektosolution.jects/x/salesman.fr.hAuR.b?outDunod'unh.ppp.etit10quartded'heurenales,deacalcul,anceronsnousid?essommesparvourenlesusdesauumsr?sul-cauxtat2-Opt,deplaunegurequ'on12.aConclusiontetexploreram?liorationssph?reengrossevisageablesraUneondizainepuisdeetc.).candidatsn'aauonsd?impl?mendescette250maisvillestempsoncalcultesttrouvt?tunevsolutionladondestlablongueursolutionsestnousdev(pobtengrandesontropvisiblemen.desIlcommn'estOnbienourraits?rpartipascelaprouvmettan?auqueoinceunesoitdel'optimfusionum,deuxmais:celagardesemtron?onsbleuns,probable.onNouspn'acvponsindonclaquellepasdeuxgagn?estlemeilleure.d?[1]:-).upetit,TD?outefois,250nous(ha://labvtml).ons[2]obtenolois,uHeuristiquesdesoursolutionsprob-quiduneosonageurtcommercequettpaleurses.ec-vharoloi/bacDesja2001.a/proCormen,tml).Leiserson,[3]plusTh.,longuesCh.,queRivest,laIntrplusductioncourtel'algo-conn.ue,d,cecqui5n'est24,pas8489si489499.mal.En

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.

Diffusez cette publication

Vous aimerez aussi