Problemet med resande säljare

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 juni 2022; kontroller kräver 7 redigeringar .

Resandeförsäljarproblemet (eller TSP från engelska traveling salesman problem ) är ett av de mest kända kombinatoriska optimeringsproblemen , som består i att hitta den mest lönsamma vägen som passerar genom de angivna städerna minst en gång och sedan återvända till den ursprungliga staden. I förhållandena för problemet indikeras ruttlönsamhetskriteriet (det kortaste, billigaste, kumulativa kriteriet, etc.) och motsvarande matriser för avstånd, kostnader och liknande. Som regel anges att rutten endast ska passera varje stad en gång - i det här fallet görs valet bland Hamiltonian-cyklerna. Det finns flera speciella fall av den allmänna formuleringen av problemet, i synnerhet problemet med geometriska resande försäljare (även kallat plan eller euklidiskt, när avståndsmatrisen reflekterar avstånden mellan punkter på planet), det metriska resandeförsäljarproblemet (när triangel ojämlikhet uppfylls på kostnadsmatrisen ), symmetriska och asymmetriska resande säljare problem . Det finns också en generalisering av problemet, det så kallade generaliserade resandeförsäljarproblemet .

Optimeringsproblemformuleringen tillhör klassen NP-hårda problem, men som de flesta av dess speciella fall. Versionen av "beslutsproblemet" (det vill säga en som frågar om det finns en rutt som inte är längre än ett givet värde på k ) tillhör klassen av NP-fullständiga problem . Problemet med resande försäljare är ett av omräkningsproblemen : även med ett relativt litet antal städer (> 66) kan det inte lösas med metoden för uppräkning av alternativ av några teoretiskt tänkbara datorer på en tid mindre än flera miljarder år.

Historik

Relaterat till resandeförsäljarproblemet är problemet med att hitta en Hamiltonsk cykel . Ett exempel på ett sådant problem är problemet med riddarens drag , känt åtminstone sedan 1700-talet [1] . Leonhard Euler tillägnade henne ett stort verk "Lösningen av en nyfiken fråga, som inte verkar vara föremål för någon forskning", daterat 1759 [2] . Ett annat exempel på ett problem för att hitta en Hamiltonsk cykel är icosian : ett matematiskt pussel där du måste gå igenom en dodekaeder (en graf med 20 noder) och besöka varje vertex exakt en gång. Detta problem föreslogs av William Hamilton på 1800-talet, han definierade också en klass av sådana vägar.

