Den omreisende selgers problem

I informatikk er det reisende selgerproblemet , eller selgerproblemet , et optimaliseringsproblem som, gitt en liste over byer, og avstandene mellom alle par av byer, bestemmer en kortere krets som besøker hver by en gang og bare en gang.

Til tross for enkelheten i uttalelsen, er det et optimaliseringsproblem som vi ikke kjenner en algoritme som gjør det mulig å finne en nøyaktig løsning raskt i alle tilfeller. Mer presist, vi kjenner ikke en polynomisk tidsalgoritme , og dens avgjørelsesversjon ( for en avstand D, er det en sti kortere enn D som går gjennom alle byene og slutter i startbyen? ) Er et NP-komplett problem , som er en indikasjon på vanskeligheten.

Dette er et kjent algoritmisk problem , som har generert mye forskning og ofte brukes som en introduksjon til algoritmikk eller kompleksitetsteori . Den har mange anvendelser, enten i planlegging og logistikk, eller i fjernere felt som genetikk (erstatter byer med gener og avstand med likhet).

beskrivelse av problemet

Uttalelsen om den omreisende selgers problem er som følger: gitt n poeng (av "byer") og avstandene mellom hvert punkt, finn en bane med minimum total lengde som går nøyaktig en gang gjennom hvert punkt og returnerer til utgangspunktet. Formelt sett er en forekomst en komplett graf med et sett med hjørner, et sett med kanter og en kostnadsfunksjon på kantene . Problemet er å finne den korteste Hamilton-syklusen i grafen G. $G = (V, A, \ omega)$ $V$ $PÅ$ $\ omega$

Eksempel

Vi vurderer listen over byene A, B, C, D og avstandene som er gitt på tegningen nedenfor til venstre. En første sti som starter fra A, går tilbake til A og som besøker alle byene er ABDCA. En kortere vei er ACBDA. ACBDA-banen er optimal.

Kombinatorisk eksplosjon

Antall kandidatveier i henhold til antall byer

Antall byer $ikke$	Antall kandidatveier $\ frac {1} {2} (n-1)!$
3	1
4	3
5	12
6	60
7	360
8	2.520
9	20 160
10	181,440
15	43 589 145 600
20	6,082 × 10 16
71	5.989 × 10 99

Dette problemet er mer komplisert enn det ser ut til; det er ingen kjent løsningsmetode som gjør det mulig å oppnå nøyaktige løsninger i rimelig tid for store tilfeller (stort antall byer) av problemet. For disse store tilfellene vil vi derfor ofte måtte nøye oss med omtrentlige løsninger , fordi vi står overfor en kombinatorisk eksplosjon .

For et sett med poeng er det totalt mulige stier ( faktoriell av ). Utgangspunktet endrer ikke lengden på stien, vi kan velge denne vilkårlig, vi har altså forskjellige stier. Til slutt, siden hver sti kan beveges i to retninger og de to mulighetene har samme lengde, kan vi dele dette tallet med to. For eksempel, hvis vi navngir punktene ,, stiene abcd og dcba, cdab og badc, adcb og bcda, cbad og dabc har alle samme lengde; bare startpunktet og kjøreretningen endres. Vi har derfor kandidatveier å vurdere. $ikke$ $ikke!$ $ikke$ $(n-1)!$ $a, b, c, d$ ${\ displaystyle {\ frac {(n-1)!} {2}}}$

For eksempel for 71 byer er antall kandidatveier større enn 5 × 10 80, som er omtrent antall atomer i det kjente universet .

Varianter

Orientering

Ingenting hindrer grafen som er gitt som inndata fra å bli orientert. I dette tilfellet vurderer vi at en sti eksisterer i den ene retningen, men ikke i den andre (eksempel: enveis veier).

Asymmetri

Noen ganger snakker vi om et symmetrisk eller asymmetrisk problem.

Symmetrisk selgerproblem : Gitt et sett med noder og avstander for hvert noderpar, finn en syklus med minimum lengde som besøker hver node nøyaktig en gang. For og to noder av en kant, er avstanden fra til den samme som fra til . $ikke$ $Jeg$ $j$ $Jeg$ $j$ $j$ $Jeg$

