Problemet med den rejsende sælger

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. juni 2022; checks kræver 7 redigeringer .

Det rejsende sælgerproblem (eller TSP fra det engelske traveling salesman problem ) er et af de mest berømte kombinatoriske optimeringsproblemer , som består i at finde den mest profitable rute, der passerer gennem de angivne byer mindst én gang og derefter vende tilbage til den oprindelige by. Under problemets betingelser er ruterentabilitetskriteriet (det korteste, billigste, kumulative kriterium osv.) og de tilsvarende matricer for afstande, omkostninger og lignende angivet. Som regel er det angivet, at ruten kun skal passere gennem hver by én gang - i dette tilfælde træffes valget blandt de Hamiltonske cykler. Der er flere specielle tilfælde af den generelle formulering af problemet, især problemet med geometriske rejsende sælger (også kaldet plan eller euklidisk, når afstandsmatrixen afspejler afstandene mellem punkter på flyet), det metriske rejsende sælgerproblem (når trekantulighed er opfyldt på omkostningsmatrixen ), symmetriske og asymmetriske rejsende sælgerproblemer . Der er også en generalisering af problemet, det såkaldte generaliserede rejsende sælgerproblem .

Optimeringsproblemformuleringen hører dog til klassen af NP-hårde problemer, ligesom de fleste af dens særlige tilfælde. Den version af "beslutningsproblemet" (det vil sige en, der spørger, om der er en rute, der ikke er længere end en given værdi af k ) tilhører klassen af NP-komplette problemer . Problemet med den rejsende sælger er et af omregningsproblemerne : selv med et relativt lille antal byer (> 66) kan det ikke løses ved hjælp af metoden med opregning af muligheder af nogen teoretisk tænkelige computere på en tid mindre end flere milliarder år.

Historie

Relateret til den rejsende sælger problemet er problemet med at finde en Hamiltonian cyklus . Et eksempel på et sådant problem er problemet med ridderens træk , kendt i hvert fald siden det 18. århundrede [1] . Leonhard Euler dedikerede hende et stort værk "Løsningen af et kuriøst spørgsmål, som ikke synes at være genstand for nogen forskning," dateret 1759 [2] . Et andet eksempel på et problem med at finde en Hamiltonsk cyklus er icosian : et matematisk puslespil, hvor du skal gennem et dodecahedron (en graf med 20 noder) og besøge hvert toppunkt nøjagtigt én gang. Dette problem blev foreslået af William Hamilton i det 19. århundrede, han definerede også en klasse af sådanne stier.

I 1832 udkom en bog med titlen "Rejsende sælger - hvordan han skulle opføre sig, og hvad han skulle gøre for at levere varer og få succes i sine affærer - råd fra en gammel kurer" ( tysk: Der Handlungsreisende - wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein - von einem alten Commis-Voyageur ), som beskriver problemet, men ikke bruger det matematiske apparat til at løse det. Men det giver eksempler på ruter for nogle regioner i Tyskland og Schweiz.

De første omtaler som et matematisk optimeringsproblem tilhører Carl Menger , som formulerede det på et matematisk kollokvium i 1930 som følger:

Vi kalder budbringerproblemet (da dette spørgsmål opstår for hvert postbud, især mange rejsende løser det) problemet med at finde den korteste vej mellem et begrænset sæt af steder, hvor afstanden er kendt.

Snart dukkede det velkendte navn på det rejsende sælgerproblem op , som blev foreslået af Hassler Whitney fra Princeton University .

Sammen med den nemme definition og den relative lethed ved at finde gode løsninger, er problemet med den rejsende sælger anderledes, fordi det er en ret vanskelig opgave at finde en virkelig optimal vej. I betragtning af disse egenskaber, fra anden halvdel af det 20. århundrede, har studiet af rejsende sælgerproblemet ikke så meget praktisk betydning, men teoretisk som en model for udvikling af nye optimeringsalgoritmer.

Mange af nutidens almindelige diskrete optimeringsmetoder , såsom cutoff , branch and bound , og forskellige varianter af heuristiske algoritmer, er blevet udviklet ved at bruge problemet med rejsende sælger som eksempel.