År 1832 publicerades en bok med titeln "Resande försäljare - hur han bör bete sig och vad han bör göra för att leverera varor och bli framgångsrik i sina angelägenheter - råd från en gammal kurir" ( tyska: 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 inte använder den matematiska apparaten för att lösa det. Men det ger exempel på rutter för vissa regioner i Tyskland och Schweiz.

De första omnämnandena som ett matematiskt optimeringsproblem tillhör Carl Menger , som formulerade det på ett matematiskt kollokvium 1930 enligt följande:

Vi kallar budbärarproblemet (eftersom denna fråga uppstår för varje brevbärare, i synnerhet många resenärer löser det) problemet med att hitta den kortaste vägen mellan en ändlig uppsättning platser, vars avstånd är känt.

Snart dök det välkända namnet på resandeförsäljarproblemet upp , som föreslogs av Hassler Whitney från Princeton University .

Tillsammans med den enkla definitionen och den relativa lättheten att hitta bra lösningar, är problemet med resande säljare annorlunda eftersom det är en ganska svår uppgift att hitta en verkligt optimal väg. Med tanke på dessa egenskaper, från och med andra hälften av 1900-talet, har studiet av problemet med resande försäljare inte så mycket praktisk betydelse utan teoretisk som en modell för att utveckla nya optimeringsalgoritmer.

Många av dagens vanliga diskreta optimeringsmetoder , såsom cutoff , branch and bound , och olika varianter av heuristiska algoritmer, har utvecklats med hjälp av resandeförsäljarproblemet som exempel.

På 1950- och 1960 -talen väckte problemet med resande försäljare uppmärksamhet från forskare i USA och Europa. Ett viktigt bidrag till studiet av problemet tillhör George Danzig , Delbert Ray Fulkerson ( eng. Delbert Ray Fulkerson ) och Selmer Johnson ( eng. Selmer M. Johnson ), som 1954 vid RAND Corporation- institutet formulerade problemet i formen av ett diskret optimeringsproblem och tillämpas på det för att lösa cut-off-metoden . Med den här metoden byggde de en resande försäljares väg för en viss problemformulering med 49 städer och underbyggde dess optimalitet. På 1960- och 1970-talen studerades problemet av många forskare både teoretiskt och i termer av dess tillämpningar inom datavetenskap, ekonomi, kemi och biologi.

Richard Karp bevisade 1972 NP - fullständigheten i problemet med att hitta Hamiltonska vägar, vilket tack vare polynomreducerbarhet antydde NP-hårdheten hos resandeförsäljarproblemet. Utifrån dessa egenskaper gav han en teoretisk motivering för komplexiteten i att hitta lösningar på problemet i praktiken.

Stora framgångar uppnåddes i slutet av 1970- och 1980-talet, när Martin Grötschel ( tyska Martin Grötschel ), Manfred Padberg ( tyska Manfred Padberg ) och Giovanni Rinaldi ( italienska Giovanni Rinaldi ) och andra, med hjälp av nya divisionsmetoder plan, grenar och gränser beräknade lösningen för ett särskilt fall av problemet med 2393 städer.

På 1990 -talet satte David Applegate , Robert Bixby , Vašek Chvátal och William Cook rekord för Concorde-programmet . Gerhard Reinelt ( tyska Gerhard Reinelt ) skapade TSPLIB - en uppsättning standardiserade instanser av problemet med resande försäljare av varierande grad av komplexitet för att jämföra resultaten av olika grupper av forskares arbete. I mars 2005 löstes ett problem med 33 810 noder av Concord -programmet : en väg med längden 66 048 945 beräknades och frånvaron av kortare vägar bevisades. I april 2006 hittades en lösning för ett exempel med 85 900 noder. Med hjälp av nedbrytningsmetoder är det möjligt att beräkna lösningar för fall av problem med miljontals noder, vars längd är mindre än 1% mer än den optimala.

Formell definition

Grafrepresentation

För att kunna använda den matematiska apparaten för att lösa problemet bör den presenteras i form av en matematisk modell . Problemet med resande försäljare kan representeras som en modell på en graf , det vill säga att använda hörn och kanter mellan dem. Sålunda motsvarar grafens hörn städer, och kanterna mellan hörnen och motsvarar kommunikationsvägarna mellan dessa städer. Varje kant kan associeras med ett ruttlönsamhetskriterium , vilket kan förstås som till exempel avståndet mellan städer, tiden eller kostnaden för resan. $\left(i,j\right)$ $i$ $j$ $\left(i,j\right)$ $c_{ij}\geqslant 0$

En Hamilton-cykel är en bana som inkluderar exakt en gång varje hörn av grafen.

För att förenkla problemet och garantera förekomsten av en rutt, antas det vanligtvis att modelldiagrammet för problemet är helt sammankopplat , det vill säga att det finns en kant mellan ett godtyckligt par av hörn. I de fall det inte finns någon kommunikation mellan enskilda städer kan detta uppnås genom att införa kanter med maximal längd. På grund av den stora längden kommer en sådan kant aldrig att falla in i den optimala vägen, om den finns.

Sålunda är lösningen på resandeförsäljarproblemet att hitta den Hamiltonska cykeln med minimivikt i en komplett vägd graf.

Beroende på vilket ruttlönsamhetskriterium som jämförs med kanternas storlek, finns det olika versioner av problemet, varav de viktigaste är de symmetriska och metriska problemen.

Asymmetriska och symmetriska problem

I allmänhet skiljer sig problemet med asymmetriska resande försäljare genom att det modelleras av en riktad graf. Därmed bör man också överväga vilken riktning kanterna är i.

I fallet med ett symmetriskt problem har alla par av kanter mellan samma hörn samma längd, det vill säga längderna för kanten är samma . I det symmetriska fallet är antalet möjliga vägar hälften av det asymmetriska fallet. Det symmetriska problemet modelleras av en oriktad graf (se figur). $\left(i,j\right)$ $c_{ij}=c_{ji}$

Faktum är att problemet med resande försäljare i fallet med riktiga städer kan vara både symmetriskt och asymmetriskt, beroende på rutternas varaktighet eller längd och på rörelseriktningen.

Metriskt problem

Ett symmetriskt resandeförsäljarproblem kallas metriskt om triangelolikheten är uppfylld med avseende på kanternas längder . Relativt sett, i sådana problem är omvägar längre än raka linjer, det vill säga kanten från vertex till vertex är aldrig längre än vägen genom den mellanliggande vertexen : $i$ $j$ $k$

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

Denna kantlängdsegenskap definierar ett mätbart utrymme på uppsättningen av kanter och ett avståndsmått som tillfredsställer den intuitiva förståelsen av avstånd.

Avståndsfunktioner som är vanliga i praktiken är också metriker och uppfyller triangelolikheten:

Euklidiskt avstånd i problemet med euklidiskt resande försäljare,
Manhattanmåttet (även kvartalsmåttet) för det rektangulära resandeförsäljarproblemet, där avståndet mellan hörn på gittret är lika med summan av avstånden längs y-axeln och abskissan,
Det maximala måttet som definierar avståndet mellan hörnen på en gittergraf som det maximala värdet på avståndet längs ordinatan och abskissan.

De två sista måtten används till exempel vid borrning av hål i kretskort, när maskinen måste göra fler hål på kortast tid och kan flytta borren i båda riktningarna för att flytta från ett hål till nästa. Manhattan-metriken motsvarar fallet när rörelse i båda riktningarna sker sekventiellt, och maximum motsvarar fallet när rörelse i båda riktningarna sker synkront, och den totala tiden är lika med den maximala rörelsetiden längs ordinatan eller abskissaxeln.

Det icke-metriska resandeförsäljarproblemet kan till exempel uppstå i fallet med att minimera vistelsens varaktighet i närvaro av ett urval av fordon i olika riktningar. I ett sådant fall kan omvägen med flyg vara kortare än den direkta förbindelsen med bil.

Om det i praktiken, under problemets förhållanden, är tillåtet att besöka städer flera gånger, kan det symmetriska problemet reduceras till ett metriskt. För detta övervägs problemet på den så kallade avståndsgrafen. Denna graf har samma uppsättning hörn som den ursprungliga och är helt ansluten. Längden på kanterna mellan hörnen och på avståndsgrafen motsvarar längden på det kortaste avståndet mellan hörnen och i den ursprungliga grafen. För längder definierade på detta sätt gäller triangelolikheten, och varje rutt på avståndsgrafen motsvarar alltid en rutt med möjliga upprepningar av hörn i den ursprungliga grafen. $c_{ij}$ $i$ $j$ $i$ $j$ $c_{ij}$

Formulering som ett diskret optimeringsproblem

Ett av tillvägagångssätten för att lösa problemet är att formulera det som ett diskret optimeringsproblem, med lösningarna representerade som variabler, och sambanden som ojämlikhetsrelationer dem emellan. Således är flera alternativ möjliga. Till exempel kan ett symmetriskt problem representeras som en uppsättning kanter . Varje kant tilldelas en binär variabel , lika med 1 om kanten tillhör rutten, och 0 annars. En godtycklig rutt kan representeras som värden för en uppsättning medlemskapsvariabler, men inte varje sådan uppsättning definierar en rutt. Villkoret att värdena för uppsättningen av variabler bestämmer rutten är de linjära ojämlikheterna som beskrivs nedan. $V$ $\{I j\}$ $x_{ij}\in \{0,1\}$

Varje vertex måste kommunicera genom ett par kanter med resten av hörnen, det vill säga genom ingångs- och utgångskanterna:

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

Totalt är varje term lika med antingen 1 (tillhör rutten) eller 0 (hör inte med). Det vill säga att den resulterande summan är lika med antalet kanter i rutten som har en vertex vid en av ändarna. Det är lika med 2, eftersom varje vertex har en ingångs- och utgångskant. I den intilliggande figuren visas vertex med ingångs- och utmatningskanter, och ruttkanter visas som tjocka linjer. Bredvid revbenen är längderna applicerade på ovanstående mängd. $x_{ij}$ $i$ $i$ $x_{ij}$

De tidigare beskrivna multiplicitetsvillkoren uppfylls inte bara av rutter, utan också av värdena för variabler som motsvarar individuella cykler, där varje hörn bara tillhör en cykel (se figur). För att undvika sådana fall måste de så kallade loop-ojämlikheterna (eller subroute-elimineringsvillkoren), som definierades av Danzig, Fulkerson och Johnson 1954 under namnet loop conditions , uppfyllas . Dessa ojämlikheter definierade ett ytterligare villkor att varje uppsättning av hörn är antingen tom eller innehåller alla hörn, kombinerat med resten av hörnen genom minst två kanter: $S\delmängd V$

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

för alla uppsättningar av hörn , där . Denna summa är lika med summan av längderna på bankanterna mellan vertex och vertex . För att eliminera onödiga ojämlikheter kan vi begränsa oss till uppsättningar av hörn med ett minimum av två och ett maximum av hörn. I figuren bredvid är kanter med längder markerade med tjocka linjer, de återstående kanterna har längd . Införandet av ytterligare villkor (2) för vertexuppsättningen , som består av tre vänstra hörn, kommer att säkerställa att den kombineras genom minst två bankanter med tre hörn till höger för att eliminera båda cyklerna. Antalet cykeleliminerande ojämlikheter enligt Danzig, Fulkerson och Johnson är . $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)$