Asymmetrisk selgerproblem : Gitt et sett med noder og avstander for hvert noderpar, finn en syklus med minimum lengde som besøker hver node nøyaktig en gang. Denne gang avstanden mellom to noder og en kant er ikke nødvendigvis er den samme uansett om vi kommer fra til eller fra til . $ikke$ $Jeg$ $j$ $Jeg$ $j$ $j$ $Jeg$

Også ulike operasjonelle forskningsproblemer er knyttet til den omreisende selgeren. En skruppelløs reisende selger ville være interessert i det dobbelte problemet med den korteste veien (for hans faktiske reise) og den lengste veien (for utgiftsrapporten).

Nøyaktig oppløsning

Kompleksiteten i problemet

Den avgjørelsen problem forbundet med den omreisende selger optimaliseringsproblem er en av Karp er 21 NP-komplette problemer . Papadimitriou demonstrerte i 1977 at problemet forblir NP-hardt, selv om avstandene er gitt av euklidiske avstander. Dermed forblir problemet NP-vanskelig selv om vi fjerner tilstanden "ikke gå gjennom en by på det meste en gang".

Algoritmer

En naiv tilnærming til oppløsning, men som gir et eksakt resultat, er opptellingen av alle mulige baner ved uttømmende søk . Den tid kompleksiteten av denne algoritmen er i (mer nøyaktig , noe som raskt blir upraktisk selv for små tilfeller. Hvis for eksempel beregning av en bane tar ett mikrosekund, og deretter beregning av alle banene for 10 poeng er 181,440 mikrosekunder eller 0,18 sek , men for 15 poeng representerer dette allerede 43.589.145.600 mikrosekunder, eller litt over 12 timer, og i 20 poeng på 6 × 10 16 mikrosekunder, eller nesten to årtusener (1.901 år). 25 byer overskrider beregningstiden universets alder . $Vi!)$ ${\ displaystyle {\ frac {(n-1)!} {2}}}$

Held og Karp har vist at dynamisk programmering løser problemet i . ${\ displaystyle O (n ^ {2} 2 ^ {n})}$

De lineære optimaliseringsmetodene er hittil blant de mest effektive for å løse det omreisende selgerproblemet og lar nå løse store problemer (i målestokk av et land), muligens med en beregningstid.

Spesielle tilfeller

Bitonic tur i en euklidisk graf

Når det gjelder en euklidisk graf, det vil si når kantene har vekt for avstandene mellom toppunktene som for eksempel er tilfelle mellom byer på et veikart, har visse varianter av problemet til handelsreisende en nøyaktig løsning som kan bestemmes i polynomisk tid . Dette er tilfelle når vi ser etter den raskeste bitoniske kretsen , der vi starter fra det vestligste punktet og alltid går østover til det østligste punktet før vi kommer tilbake. Ved startpunktet, alltid vestover. I dette spesielle tilfellet først introdusert av Jon Louis Bentley , kan en optimal løsning bestemmes av dynamisk programmering . $ikke$ $O (n ^ 2)$

Tilnærming

Generell sak

Generelt sett, og forutsatt at det ikke er noen tilnærmelsesalgoritme for å løse det reisende selgerproblemet. For å vise det fortsetter vi med det absurde forutsatt at det for en viss grad eksisterer en algoritme for tilnærming av faktorene . Vi viser da at denne tilnærmelsesalgoritmen gjør det mulig å løse problemet med søket etter en Hamilton-syklus i polynomisk tid, selv om den er NP-komplett. ${\ displaystyle {\ mathtt {P}} \ neq {\ mathtt {NP}}}$ $\ epsilon> 0$ ${\ displaystyle 1+ \ epsilon}$