I 1950'erne og 1960'erne tiltrak problemet med rejsende sælger opmærksomhed fra videnskabsmænd i USA og Europa. Et vigtigt bidrag til undersøgelsen af problemet tilhører George Danzig , Delbert Ray Fulkerson ( eng. Delbert Ray Fulkerson ) og Selmer Johnson ( eng. Selmer M. Johnson ), som i 1954 ved RAND Corporation- instituttet formulerede problemet i formen af et diskret optimeringsproblem og anvendt til at løse cut-off-metoden . Ved hjælp af denne metode byggede de en rejsende sælgers vej for en bestemt problemformulering med 49 byer og underbyggede dens optimalitet. I 1960'erne og 1970'erne blev problemet undersøgt af mange videnskabsmænd både teoretisk og med hensyn til dets anvendelser inden for datalogi, økonomi, kemi og biologi.

Richard Karp beviste i 1972 NP-fuldstændigheden af problemet med at finde Hamiltonske stier, som takket være polynomiel reduktionsevne antydede NP-hårdheden af det rejsende sælgerproblem. Ud fra disse egenskaber gav han en teoretisk begrundelse for kompleksiteten i at finde løsninger på problemet i praksis.

Store succeser blev opnået i slutningen af 1970'erne og 1980'erne, da Martin Grötschel ( tyske Martin Grötschel ), Manfred Padberg ( tyske Manfred Padberg ) og Giovanni Rinaldi ( italienske Giovanni Rinaldi ) og andre ved hjælp af nye divisionsmetoder plan, grene og grænser beregnede løsningen for et særligt tilfælde af problemet med 2393 byer.

I 1990'erne satte David Applegate , Robert Bixby , Vašek Chvátal og William Cook rekorder for Concorde-programmet . Gerhard Reinelt ( tysk Gerhard Reinelt ) skabte TSPLIB - et sæt standardiserede forekomster af det rejsende sælgerproblem af varierende grad af kompleksitet for at sammenligne resultaterne af forskellige grupper af forskeres arbejde. I marts 2005 blev et problem med 33.810 noder løst af Concord -programmet : en sti med længden 66.048.945 blev beregnet, og fraværet af kortere stier blev bevist. I april 2006 blev der fundet en løsning for en instans med 85.900 noder. Ved hjælp af nedbrydningsmetoder er det muligt at beregne løsninger til tilfælde af et problem med millioner af knudepunkter, hvis længde er mindre end 1% mere end den optimale.

Formel definition

Grafrepræsentation

For at kunne bruge det matematiske apparat til at løse problemet, skal det præsenteres i form af en matematisk model . Problemet med den rejsende sælger kan repræsenteres som en model på en graf , det vil sige ved at bruge spidser og kanter mellem dem. Grafens toppunkter svarer således til byer, og kanterne mellem toppunkterne og svarer til kommunikationsvejene mellem disse byer. Hver kant kan knyttes til et ruterentabilitetskriterium , som for eksempel kan forstås som afstanden mellem byer, rejsens tid eller pris. $\venstre(i,j\højre)$ $jeg$ $j$ $\venstre(i,j\højre)$ $c_{ij}\geqslant 0$

En Hamilton-cyklus er en sti, der inkluderer nøjagtigt én gang hvert hjørne af grafen.

For at forenkle problemet og garantere eksistensen af en rute, antages det normalt, at modelgrafen for problemet er fuldt forbundet , det vil sige, at der er en kant mellem et vilkårligt par af hjørner. I de tilfælde, hvor der ikke er kommunikation mellem de enkelte byer, kan dette opnås ved at indføre kanter med en maksimal længde. På grund af den store længde vil en sådan kant aldrig falde ind i den optimale rute, hvis den findes.

Løsningen på det rejsende sælgerproblem er således at finde den Hamiltonske cyklus med minimumvægt i en komplet vægtet graf.

Afhængigt af hvilket ruterentabilitetskriterium der sammenlignes med kanternes størrelse, findes der forskellige versioner af problemet, hvoraf de vigtigste er de symmetriske og metriske problemer.

Asymmetriske og symmetriske problemer

Generelt adskiller det asymmetriske rejsende sælgerproblem sig ved, at det er modelleret af en rettet graf. Således bør man også overveje, hvilken retning kanterne er i.