År 1960 utarbetade Miller, Tucker och Zemlin alternativa villkor för att eliminera subrutter genom att introducera nya variabler som specificerade ordningen på besökta städer, vilket endast kräver ytterligare ojämlikheter. Dessutom, på grund av dualiteten i formuleringarna av Miller, Tucker och Zemlin, är problemet med resande säljare fortfarande NP-hårt. $n$ $n^{2}-n+1$ $x_{ij}$

Således definierar varje vektor med element lika med 0 och 1 som uppfyller alla ojämlikheter en korrekt rutt, vilket är en lösning på det omformulerade resandeförsäljarproblemet: beräkna

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

Eftersom variablerna bara har värdena 0 och 1 är summan lika med den totala längden på kanterna som hör till rutten. $x_{ij}$ $c_{ij}$ $\{I j\}$

Antalet ojämlikheter av typen (2) växer exponentiellt när antalet städer ökar, eftersom nästan varje delmängd av noder definierar en olikhet. Detta problem kan lösas genom att använda klippplansmetoden , på grund av vilken ojämlikheter läggs till endast när dessa ojämlikheter verkligen behövs. Ur geometrisk synvinkel kan linjära ojämlikheter representeras som hyperplan i variablernas rymd. Uppsättningen av vektorer som uppfyller dessa ojämlikheter bildar en polytop (flerdimensionell polyhedron), eller flerdimensionell polygon, i ett sådant utrymme, den exakta formen bestäms av längderna och är för det mesta okänd. Det kan dock visas att förhållandena (1) och (2) bestämmer polytopens ytor (facetter), det vill säga sidoytorna på polytopen med den högsta dimensionen. Därför är de bland de starkaste linjära ojämlikheterna som kan beskriva en rutt. Det finns också många olika aspekter som definieras av ojämlikheter som bara är kända i ett fåtal fall. Även om (1) och (2) tillsammans med begränsningarna helt modellerar problemet för binära vektorer, kan dessa olikheter användas i gren- och bunden-metoden för att förkasta lösningar med linjära optimeringsmetoder med icke-heltalskoordinater (se avsnittet om exakta metoder). Nedan). $2^{|V|}$ $c_{ij}$

