Le Problème du voyageur de commerce

Charles Bouillaguet

Description

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

Sujets

• Mémoire
• Arbre couvrant de poids minimal

Informations

• Publié par: profil-nechor-2012
• Publié le: 01 juin 2004
• Nombre de lectures: 43
• Langue: Français

Extrait

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