I tilfælde af et symmetrisk problem har alle par af kanter mellem de samme hjørner den samme længde, det vil sige, at længderne for kanten er de samme . I det symmetriske tilfælde er antallet af mulige ruter halvdelen af det asymmetriske tilfælde. Det symmetriske problem er modelleret af en urettet graf (se figur). $\venstre(i,j\højre)$ $c_{ij}=c_{ji}$

Faktisk kan problemet med rejsende sælger i tilfælde af rigtige byer være både symmetrisk og asymmetrisk, afhængigt af ruternes varighed eller længde og bevægelsesretningen.

Metrisk problem

Et symmetrisk rejsende sælgerproblem kaldes metrisk , hvis trekantens ulighed er opfyldt med hensyn til længderne af kanterne . Relativt set er omveje i sådanne problemer længere end lige linjer, det vil sige, at kanten fra toppunkt til toppunkt aldrig er længere end vejen gennem det mellemliggende toppunkt : $jeg$ $j$ $k$

c_{ij}\leqslant c_{ik}+c_{kj}

Denne kantlængdeegenskab definerer et målbart rum på sættet af kanter og et afstandsmål, der tilfredsstiller den intuitive forståelse af afstand.

Afstandsfunktioner, der er almindelige i praksis, er også metrikker og opfylder trekantens ulighed:

Euklidisk afstand i det euklidiske rejsende sælgerproblem,
Manhattan-metrikken (også kvartalsmetrik) for det rektangulære rejsende sælgerproblem, hvor afstanden mellem hjørner på gitteret er lig med summen af afstandene langs y-aksen og abscissen,
Den maksimale metrik , der definerer afstanden mellem hjørnerne af en gittergraf som den maksimale værdi af afstanden langs ordinaten og abscissen.

De sidste to metrikker bruges for eksempel ved boring af huller i printplader, når maskinen skal lave flere huller på mindst tid og kan flytte boret i begge retninger for at flytte fra et hul til det næste. Manhattan-metrikken svarer til det tilfælde, hvor bevægelse i begge retninger sker sekventielt, og maksimum svarer til tilfældet, når bevægelse i begge retninger sker synkront, og den samlede tid er lig med den maksimale bevægelsestid langs ordinat- eller abscisseaksen.

Det ikke-metriske rejsende sælgerproblem kan for eksempel opstå i tilfælde af at minimere opholdets varighed i nærværelse af et udvalg af køretøjer i forskellige retninger. I et sådant tilfælde kan omvejen med fly være kortere end den direkte forbindelse med bil.

Hvis det i praksis under problemets betingelser er tilladt at besøge byer flere gange, så kan det symmetriske problem reduceres til et metrisk. Hertil betragtes problemet på den såkaldte afstandsgraf. Denne graf har det samme sæt toppunkter som den originale og er fuldt forbundet. Længden af kanterne mellem spidserne og på afstandsgrafen svarer til længden af den korteste afstand mellem spidserne og i den originale graf. For længder defineret på denne måde gælder trekantuligheden, og hver rute på afstandsgrafen svarer altid til en rute med mulige gentagelser af hjørner i den originale graf. $c_{ij}$ $jeg$ $j$ $jeg$ $j$ $c_{ij}$

Formulering som et diskret optimeringsproblem

En af tilgangene til at løse problemet er at formulere det som et diskret optimeringsproblem, med løsningerne repræsenteret som variable, og sammenhængene som ulighedsrelationer mellem dem. Der er således flere muligheder. For eksempel kan et symmetrisk problem repræsenteres som et sæt kanter . Hver kant tildeles en binær variabel , lig med 1, hvis kanten hører til ruten, og 0 ellers. En vilkårlig rute kan repræsenteres som værdier af et sæt medlemsvariabler, men ikke alle sådanne sæt definerer en rute. Betingelsen for, at værdierne af sættet af variabler bestemmer ruten, er de lineære uligheder beskrevet nedenfor. $V$ $\{i,j\}$ $x_{ij}\in \{0,1\}$

Hvert toppunkt skal kommunikere gennem et par kanter med resten af toppunkterne, det vil sige gennem input- og outputkanterne:

\forall i\in V,\;\sum _{j\in V\setminus \{i\}}x_{ij}=2\qquad (1)