Algoritmisk komplexitet

Eftersom den resande försäljaren i varje stad ställs inför valet av nästa stad bland de som han ännu inte har besökt, finns det rutter för det asymmetriska och rutter för det symmetriska resandeförsäljarproblemet. Storleken på sökutrymmet beror alltså på antalet städer. $(n-1)!$ $(n-1)!/2$

Olika versioner av resandeförsäljarproblemet (metriska, symmetriska och asymmetriska) är NP-ekvivalenta. Enligt den vanliga men oprövade gissningen om olikheten mellan komplexitetsklasserna P och NP finns det ingen deterministisk Turing-maskin som kan lösa probleminstanser i polynomtid beroende på antalet städer.

Det är också känt att det under villkoret inte finns någon algoritm som, för något polynom, skulle beräkna sådana lösningar på det resande säljarproblemet som skulle skilja sig från det optimala maximumet med en faktor . $P\neq NP$ $sid$ $2^{p(n)}$

I praktiken krävs inte alltid sökandet efter en strikt optimal rutt. Det finns algoritmer för att hitta ungefärliga lösningar på ett metriskt problem i polynomtid och hitta en rutt som är högst dubbelt så lång som den optimala. Än så länge är ingen polynomtidsalgoritm känd som skulle garantera en noggrannhet bättre än 1,5 av den optimala. Genom antagande finns det en (okänd) konstant så att ingen polynom-tidsalgoritm kan garantera noggrannhet . Som Arora har visat, för det euklidiska resandeförsäljarproblemet, finns det ett polynomtids -PTAS-schema för att hitta en ungefärlig lösning. $P\neq NP$ $c>0$ $1+c$