Vi vurderer en graf , vi kan anta uten tap av allmenhet at alle kantene har vekt 1. Vi forvandler den til den komplette grafen ved å legge til mellom hvert par uforbundne hjørner en vektkant der hvor antall hjørner av . Hvis grafen har en Hamiltonian-krets, har den en minste vektrunde , ellers inneholder minimumsrunden minst en vektkant, og vekten er derfor minst . I det første tilfellet vil vår tilnærmelsesalgoritme i polynomtid finne en vekttur på det meste , i den andre vil den i det minste finne en vektvisning . Ettersom man kan skille mellom de to situasjonene i polynomial tid, følger det at eksistensen av en Hamiltonian-krets kan utføres i polynomial tid som resulterer i en motsetning; det er derfor ingen generell tilnærmingsalgoritme for å løse det reisende selgerproblemet. $G$ $G '$ $G$ ${\ displaystyle | S | (1+ \ epsilon) +1}$ $| S |$ $G$ $G$ $G '$ $| S |$ ${\ displaystyle | S | (1+ \ epsilon) +1}$ ${\ displaystyle | S | (1+ \ epsilon) +1+ | S | -1 = | S | (2+ \ epsilon)}$ ${\ displaystyle | S | (1+ \ epsilon)}$ ${\ displaystyle | S | (2+ \ epsilon)> | S | (1+ \ epsilon)}$

Metrisk sak

I noen tilfeller eksisterer tilnærmelsesalgoritmer , Christofides-algoritmen er en faktor 3/2 tilnærming i det metriske tilfellet, det vil si når vekten av kantene respekterer den trekantede ulikheten . I dette tilfellet er problemet APX-hardt selv med vekt 1 eller 2. Den beste nedre grensen for tilnærmelsesfaktoren er 123/122.

Et fortrykk av 2020 forbedrer faktoren med 3/2 - 10-36 .

Euklidisk sak

Når det gjelder en euklidisk beregning , er det et polynomisk tidsnærmetingsskjema . Det ble uavhengig oppdaget av Sanjeev Arora og Joseph SB Mitchell , og vant dem Gödelprisen i 2010.

Teknikker

Formulering ved lineær optimalisering

Følgende formalisering av problemet, i form av en lineær heltalloptimalisering av problemet, brukes til utforming av tilnærmelsesalgoritmer. Merk settet av kantene forlater toppunktet sett S . $\ delta (S)$

{\ displaystyle {\ begin {align} & {\ text {minimize}} && \ sum \ mathbf {c} _ {e} \ mathbf {x} _ {e} \\ & {\ text {for eksempel}} && \ mathbf {x (\ delta (S))} \ geq 2, {\ text {for ethvert delsett}} \ mathbf {S} {\ text {de}} \ mathbf {V}, \\ & {\ text { og}} && \ mathbf {x (\ delta (v))} \ geq 2, {\ text {for ethvert element}} \ mathbf {v} {\ text {de}} \ mathbf {V}, \ \ & {\ text {and}} && \ mathbf {x_ {e}} {\ text {in}} \ mathbf {0,1} \\\ end {aligned}}}

Avslapningen av dette programmet for et lineært optimaliseringsproblem (det vil si uten begrensninger av integritet ) kalles Held and Karp avslapning eller subtour LP . Denne avslapningen har et eksponentielt antall begrensninger, men kan løses på polynomtid ved å løse separasjonsproblemet , som viser seg å være beregningen av et minimumskutt .

Det antas at Held og Karp-avslapningen har et integritetsgap på 4/3.

Faktor 2-tilnærming ved hjelp av spennende trær

Christofides-algoritmen er basert på en enkel faktor 2 tilnærmelsesalgoritme som bruker forestillingen om et spennende tre med minimal vekt . Ettersom en hvilken som helst tur har en kumulativ vekt som er større enn den for det minimale spennende treet, og siden en prefiksbane for treet passerer to ganger gjennom hver av de interne nodene, har en tur som følger en prefiksbane en kumulativ vekt mindre enn det dobbelte av løsningen minimal til den omreisende selgers problem. Det gjenstår å konvertere denne ruten til en rute som går en gang og bare en gang gjennom hver av toppunktene i grafen. Deretter utnytter vi den trekantede ulikheten: Hvis ruten mellom to toppmøter går gjennom et allerede besøkt mellomtoppmøte, hopper vi over det for å gå direkte til det første toppmøtet som ennå ikke er besøkt. Den trekantede ulikheten sørger da for at reisens totale vekt ikke øker; følgelig får vi en Hamiltonian-krets med en vekt som er mindre enn det dobbelte av minimumskretsen.