I alt er hvert led lig med enten 1 (tilhører ruten) eller 0 (tilhører ikke). Det vil sige, at den resulterende sum er lig med antallet af kanter i ruten, der har et toppunkt i en af enderne. Det er lig med 2, da hvert toppunkt har en input- og outputkant. På den tilstødende figur er toppunktet vist med input- og outputkanter, og rutekanter er vist som tykke linjer. Ved siden af ribberne er længderne påført til ovenstående mængde. $x_{ij}$ $jeg$ $jeg$ $x_{ij}$

De tidligere beskrevne multiplicitetsbetingelser opfyldes ikke kun af ruter, men også af værdierne af variabler svarende til individuelle cyklusser, hvor hvert toppunkt kun tilhører én cyklus (se figur). For at undgå sådanne tilfælde skal de såkaldte loop-uligheder (eller subroute-elimineringsbetingelser), som blev defineret af Danzig, Fulkerson og Johnson i 1954 under navnet loop conditions , være opfyldt . Disse uligheder definerede en yderligere betingelse om, at hvert sæt af hjørner enten er tomt eller indeholder alle hjørner, kombineret med resten af hjørnerne gennem mindst to kanter: $S\undersæt V$

\sum _{i\in S,\;j\notin S}x_{ij}\geqslant 2\qquad (2)

for alle sæt af hjørner , hvor . Denne sum er lig med summen af længderne af banekanterne mellem toppunkt og toppunkt . For at eliminere unødvendige uligheder kan vi begrænse os til sæt af hjørner med et minimum af to og et maksimum af hjørner. På figuren ved siden af er kanter med længder markeret med tykke linjer, de resterende kanter har længde . Indførelsen af yderligere betingelser (2) for toppunktet , bestående af tre venstre hjørner, vil sikre, at det kombineres gennem mindst to banekanter med tre spidser til højre for at eliminere begge cyklusser. Antallet af cyklus-eliminerende uligheder ifølge Danzig, Fulkerson og Johnson er . $S$ $1\leqslant |S|\leqslant |V|-1$ $i\i S$ $j\notin S$ $S$ $|V|-2$ $\{i,j\}$ $x_{ij}=1$ $x_{ij}=0$ $S$ $S$ $2^{n}-2(n-1)$

I 1960 udtænkte Miller, Tucker og Zemlin alternative betingelser for at eliminere underruter ved at indføre nye variabler, der specificerede rækkefølgen af besøgte byer, hvilket kun kræver yderligere uligheder. På grund af dualiteten i formuleringerne af Miller, Tucker og Zemlin er problemet med den rejsende sælger desuden NP-hårdt. $n$ $n^{2}-n+1$ $x_{ij}$

Hver vektor med elementer lig med 0 og 1, der opfylder alle uligheder, definerer således en korrekt rute, som er en løsning på det omformulerede rejsende sælgerproblem: beregn

\min \;\venstre\{\sum _{i\in V}\sum _{j\in V\setminus \{i\}}c_{ij}x_{ij}\;|\;x{\mbox { gyldig (1) (2),}}\;x_{ij}\in \{0,1\}\right\}.\qquad (3)

Da variablerne kun har værdierne 0 og 1, er summen lig med den samlede længde af de kanter , der hører til ruten. $x_{ij}$ $c_{ij}$ $\{i,j\}$

Antallet af uligheder af typen (2) vokser eksponentielt , efterhånden som antallet af byer stiger, da næsten hver delmængde af noder definerer en ulighed. Dette problem kan løses ved at anvende klippeplanmetoden , på grund af hvilken uligheder kun tilføjes, når disse uligheder virkelig er nødvendige. Fra et geometrisk synspunkt kan lineære uligheder repræsenteres som hyperplaner i variables rum. Sættet af vektorer, der opfylder disse uligheder, danner en polytop (multidimensional polyhedron), eller multidimensional polygon, i et sådant rum, den nøjagtige form er bestemt af længderne og er for det meste ukendt. Det kan dog påvises, at betingelserne (1) og (2) bestemmer polytopens flader (facet), det vil sige sidefladerne af polytopen med den højeste dimension. Derfor er de blandt de stærkeste lineære uligheder, der kan beskrive en rute. Der er også mange forskellige facetter defineret af uligheder, der kun kendes i nogle få tilfælde. Selvom (1) og (2) sammen med begrænsningerne udelukkende modellerer problemet for binære vektorer, kan disse uligheder bruges i branch and bound-metoden til at kassere løsninger ved lineære optimeringsmetoder med ikke-heltalskoordinater (se afsnittet om nøjagtige metoder). under). $2^{|V|}$ $c_{ij}$