Dessutom kan data ha funktioner som kan hjälpa till att lösa problemet. Till exempel ligger städer inte av en slump, utan efter terrängen, eller till och med längs den optimala handelsvägen som länge har hittats. Ytterligare information och heuristik gör att vi kan hitta acceptabla lösningar inom rimlig tid.

Stängda och öppna varianter av problemet

I den stängda versionen av resandeförsäljarproblemet krävs det att man besöker alla hörn i grafen och sedan återgår till den ursprungliga hörn. Den öppna varianten skiljer sig från den stängda genom att den inte kräver att man återgår till startpunkten.

En öppen version av problemet reduceras till en sluten genom att ersätta vikterna av bågarna som ingår i startpunkten med siffran 0. Den optimala slutna resande försäljarvägen i en sådan graf motsvarar den optimala öppna rutten i den ursprungliga grafen.

För att reducera en sluten variant till en icke-stängd, är det nödvändigt att fastställa ett antal som strikt överstiger vikten av en resande försäljarrutt i en given graf ( du kan till exempel ta summan av de maximala viktbågarna som utgår från varje vertex , ökat med 1). Sedan måste du lägga till en ny vertex i grafen (vi antar att hörn på den ursprungliga grafen är numrerade från 0 till , medan startpunkten har nummer 0). Kostnaderna för bågar som lämnar och går in i vertexet definieras enligt följande: $K$ $K$ $v_{n}$ $n-1$ $v_{n}$

$c_{n,i}=3K$
$c_{0,n}=3K$
$c_{i,n}=c_{i,0}+2K$ kl från till $i$ $ett$ $n-1$