Heuristikk

På grunn av problemets innledende kompleksitet ( ), dets betydning og NP-fullstendighet, har mange heuristikker blitt foreslått. $Vi!)$

Lokal søkeheuristikk

En klassisk heuristikk, kalt 2-opt, er et lokalt søk som består av å starte fra en løsning og prøve å forbedre den ved iterativt å bytte hjørnene i to kanter. Den heuristiske Lin-Kernighan er en forbedring.

En annen lokal søkeheuristikk kalt Ruin and Recreate , nær simulert annealing , er å starte fra en løsning, ødelegge en region av den og deretter gjenskape den ved å forbedre den.

Meta-heuristikk

De genetiske algoritmene kan også tilpasses Travellerselgerproblemet. Ideen ble først foreslått av John Holland tidlig på 1970-tallet.

Grådige heuristikker

For det omreisende selgerproblemet , konstruerer en grådig heuristikk en enkelt løsning, ved en rekke endelige avgjørelser uten tilbakesporing, blant disse metodene siterer vi nærmeste nabo, nærmeste innsetting, fjerneste innsetting og beste innsetting.

I den nærmeste nabometoden starter vi fra et hvilket som helst toppunkt og ved hver av iterasjonene kobler vi det siste toppunktet som er nådd til det nærmeste toppunktet i en kostnadsforståelse, så kobler vi endelig det siste toppunktet til det først valgte toppunktet. $(n-1)$

I innsettingsmetodene starter vi fra en syklus redusert til en sløyfe i starten, ved hver iterasjon velger vi et gratis toppunkt, så ser vi etter innsettings- og syklusposisjonen som minimerer den totale økningen i kostnader: $j$ $Jeg$ $j$

i den fjerneste innsettingen er det frie toppunktet lengst fra syklusen i form av kostnader; $j$
i nærmeste innsetting er nærmest syklusen; $j$
til slutt i den beste innsettingen tester vi alle hjørnene som ennå ikke er satt inn, og vi velger den som gir den minste økningen i kostnad. $j$

Historie og betydning

Opprinnelse og spesielle tilfeller

Prinsippet om en slik tur ble beskrevet allerede i 1832, skriftlig av en selger, og effektive ruter ble referert til i guider. Flere gamle problemer kan sees på som spesielle tilfeller av problemet; for eksempel, i 1856, var William Rowan Hamilton interessert i et geometrisk problem av denne typen på en dodekaeder , dessuten betegner begrepet Hamilton-syklus en syklus som går gjennom alle toppunktene i en graf.

Terminologi

Begrepet omreisende selgerproblem kommer fra oversettelsen av det amerikanske engelsk omreisende selgerproblemet , som dukket opp på 1930- eller 1940-tallet, sannsynligvis ved Princeton University hvor flere forskere var interessert i det. Det var også i denne perioden at problemet ble formulert uavhengig i flere forskningsmiljøer, spesielt rundt Karl Menger .

Utvikling

Problemet interesserte da et bredere samfunn og var spesielt opphavet til oppdagelsen av flere teknikker, som blandet lineær optimalisering ( blandet heltallsprogrammering ) og metoden for separasjon og evaluering ( gren-og-bundet ).

I 1972 viste Richard Karp at det tilhørende beslutningsproblemet er NP-komplett .

Viktigheten i undervisning og forskning

Den omreisende selgeren er et av de mest studerte algoritmiske problemene i dag. Videre, på grunn av enkelheten i uttalelsen, brukes den ofte til å introdusere algoritmer, derav en relativ kjendis.

Varianter