Algoritmisk kompleksitet

Da den rejsende sælger i hver by står over for valget af den næste by blandt dem, han endnu ikke har besøgt, er der ruter for den asymmetriske og ruter for den symmetriske rejsende sælger-problemet. Størrelsen af søgerummet afhænger således faktorielt af antallet af byer. $(n-1)!$ $(n-1)!/2$

Forskellige versioner af problemet med rejsende sælger (metrisk, symmetrisk og asymmetrisk) er NP-ækvivalente. Ifølge den almindelige, men ubeviste formodning om uligheden i kompleksitetsklasserne P og NP, er der ingen deterministisk Turing-maskine , der er i stand til at løse problemforekomster i polynomisk tid afhængigt af antallet af byer.

Det er også kendt, at der under betingelsen ikke er nogen algoritme, der for nogle polynomier ville beregne sådanne løsninger på det rejsende sælgerproblem, som ville afvige fra det optimale maksimum med en faktor . $P\neq NP$ $s$ $2^{p(n)}$

I praksis er det ikke altid nødvendigt at søge efter en strengt optimal rute. Der findes algoritmer til at finde omtrentlige løsninger på et metrisk problem i polynomisk tid og finde en rute, der højst er dobbelt så lang som den optimale. Indtil videre kendes ingen polynomiel tidsalgoritme, der ville garantere en nøjagtighed bedre end 1,5 af den optimale. Ved antagelse eksisterer der en (ukendt) konstant , således at ingen polynomiel-tidsalgoritme kan garantere nøjagtighed . Som Arora har vist, er der for det euklidiske rejsende sælgerproblem et polynomisk tids -PTAS-skema til at finde en omtrentlig løsning. $P\neq NP$ $c>0$ $1+c$

Derudover kan dataene have funktioner, der kan hjælpe med at løse problemet. For eksempel ligger byer ikke tilfældigt, men efter terrænet, eller endda langs den optimale handelsrute, der længe er blevet fundet. Yderligere information og heuristik giver os mulighed for at finde acceptable løsninger inden for rimelig tid.

Lukkede og åbne varianter af problemet

I den lukkede version af problemet med den rejsende sælger er det påkrævet at besøge alle hjørnerne af grafen og derefter vende tilbage til det oprindelige toppunkt. Den åbne variant adskiller sig fra den lukkede ved, at den ikke kræver tilbagevenden til startspidsen.

En åben version af problemet reduceres til en lukket ved at erstatte vægten af de buer, der indgår i startspidsen, med tallet 0. Den optimale lukkede rejsende sælgerrute i en sådan graf svarer til den optimale åbne rute i den originale graf.

For at reducere en lukket variant til en ikke-lukket, er det nødvendigt at bestemme et tal, der strengt taget overstiger vægten af enhver rejsende sælgerrute i en given graf (f.eks. kan du tage summen af de maksimale vægtbuer, der udgår fra hvert toppunkt , forhøjet med 1). Derefter skal du tilføje et nyt toppunkt til grafen (vi antager, at toppunkterne på den originale graf er nummereret fra 0 til , mens startpunktet har nummer 0). Omkostningerne ved buer, der forlader og kommer ind i toppunktet , er defineret som følger: $K$ $K$ $v_{n}$ $n-1$ $v_{n}$

$c_{n,i}=3K$
$c_{0,n}=3K$
$c_{i,n}=c_{i,0}+2K$ kl fra til $jeg$ $en$ $n-1$

Den optimale ikke-lukkede rejsende sælgerrute i en sådan graf svarer til den optimale lukkede rejsende sælgerrute i den originale graf og har en højere omkostning. $2K$

Løsningsmetoder

Protozoer

udtømmende søgning
tilfældig opregning
grådige algoritmer
- nærmeste nabo metode
- nærmeste byinklusionsmetode
- billigste metode
minimum spanning tree metode
simuleret udglødningsmetode