Den optimala icke-stängda resande försäljarvägen i en sådan graf motsvarar den optimala stängda resande försäljarrutten i den ursprungliga grafen och har en högre kostnad. $2K$

Lösningsmetoder

Protozoer

uttömmande sökning
slumpmässig uppräkning
giriga algoritmer
- närmaste granne metod
- den närmaste metoden för inkludering av staden
- lägsta kostnadsmetoden
minimum spaning tree-metoden
simulerad glödgningsmetod

Alla effektiva (minskande full uppräkning) metoder för att lösa problemet med resande säljare är heuristiska metoder . De flesta heuristiska metoder hittar inte den mest effektiva vägen, utan en ungefärlig lösning . Så kallade när som helst algoritmer är ofta efterfrågade .[ förtydliga ] , det vill säga gradvis förbättra någon nuvarande ungefärlig lösning.

Ett exempel på den enklaste metoden för att lösa den metriska versionen av problemet är användningen av minsta spännträd, vilket ger en lösning med en approximationsfaktor och har tidskomplexitet . Tanken är att varje ansluten graf innehåller en lägre kostnadströskel för sin subgraf, det minsta spännträdet, och att varje cykel som besöker varje grafvertex minst en gång kan omvandlas till en kostnadsoptimal rutt med hjälp av måtten: $2$ $O(n^{2}\log n)$

Hitta det minsta spännträdet i grafen . $T$ $G$
Skapa en graf genom att dubbla alla kanter i . Så alla hörn i har ett jämnt antal kanter. $T'$ $T$ $T'$
Hitta Euler-cykeln . $T'$ $C'$
Minska , hoppa över dubbla kanter, få en cykel . $C'$ $C$
Ta fram . $C$

Värdet på approximationsfaktorn bevisas enligt följande: Låt - det minsta spännträdet, - samma träd, men med dubbla kanter, - Euler-cykeln på grafen , - resultatet av algoritmen, - den minsta rutten. Observera att , liksom . Då är approximationsfaktorn . $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$

Ovanstående metod kan emellertid optimeras genom att öka antalet kanter vid hörn med ett udda antal grannar med 1, vilket motsvarar matchande "udda" hörn. Det är viktigt att notera att antalet "udda" hörn alltid är jämnt, baserat på handskakningslemma . I ett sådant fall har den optimerade algoritmen en approximationsfaktor och tidskomplexitet . Innan beviset, låt oss visa att , där är en matchning och är en optimal rutt: Låt vara uppsättningen av "udda" hörn av det minsta spännträdet , och vara en cykel som erhålls från genom att hoppa över hörn . Uppenbarligen har en jämn längd, samt två icke-korsande maximala matchningar och , för vilka och . Av detta följer att , och därmed . Baserat på detta hittar vi approximationsfaktorn för algoritmen: . $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$

Det finns också inställningar där problemet med resande säljare blir NP-komplett . Vanligtvis ser sådana påståenden ut så här: finns det en sådan tur på en given graf G att dess kostnad inte överstiger x . Ofta testas nya tillvägagångssätt för heuristisk reduktion av uttömmande sökning på den .

I praktiken används olika modifieringar av effektivare metoder: branch and bound- metoden och metoden för genetiska algoritmer , såväl som myrkolonialgoritmen .

Branch and Bound Method

Det är möjligt att hitta en exakt lösning på resandeförsäljarproblemet, det vill säga att "manuellt" beräkna längden på alla möjliga rutter och välja den rutt som har minst längd. Men även för ett litet antal städer är det praktiskt taget omöjligt att lösa problemet på detta sätt. För en enkel variant, ett symmetriskt problem med städer, finns det möjliga rutter, det vill säga för 15 städer finns det 43 miljarder rutter och för 18 städer finns det redan 177 biljoner. Hur snabbt varaktigheten av beräkningarna växer kan visas av följande exempel. Om det fanns en enhet som kunde hitta en lösning för 30 städer på en timme, då skulle ytterligare två städer ta tusen gånger längre tid; det vill säga mer än 40 dagar. $n$ $(n-1)!/2$