PTSP-varianten (for fysisk reisendeselgerproblem) består i å besøke et endelig antall en gang og bare en gang i et 2D-miljø med hindringer. MTSP-varianten (for flere reisende selgerproblemer) generaliserer problemet til flere reisende, og selve generaliserer til rutingproblemet for kjøretøyet .

applikasjoner

Det omreisende selgerproblemet har mange applikasjoner, og har dessuten vært motivert av konkrete problemer, for eksempel ruten til skolebusser.

En første type klassisk applikasjon er selvfølgelig innen logistikk , for eksempel for postkontoret , distribusjon av måltider hjemme, installasjonskontroll osv. Det er også mulig å optimalisere maskinens bevegelser, for eksempel for å minimere den totale tiden det tar en CNC-fresemaskin å bore n punkter i et metallplate, eller minimere bevegelsene til store teleskoper (som er veldig sakte).

Vi kan sitere mer overraskende bruksområder, for eksempel: i biologi hjelper problemet med genomsekvensering (for å koble små fragmenter til større kjeder), og i produksjonen brukes det til å teste trykte kretser .

Merknader og referanser

Merknader

Vanligvis gjennom filial og kutt metode .

Referanser

" TERMIUM Plus," reisende selgerproblem " , på btb.termiumplus.gc.ca (åpnet 14. august 2016 ) .
Vi gir her en geometrisk intuisjon. Men det reisende selgerproblemet tar som input en matrise over avstander som ikke nødvendigvis tilfredsstiller den trekantede ulikheten. Det metriske tilfellet (hvor den trekantede ulikheten holder) og det euklidiske tilfellet blir diskutert senere i artikkelen.
Patrick Siarry , Metaheuristics: simulert herding søke med tabu, variable området i søk, grep metoder, evolusjonære algoritmer, kunstige maur, partikkel svermer og andre optimaliseringsmetoder , Eyrolles ,26. mars 2014, 534 s. ( ISBN 978-2-212-26621-4 , leses online ) , s. 182.
Vi kan estimere størrelsesorden for antall atomer i universet til 10 80 .
Present spesielt i listen over 21 NP-komplette problemer med Karp : (en) Richard M. Karp , “reduserbarheten Blant Kombi problemer” , i Raymond E. Miller og James W. Thatcher, Complexity of Computer beregninger , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , les online ) , s. 85-103.
(in) " The Euclidean travelling salesman problem is NP-complete " , Theoretical Computer Science , vol. 4, n o 3,1 st juni 1977, s. 237–244 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (77) 90012-3 , leses online , åpnes 13. september 2018 )
(in) Mr. Held og RM Karp, " A Dynamic Programming Approach to Sequencing Problems ," Journal of the Society for Industrial and Applied Mathematics , 1962, 10 (1), 196-210.
(in) Se for eksempel Georgia Tech universitetsnettsted .
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein ( overs. Fra engelsk), algoritmer : Foredrag med øvelser 957 og 158 oppgaver , Dunod ,2010[ detalj av utgaven ], kap. 15 ("Dynamisk programmering"), s. 375.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein ( overs. Fra engelsk), Algoritmer : Foredrag med øvelser 957 og 158 oppgaver , Dunod ,2010[ detalj av utgaven ], kap. 35: Tilnærmelsesalgoritmer.
Nicos Christofides , “ Worst-case analyse of a new heuristic for the travelling salesman problem ”, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University , Pittsburgh ,1976.
Christos H. Papadimitriou og Mihalis Yannakakis , “ The handelsreisende problem med avstander ett og to ”, Mathematics of Operations Research , INFORMS, vol. 18, n o 1, 1993, s. 1--11.
(in) " New inapproximability grenser for TSP " , Journal of Computer and System Sciences , vol. 81, n o 8,1 st desember 2015, s. 1665–1677 ( ISSN 0022-0000 , DOI 10.1016 / j.jcss.2015.06.003 , les online , åpnet 11. oktober 2020 ).
Anna R. Karlin , Nathan Klein og trachoma Oveis Gharan , “ A (litt) Forbedret Approximation Algoritme for beregning TSP ”, arxiv: 2007,01409 [cs, matte] ,30. august 2020( les online ).
(in) Erica Klarreich , " Computer Scientists Break Record Travelling Salesperson " på Quanta Magazine (åpnet 11. oktober 2020 ) .
Sanjeev Arora , “ Polynomial time approximation schemes for Euklidean travelling salesman and other geometric problems ”, Journal of the ACM , vol. 45, n o 5,1998, s. 753–782 ( DOI 10.1145 / 290179.290180 ).
Joseph SB Mitchell , “ Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems ”, SIAM Journal on Computing , vol. 28, nr . 4,1999, s. 1 298–1 309 ( ISSN 1095-7111 , DOI 10.1137 / S0097539796309764 ).
" The Gödel Prisen 2010, Laudatio for S. Arora og JSB Mitchell " , på EATCS .
Robert D. Carr og Santosh Vempala, “ On the Held-Karp afslapning for de asymmetriske og symmetriske omreisende selgerproblemer ”, Math. Program. , vol. 100, n o 3, 2004, s. 569-587.
Rene Beier, “ The Travelling Salesman Problem, the Subtour LP, and the Held-Karp Lower Bound, ” på MPII .
(i) S. Lin og BW Kernighan (1973), " An Effektiv Heuristic Algorithm for the Traveling Salesman Problem, " Operations Res. 21, 498-516.
(in) G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt og G. Dueck, " Record Breaking Results Optimization Using the Principle Ruin and Recreate " Journal of Computational Physics 159, 2000, 139-171.
(i) JH Holland, tilpasning i naturlige og kunstige Systems , University of Michigan Press ( 1975 ).
David L. Applegate, Robert E. Bixby, Václav Chvátal og William J. Cook, kap. 1 “Problemet” , i Det omreisende selgerproblemet: En beregningsstudie , Princeton University Press , 2006.
(in) Richard M. Karp , "reducibility Among Combinatorial Problems" i Raymond E. Miller og James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN 978-1-4684-2003-6 , DOI 10.1007 / 978-1-4684-2001-2_9 , les online ) , s. 85-103.
(en-US) “ Løsning av det fysiske reisende selgerproblemet: treesøk og makrohandlinger - IEEE Journals & Magazine ” , på ieeexplore.ieee.org (åpnet 16. juli 2018 )
(in) " The multiple travelling salesman problem: an overview of formulations and procedures solution " , Omega , Vol. 34, n o 3,1 st juni 2006, s. 209–219 ( ISSN 0305-0483 , DOI 10.1016 / j.omega.2004.10.004 , leses online , åpnes 13. september 2018 )
David L. Applegate, Robert E. Bixby, Václav Chvátal and William J. Cook, kap. 2 “Applications” , i The Travelling Salesman Problem: A Computational Study , Princeton University Press ,2006.
(i) William Timothy Gowers (red.), Kap. VII.5 "Innflytelsen av matematikk: Matematikken for algoritmedesign" , i The Princeton-følgesvenn til matematikk , Princeton og Oxford, Princeton University Press,2008( ISBN 978-0-691-11880-2 ) , s. 871-878.

Se også

Relaterte artikler

Eksterne linker

Java-applet, som illustrerer det reisende selgerproblemet
tsplib, et bibliotek som gir eksempler på problemet
concorde, en programvare som kan løse forekomster av problemet
En applet som bruker google maps api, som løser forekomster av problemet
TSP Solver med BING Maps løser TSP og TSPTW.
simulert annealing for den omreisende selgeren, online applikasjon
Approximation Taxonomy of Metric TSP ved Universitetet i Bonn
TSP i urban logistikk (en) " Et bidrag til å løse det reisende selgerproblemet ved bruk av maurkolonioptimalisering og nettkartplattformer : Søknad til logistikk i urbane sammenheng " , Codit14 , IEEE,september 2014, s. 7 ( ISBN 978-1-4799-6773-5 , leses online )