Alle effektive (reducerende fuld opregning) metoder til at løse problemet med den rejsende sælger er heuristiske metoder . De fleste heuristiske metoder finder ikke den mest effektive rute, men en omtrentlig løsning . Såkaldte når som helst algoritmer er ofte efterspurgte .[ klargør ] , det vil sige gradvist at forbedre en eller anden nuværende omtrentlig løsning.

Et eksempel på den enkleste metode til at løse den metriske version af problemet er brugen af minimumspændende træer, som giver en løsning med en tilnærmelsesfaktor og har tidskompleksitet . Ideen er, at hver tilsluttet graf indeholder en lavere omkostningstærskel for sin undergraf, minimumspændingstræet, og at enhver cyklus, der besøger hvert grafvertex mindst én gang, kan transformeres til en omkostningsoptimal rute ved hjælp af metrikken: $2$ $O(n^{2}\log n)$

Find det mindste spændingstræ på grafen . $T$ $G$
Lav en graf ved at fordoble alle kanter i . Så alle hjørner i har et lige antal kanter. $T'$ $T$ $T'$
Find Euler-cyklussen . $T'$ $C'$
Reducer , spring over fordoblede kanter, få en cyklus . $C'$ $C$
Tag ud . $C$

Værdien af tilnærmelsesfaktoren bevises som følger: Lad - det mindste spændingstræ, - det samme træ, men med fordoblede kanter, - Euler-cyklussen på grafen , - resultatet af algoritmen, - minimumsruten. Bemærk at , samt . Så er tilnærmelsesfaktoren . $T$ $T'$ $C'$ $T'$ $C$ $C^{*}$ $c(T)\leqslant c(C^{*}-e)\leqslant c(C^{*})$ $c(C)\leqslant c(C')=2\cdot c(T)$ ${\frac {C}{C^{*}}}\leqslant {\frac {2\cdot c(T)}{c(C^{*})))\leqslant {\frac {2\ cdot c(C^{*})}{c(C^{*})}}=2$

Ovenstående metode kan dog optimeres ved at øge antallet af kanter ved toppunkter med et ulige antal naboer med 1, hvilket svarer til matchende "ulige" toppunkter. Det er vigtigt at bemærke, at antallet af "ulige" hjørner altid er lige, baseret på håndtrykslemmaet . I et sådant tilfælde har den optimerede algoritme en tilnærmelsesfaktor og tidskompleksitet . Før beviset, lad os vise, at , hvor er en matchning og er en optimal rute: Lad være sættet af "ulige" hjørner af minimumspændingstræet , og være en cyklus opnået fra ved at springe hjørner over . Naturligvis har en lige længde, samt to ikke-skærende maksimale matchninger og , for hvilke og . Det følger heraf , at og dermed . Ud fra dette finder vi algoritmens tilnærmelsesfaktor: . $3/2$ $O(n^{3})$ $c(M)\leqslant c(C^{*})/2$ $M$ $C^{*}$ $U$ $T$ $C''$ $C^{*}$ $V\setminus U$ $C''$ $M_{1}$ $M_{2}$ $c(M)\leqslant c(M_{1})$ $c(M)\leqslant c(M_{2})$ $2\cdot c(M)\leqslant c(M_{1})+c(M_{2})=c(C'')\leqslant c(C^{*})$ $c(M)\leqslant c(C^{*})/2$ ${\frac {c(C)}{c(C^{*})}}\leqslant {\frac {c(T)+c(M)}{c(C^{*})}} \leqslant {\frac {c(C^{*})+c(C^{*})/2}{c(C^{*})}}\leqslant {\frac {1.5\cdot c(C^ {*})}{c(C^{*})}}=1,5$

Der er også indstillinger, hvor problemet med rejsende sælger bliver NP-komplet . Normalt ser sådanne udsagn sådan ud: er der sådan en tur på en given graf G , at dens pris ikke overstiger x . Ofte testes nye tilgange til heuristisk reduktion af udtømmende søgning på det .

I praksis bruges forskellige modifikationer af mere effektive metoder: branch and bound- metoden og metoden for genetiske algoritmer , såvel som myrekolonialgoritmen .

Filial og bundet metode