Diskreta optimeringsmetoder, i synnerhet förgrenade och bundna metoder, gör det möjligt att hitta optimala eller ungefärliga lösningar för tillräckligt stora problem.

I en geometrisk tolkning behandlar dessa metoder problemet som en konvex polytop, det vill säga en flerdimensionell polygon i en dimensionell enhetskub , där är lika med antalet kanter i grafen. Varje vertex i denna enhetskub motsvarar en rutt, det vill säga en vektor med element 0/1, som uppfyller de linjära olikheter som beskrivs ovan. Hyperplanen som beskrivs av dessa ojämlikheter skär av de kanter på enhetskuben som inte motsvarar någon rutt. $m$ $[0,1]^{m}$ $m$

Den intilliggande figuren visar tillämpningen av metoden för ett problem med tre noder. I enlighet med de tre möjliga kanterna mellan hörnen jämförs binära variabler och . I det här fallet finns det bara en möjlig väg, nämligen den som går genom tre hörn. Denna rutt uppfyller ojämlikheten , som säger att en rutt måste passera genom minst två hörn. Förutom denna väg, som motsvarar vektorn (1,1,1), uppfyller alla punkter i den rödmarkerade delen av denna ojämlikhet också olikheten. Plan som passerar genom de röda linjerna skär av alla hörn som motsvarar icke-existerande banor med högst en kant, nämligen nollvektor (0, 0, 0), enhetsvektorer (1, 0, 0), (0, 1, 0) och (0, 0, 1). En stark ojämlikhet kommer att skära bort allt från enhetskuben, förutom den enda giltiga punkten (1, 1, 1). I detta speciella fall kan samma effekt erhållas av tre olikheter av typen (1). $x_{1},\,x_{2}$ $x_{3}$ $x_{1}+x_{2}+x_{3}\geqslant 2$ $x_{1}+x_{2}+x_{3}\geqslant 3$

För att bestämma den tillåtna kanten med minsta längd bör man lösa uppsättningar av linjära optimeringsproblem som skär bort onödiga delar av enhetskuben genom att skära plan och försöka dela upp enhetskuben i mindre polytoper med hjälp av branch and bound-metoden.

Den här metoden räcker dock vanligtvis inte för att snabbt hitta rutter. Den största fördelen med exakta metoder är att de, givet tillräckligt med tid, beräknar den kortaste vägen. Med en nedre gräns för optimala lösningar kan man uppskatta hur mycket den hittade vägen skiljer sig från den optimala. Till exempel, med en nedre gräns på 100, och efter att ha hittat en rutt med längd 102, kan den optimala rutten vara mellan 100 och 102. Det så kallade optimalitetsintervallet , eller det maximala relativa avståndet mellan längden på den optimala rutten och kortaste kända vägen, kommer att vara (102 - 100) /100 = 2%, det vill säga längden på den hittade vägen 102 skiljer sig med maximalt 2% från den optimala. När längden på den beräknade rutten är lika med längden på den föregående, anses den hittade lösningen vara optimal. För att hitta rutter av acceptabel längd kan exakta metoder kombineras med heuristiska.

Gren och bunden metod för att lösa problemet med resande försäljare föreslogs 1963 av en grupp författare (J. Little, K. Murty, D. Sweeney, K. Carol) [3] .

Elastisk nätverksmetod

Historik

1987 användes den av Durbin och Willshaw, som påpekade en analogi med mekanismerna för att upprätta ordnade neurala anslutningar [4] .

Var och en av den resande försäljarens rutter betraktades som en kartläggning av en cirkel på ett plan (någon punkt av denna cirkel är kartlagd till varje stad på planet). Närliggande punkter på cirkeln bör kartläggas till punkter, om möjligt, närmast och på planet.