Det er muligt at finde en nøjagtig løsning på det rejsende sælgerproblem, det vil sige at "manuelt" beregne længderne på alle mulige ruter og vælge ruten med den mindste længde. Men selv for et lille antal byer er det praktisk talt umuligt at løse problemet på denne måde. For en simpel variant, et symmetrisk problem med byer, er der mulige ruter, det vil sige, for 15 byer er der 43 milliarder ruter og for 18 byer er der allerede 177 billioner. Hvor hurtigt varigheden af beregninger vokser, kan vises af følgende eksempel. Hvis der var en enhed, der kunne finde en løsning for 30 byer på en time, så ville to ekstra byer tage tusind gange længere tid; det vil sige mere end 40 dage. $n$ $(n-1)!/2$

Diskrete optimeringsmetoder, især branche- og bundmetoder, gør det muligt at finde optimale eller omtrentlige løsninger på tilstrækkeligt store problemer.

I en geometrisk fortolkning behandler disse metoder problemet som en konveks polytop, det vil sige en flerdimensionel polygon i en dimensionel enhedsterning , hvor er lig med antallet af kanter i grafen. Hvert toppunkt i denne enhedsterning svarer til en rute, det vil sige en vektor med elementerne 0/1, som opfylder de lineære uligheder beskrevet ovenfor. Hyperplanerne beskrevet af disse uligheder afskærer de kanter af enhedsterningen, som ikke svarer til nogen rute. $m$ $[0,1]^{m}$ $m$

Den tilstødende figur viser anvendelsen af metoden til et problem med tre noder. I overensstemmelse med de tre mulige kanter mellem hjørnerne, sammenlignes binære variabler og . I dette tilfælde er der kun én mulig rute, nemlig den, der går gennem tre hjørner. Denne rute opfylder uligheden , som siger, at en rute skal passere gennem mindst to hjørner. Udover denne vej, som svarer til vektoren (1,1,1), opfylder alle punkter i den rødmarkerede del af denne ulighed også uligheden. Planer, der går gennem de røde linjer, afskærer alle hjørner svarende til ikke-eksisterende baner med højst én kant, nemlig nulvektor (0, 0, 0), enhedsvektorer (1, 0, 0), (0, 1, 0) og (0, 0, 1). En stærk ulighed vil afskære alt fra enhedsterningen, undtagen det eneste gyldige punkt (1, 1, 1). I dette særlige tilfælde kan den samme effekt opnås ved tre uligheder af typen (1). $x_{1},\,x_{2}$ $x_{3}$ $x_{1}+x_{2}+x_{3}\geqslant 2$ $x_{1}+x_{2}+x_{3}\geqslant 3$

For at bestemme den tilladte kant med den mindste længde, bør man løse sæt lineære optimeringsproblemer, der afskærer unødvendige dele af enhedsterningen ved at skære planer og forsøge at opdele enhedsterningen i mindre polytoper ved hjælp af branch and bound-metoden.

Denne metode er dog normalt ikke nok til hurtigt at finde ruter. Den største fordel ved nøjagtige metoder er, at de, givet nok tid, beregner den korteste rute. Med en nedre grænse for optimale løsninger kan man vurdere, hvor meget den fundne rute afviger fra den optimale. For eksempel med en nedre grænse på 100, og efter at have fundet en rute med længde 102, kan den optimale rute være mellem 100 og 102. Det såkaldte optimalitetsinterval eller den maksimale relative afstand mellem længden af den optimale rute og korteste kendte rute, vil være (102 - 100) /100 = 2%, dvs. længden af den fundne rute 102 afviger maksimalt med 2% fra den optimale. Når længden af den beregnede rute er lig med længden af den foregående, vurderes det, at den fundne løsning er optimal. For at finde ruter af acceptabel længde kan nøjagtige metoder kombineres med heuristiske.

Gren og bundet metode til at løse problemet med den rejsende sælger blev foreslået i 1963 af en gruppe forfattere (J. Little, K. Murty, D. Sweeney, K. Carol) [3] .

Elastisk netværksmetode

Historie

I 1987 blev det brugt af Durbin og Willshaw, som påpegede en analogi med mekanismerne til at etablere ordnede neurale forbindelser [4] .

Hver af den rejsende sælgers ruter blev betragtet som en kortlægning af en cirkel på et fly (et punkt i denne cirkel er kortlagt til hver by på flyet). Nabopunkter på cirklen skal kortlægges til punkter, hvis det er muligt, nærmest og på planet.

Algoritme

Det starter med installationen af en lille cirkel på flyet. Den udvider sig ujævnt og bliver til en ring, der passerer næsten alle byer og dermed etablerer den ønskede rute. Hvert bevægeligt punkt i ringen er påvirket af to komponenter: at flytte punktet mod den nærmeste by og flytte mod naboerne til punktet på ringen for at reducere dets længde. Byen forbindes til sidst med en bestemt del af ringen, efterhånden som den udvider sig. Da et sådant elastisk netværk udvides, er hver by forbundet med en bestemt del af ringen.

I begyndelsen har alle byer omtrent samme indflydelse på hvert waypoint. Efterfølgende bliver større afstande mindre indflydelsesrige, og hver by bliver mere specifik for de punkter i ringen, der er tættest på den. Denne gradvise stigning i specificitet, som minder om Kohonen-netværksindlæringsmetoden, styres af værdien af en effektiv radius.

Durbin og Willshaw viste, at for problemet med 30 byer, som Hopfield og Tank betragter, genererer den elastiske netværksmetode den korteste rute i omkring 1000 iterationer. For 100 byer var ruten fundet ved denne metode kun 1 % højere end den optimale.

Myrealgoritme

Genetisk algoritme

Dynamisk programmeringsalgoritme

Hovedideen er at beregne og gemme stien fra den oprindelige by til hver af de andre byer, og derefter summere denne værdi med stien fra hver af de andre byer til de resterende byer osv. Fordelen ved denne metode frem for brute- kraftmetoden er en væsentlig reduktion i den samlede volumenberegninger på grund af en mærkbar stigning i mængden af hukommelse [5] . $D$ $F$ ${\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2},P_{F}=n!\ca. n^{n} e^{-n}{\sqrt {2\pi n)),P_{D}\ll P_{F))$ $Q_{D}\sim 2^{n}{\sqrt {\frac {2n}{\pi }}},Q_{F}=2,Q_{D}\gg Q_{F}$

Se også

Noter

↑ Gross JL, Yellen J. Graph theory and its applications, 2006 , s. 275.
↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analyse Arkiveret 19. august 2021 på Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, s. 310-337.
↑ Kostevich L. S. Matematisk programmering: Inform. teknologi af optimale løsninger: Proc. godtgørelse / L. S. Kostevich. - Minsk: Ny viden, 2003. ill., s. 150, ISBN 985-6516-83-8
↑ Richard Durbin, David Willshaw. En analog tilgang til det rejsende sælgerproblem ved hjælp af en elastisk netmetode // Nature . — 22-04-1987. — Bd. 326 , udg. 6114 . — S. 689–691 . - doi : 10.1038/326689a0 . Arkiveret fra originalen den 23. april 2016.
↑ Korbut A. A., Finkelstein Yu. Yu. Diskret programmering. - M., Nauka, 1969. - C. 258-264

Litteratur

Levitin A. V. Kapitel 3. Brute Force Method: The Travelling Salesman Problem // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 159-160. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
I OG. Klog. Problemet med den rejsende sælger . - M . : "Viden" , 1969. - S. 62.
Ezhov A., Shumsky S. Neurocomputing og dets anvendelser inden for økonomi og forretning . - M .: MEPhI , 1998. - S. 216.
Gross JL, Yellen J. Grafteori og dens anvendelser. anden version. Boca Raton—London—New York: Chapman & Hall/CRC, 2006.

NP-komplette problemer
Maksimeringsproblem ved stabling (pakning)	Emballering i containere todimensionel pakning lineær pakning pakning efter vægt emballage efter værdi Rygsækproblemet
grafteori mængdeteori	Vertex Cover Problem Klik problem Problemet med et uafhængigt sæt (sæt) Sæt dækningsproblem Steiners problem Problemet med den rejsende sælger Generaliseret rejsende sælger problem
Algoritmiske problemer	Tilfredshedsproblem for booleske formler (i konjunktiv normal form)
Logiske spil og puslespil	Generaliserede tags (spil i N 2 -1) korteste løsningsproblem Problemer, hvis løsninger anvendes i Tetris Generaliseret Sudoku problem Latinsk kvadratisk påfyldningsproblem Kakuros opgave
Sværhedsklasser Operationsforskning Optimering Kombinatorisk optimering Anvendt matematik Teori om algoritmer Dynamisk programmering 21 NP-komplet Karp problem