Algoritm

Det börjar med installationen av en liten cirkel på planet. Den expanderar ojämnt och blir en ring som passerar nästan alla städer och därmed etablerar den önskade rutten. Varje rörlig punkt i ringen påverkas av två komponenter: flytta punkten mot närmaste stad och förskjutning mot grannarna till punkten på ringen för att minska dess längd. Staden ansluter så småningom till en viss del av ringen när den expanderar. När ett sådant elastiskt nätverk expanderar är varje stad associerad med en viss del av ringen.

I början har alla städer ungefär samma inflytande på varje waypoint. Därefter blir större avstånd mindre inflytelserika, och varje stad blir mer specifik för de punkter i ringen som är närmast den. Denna gradvisa ökning av specificitet, som påminner om Kohonens nätverksinlärningsmetod, styrs av värdet av någon effektiv radie.

Durbin och Willshaw visade att för problemet med 30 städer som Hopfield och Tank betraktar, genererar den elastiska nätverksmetoden den kortaste vägen i cirka 1000 iterationer. För 100 städer var rutten som hittades med denna metod endast 1 % högre än den optimala.

Myralgoritm

Genetisk algoritm

Dynamisk programmeringsalgoritm

Huvudidén är att beräkna och lagra vägen från den ursprungliga staden till var och en av de andra städerna, och sedan summera detta värde med vägen från var och en av de andra städerna till de återstående städerna, etc. Fördelen med den här metoden framför rå- kraftmetoden är en signifikant minskning av den totala volymberäkningen på grund av en märkbar ökning av mängden minne [5] . $D$ $F$ ${\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2},P_{F}=n!\approx 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 även

Anteckningar

↑ Gross JL, Yellen J. Grafteori och dess tillämpningar, 2006 , sid. 275.
↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analys Arkiverad 19 augusti 2021 på Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, sid. 310-337.
↑ Kostevich L. S. Matematisk programmering: Informera. teknik för optimala lösningar: Proc. bidrag / L. S. Kostevich. - Minsk: Ny kunskap, 2003. ill., s. 150, ISBN 985-6516-83-8
↑ Richard Durbin, David Willshaw. En analog metod för resandeförsäljarproblemet med hjälp av en elastisk nätmetod // Nature . — 1987-04-22. — Vol. 326 , utg. 6114 . — S. 689–691 . - doi : 10.1038/326689a0 . Arkiverad från originalet 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 till utveckling och analys - M . : Williams , 2006. - S. 159-160. — 576 sid. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
IN OCH. Klok. Problemet med resande säljare . - M . : "Kunskap" , 1969. - S. 62.
Ezhov A., Shumsky S. Neurocomputing och dess tillämpningar inom ekonomi och affärer . - M .: MEPhI , 1998. - S. 216.
Gross JL, Yellen J. Grafteori och dess tillämpningar. andra upplagan. Boca Raton—London—New York: Chapman & Hall/CRC, 2006.

NP-kompletta problem
Maximeringsproblem med stapling (packning)	Förpackning i behållare tvådimensionell packning linjär packning packning efter vikt förpackning efter värde Ryggsäcksproblemet
grafteori mängdteori	Vertex Cover Problem Klicka problem Problemet med en oberoende uppsättning (uppsättning) Ställtäckningsproblem Steiners problem Problemet med resande säljare Generaliserat resandeförsäljarproblem
Algoritmiska problem	Tillfredsställelseproblem för booleska formler (i konjunktiv normal form)
Logiska spel och pussel	Generaliserade taggar (spel i N 2 -1) kortaste lösningen problem Problem vars lösningar tillämpas i Tetris Generaliserat Sudoku problem Latinsk kvadrat fyllningsproblem Kakuros uppgift
Svårighetsklasser Operationsforskning Optimering Kombinatorisk optimering Tillämpad matematik Teori om algoritmer Dynamisk programmering 21 NP-komplett Karp-problem