Az utazó eladó probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. június 28-án felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A travelling salesman probléma (vagy az angol traveling salesman problem szóból TSP ) az egyik leghíresebb kombinatorikus optimalizálási probléma , amely abból áll, hogy legalább egyszer meg kell találni a legjövedelmezőbb útvonalat , amely áthalad a megadott városokon, majd visszatér az eredeti városba. A probléma körülményei között fel van tüntetve az útvonal jövedelmezőségi kritériuma (legrövidebb, legolcsóbb, kumulatív kritérium stb.) és a megfelelő távolságok, költségek és hasonlók mátrixai. Általános szabály, hogy az útvonalnak minden városon csak egyszer kell áthaladnia - ebben az esetben a Hamilton-ciklusok közül kell választani . A probléma általános megfogalmazásának számos speciális esete van, különösen a geometriai utazó eladó probléma (más néven síkbeli vagy euklideszi, amikor a távolságmátrix tükrözi a sík pontjai közötti távolságokat), a metrikus utazó eladó probléma (amikor a háromszög egyenlőtlenség teljesül a költségmátrixon ), szimmetrikus és aszimmetrikus utazó eladó problémák . A problémának van egy általánosítása is, az úgynevezett általánosított utazó eladó probléma .

Az optimalizálási problémafelvetés azonban az NP-nehéz problémák osztályába tartozik, mint a legtöbb konkrét eset. A „döntési probléma” változata (vagyis az, amelyik azt kérdezi, hogy van-e egy adott k értéknél nem hosszabb útvonal ) az NP-teljes feladatok osztályába tartozik . Az utazó kereskedő probléma az egyik transzszámítási probléma : még viszonylag kis számú város (> 66) esetén sem oldható meg egyetlen elméletileg elképzelhető számítógép által több milliárd évnél rövidebb időn belüli lehetőségek számbavételének módszerével.

Történelem

Az utazó eladó problémájához kapcsolódik a Hamilton-ciklus megtalálásának problémája . Ilyen probléma például a lovagok mozgásának problémája , amely legalább a 18. század óta ismert [1] . Leonhard Euler egy 1759-es nagyszabású munkáját szentelte neki: "Egy különös kérdés megoldása, amely úgy tűnik, hogy semmilyen kutatásnak nem tárgya" [2] . Egy másik példa a Hamilton-ciklus megtalálásának problémájára az icosian : egy matematikai feladvány, amelyben egy dodekaéderen (20 csomópontos gráfon) kell keresztülmenni, és minden csúcsot pontosan egyszer meglátogatni. Ezt a problémát William Hamilton javasolta a 19. században, ő is meghatározta az ilyen utak osztályát.

1832-ben megjelent egy könyv "Utazó értékesítő – hogyan kell viselkednie és mit kell tennie, hogy árut szállítson és sikeres legyen ügyeiben – egy régi futár tanácsa" ( németül: 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 ), amely leírja a problémát, de nem használja a matematikai apparátust annak megoldására. De példákat kínál Németország és Svájc egyes régióinak útvonalaira.

Az első említések matematikai optimalizálási problémaként Carl Mengerhez tartoznak , aki 1930 -ban egy matematikai kollokviumon a következőképpen fogalmazta meg :

Hírvivő-problémának nevezzük (mivel ez a kérdés minden postásnál felmerül, különösen sok utazó oldja meg) a legrövidebb út megtalálásának problémáját véges helyek között, amelyek távolsága ismert.

Hamarosan megjelent az utazó eladó probléma jól ismert neve , amelyet Hassler Whitney javasolt a Princeton Egyetemről .

A definíció egyszerűsége és a jó megoldások viszonylagos könnyűsége mellett az utazó értékesítő probléma annyiban különbözik, hogy az igazán optimális út megtalálása meglehetősen nehéz feladat. Ezen tulajdonságok ismeretében a 20. század második felétől kezdődően az utazó értékesítő probléma vizsgálatának nem annyira gyakorlati, mint inkább elméleti értelme van, mint inkább új optimalizáló algoritmusok kidolgozásának modellje.

A napjainkban elterjedt diszkrét optimalizálási módszerek közül sok , mint például a levágás , az elágazás és a kötés , valamint a heurisztikus algoritmusok különféle változatai az utazó eladó probléma példájával kerültek kifejlesztésre.

Az 1950 -es és 1960-as években az utazó eladók problémája felkeltette a tudósok figyelmét az Egyesült Államokban és Európában. A probléma tanulmányozásához fontos hozzájárulás George Danzig , Delbert Ray Fulkerson ( angol. Delbert Ray Fulkerson ) és Selmer Johnson ( eng. Selmer M. Johnson ), akik 1954 -ben a RAND Corporation intézetében megfogalmazták a problémát a formában. egy diszkrét optimalizálási probléma, és alkalmazzuk rá a cut-off módszer megoldására . Ezzel a módszerrel 49 várossal egy adott problémafelvetéshez építettek egy utazó értékesítői utat, és alátámasztották annak optimálisságát. Az 1960-as és 1970-es években a problémát számos tudós tanulmányozta mind elméletileg, mind számítástechnikai, közgazdasági, kémiai és biológiái alkalmazásai szempontjából.

Richard Karp 1972 - ben bebizonyította a Hamilton-utak keresésének problémájának NP-teljességét , ami a polinomiális redukálhatóságnak köszönhetően az utazó eladó probléma NP-keménységét implikálta. Ezen tulajdonságok alapján elméleti indoklást adott a probléma gyakorlati megoldásának bonyolultságára.

Nagy sikereket értek el az 1970-es és 1980-as évek végén, amikor Martin Grötschel ( német Martin Grötschel ), Manfred Padberg ( német Manfred Padberg ) és Giovanni Rinaldi ( olasz Giovanni Rinaldi ) és mások, új osztási módszerekkel sík, ág és határvonal segítségével kiszámították a megoldást. a probléma egy adott esetére 2393 várossal.

Az 1990-es években David Applegate , Robert Bixby , Vašek Chvátal és William Cook rekordokat döntött a Concorde programban . Gerhard Reinelt ( német Gerhard Reinelt ) megalkotta a TSPLIB-et - az utazó eladók problémájának szabványosított példányait, amelyek különböző összetettségűek, hogy összehasonlítsák a különböző kutatócsoportok munkájának eredményeit. 2005 márciusában egy 33 810 csomópont problémáját oldotta meg a Concord program : 66 048 945 hosszú utat számoltak ki, és bebizonyosodott a rövidebb utak hiánya. 2006 áprilisában megoldást találtak egy 85 900 csomópontot tartalmazó példányra. A dekompozíciós módszerek segítségével megoldásokat lehet kiszámítani olyan esetekre, amikor több millió csomópont van, amelyek hossza 1%-nál kevesebb, mint az optimális.

Formális definíció

Grafikonábrázolás

Ahhoz, hogy a matematikai apparátust a probléma megoldására használni lehessen, azt matematikai modell formájában kell bemutatni . Az utazó eladó probléma modellként ábrázolható egy gráfon , vagyis a köztük lévő csúcsok és élek használatával. Így a gráf csúcsai a városoknak, a csúcsok közötti élek pedig a városok közötti kommunikációs utaknak felelnek meg. Minden élhez társítható egy útvonal jövedelmezőségi feltétele , amely felfogható például a városok közötti távolság, az utazás ideje vagy költségeként. $\left(i,j\jobb)$ $én$ $j$ $\left(i,j\jobb)$ $c_{ij}\geqslant 0$

A Hamilton-ciklus egy olyan út, amely a gráf minden csúcsát pontosan egyszer tartalmazza.

A probléma egyszerűsítése és az útvonal meglétének garantálása érdekében általában azt feltételezik, hogy a probléma modellgráfja teljesen összefügg , azaz van egy él egy tetszőleges csúcspár között. Azokban az esetekben, amikor nincs kommunikáció az egyes városok között, ez maximális hosszúságú élek bevezetésével érhető el. A nagy hossz miatt egy ilyen él soha nem esik az optimális útvonalba, ha létezik.

Így az utazó eladó problémájának megoldása a minimális súly Hamilton-ciklusának megtalálása egy teljes súlyozott gráfban.

Attól függően, hogy melyik útvonal jövedelmezőségi kritériumát viszonyítjuk az élek méretéhez, a problémának különböző változatai vannak, amelyek közül a legfontosabbak a szimmetrikus és metrikus problémák.

Aszimmetrikus és szimmetrikus problémák

Általánosságban elmondható, hogy az aszimmetrikus utazó eladó probléma abban különbözik, hogy irányított gráf modellezi. Ezért azt is figyelembe kell venni, hogy az élek milyen irányban vannak.

Szimmetrikus feladat esetén az ugyanazon csúcsok közötti összes élpár azonos hosszúságú, azaz az él hossza azonos . A szimmetrikus esetben a lehetséges útvonalak száma fele az aszimmetrikus esetnek. A szimmetrikus problémát irányítatlan gráf modellezi (lásd az ábrát). $\left(i,j\jobb)$ $c_{ij}=c_{ji}$

Valójában az utazó eladó probléma valós városok esetében szimmetrikus és aszimmetrikus is lehet, az útvonalak időtartamától vagy hosszától, valamint a mozgás irányától függően.

Metrikus probléma

Egy szimmetrikus utazó eladó problémát metrikusnak nevezünk, ha a háromszög egyenlőtlensége teljesül az élek hosszára vonatkozóan . Viszonylagosan az ilyen feladatokban a kitérők hosszabbak, mint az egyenesek, vagyis a csúcstól a csúcsig tartó él soha nem hosszabb, mint a közbülső csúcson át vezető út : $én$ $j$ $k$

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

Ez az élhossz-tulajdonság egy mérhető teret határoz meg az élek halmazán és egy távolságmértéket, amely kielégíti a távolság intuitív megértését.

A gyakorlatban elterjedt távolságfüggvények is metrikák, és kielégítik a háromszög egyenlőtlenséget:

Euklideszi távolság az euklideszi utazó eladó problémában,
A téglalap alakú utazó eladó probléma Manhattan-metrikája (egyben negyedéves metrika), amelyben a rács csúcsai közötti távolság egyenlő az y-tengely és az abszcissza menti távolságok összegével,
A maximális metrika , amely a rácsgráf csúcsai közötti távolságot az ordináta és az abszcissza mentén mért távolság maximális értékeként határozza meg.

Az utolsó két mérőszámot például a nyomtatott áramköri lapok lyukak fúrásakor használják, amikor a gépnek a legrövidebb idő alatt több lyukat kell készítenie, és mindkét irányba el tudja mozgatni a fúrót, hogy egyik lyukról a másikra mozogjon. A manhattani metrika annak az esetnek felel meg, amikor a mozgás mindkét irányban szekvenciálisan történik, a maximum pedig annak az esetnek, amikor a mozgás mindkét irányban szinkronban történik, és a teljes idő megegyezik az ordináta vagy az abszcissza tengely mentén történő mozgás maximális idejével.

A nem metrikus utazó eladó probléma felmerülhet például abban az esetben, ha a tartózkodás időtartamát minimalizálják különböző irányú járművek megválasztása esetén. Ilyen esetben a légi kitérő rövidebb lehet, mint a közvetlen autós csatlakozás.

Ha a gyakorlatban a probléma körülményei között megengedett a városok többszöri látogatása, akkor a szimmetrikus probléma metrikusra redukálható. Ehhez a problémát az úgynevezett távolsággráfon vizsgáljuk. Ennek a gráfnak ugyanaz a csúcskészlete, mint az eredetinek, és teljesen összefügg. A csúcsok közötti és a távolsággráfon lévő élek hossza megfelel a csúcsok közötti és az eredeti gráfban lévő legrövidebb távolság hosszának . Az így definiált hosszúságokra a háromszög egyenlőtlenség érvényes, és a távolsággráf minden útvonala mindig megfelel egy olyan útvonalnak, amelyen az eredeti gráf csúcsai ismétlődnek. $c_{ij}$ $én$ $j$ $én$ $j$ $c_{ij}$

A megfogalmazás mint diszkrét optimalizálási probléma

A probléma megoldásának egyik megközelítése, hogy diszkrét optimalizálási problémaként fogalmazzuk meg, a megoldásokat változókként, az összefüggéseket pedig egyenlőtlenségi viszonyokként ábrázolva közöttük. Így több lehetőség is lehetséges. Például egy szimmetrikus probléma ábrázolható élek halmazaként . Minden élhez hozzá van rendelve egy bináris változó , amely egyenlő 1-gyel, ha az él az útvonalhoz tartozik, és 0-val egyébként. Egy tetszőleges útvonal a tagsági változók halmazának értékeként ábrázolható, de nem minden ilyen halmaz határoz meg útvonalat. A feltétel, hogy a változók halmazának értékei határozzák meg az útvonalat, az alább leírt lineáris egyenlőtlenségek. $V$ $\{i,j\}$ $x_{ij}\in \{0,1\}$

Minden csúcsnak egy élpáron keresztül kell kommunikálnia a többi csúcsgal, azaz a bemeneti és kimeneti éleken keresztül:

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

Összességében minden tag egyenlő vagy 1-gyel (az útvonalhoz tartozik), vagy 0-val (nem tartozik hozzá). Vagyis a kapott összeg megegyezik az útvonal azon éleinek számával, amelyeknek az egyik végén van egy csúcsa. Ez egyenlő 2-vel, mivel minden csúcsnak van bemeneti és kimeneti éle. A szomszédos ábrán a csúcs bemeneti és kimeneti élekkel, az útvonal élei pedig vastag vonalakkal láthatók. A bordák mellett a fenti mennyiségre alkalmazott hosszúságok találhatók. $x_{ij}$ $én$ $én$ $x_{ij}$

A korábban leírt multiplicitási feltételeket nem csak az útvonalak teljesítik, hanem az egyes ciklusoknak megfelelő változók értékei is, ahol minden csúcs csak egy ciklushoz tartozik (lásd az ábrát). Az ilyen esetek elkerülése érdekében teljesíteni kell az úgynevezett hurokegyenlőtlenségeket (vagy szubroute eliminációs feltételeket), amelyeket Danzig, Fulkerson és Johnson definiált 1954 - ben a hurokfeltételek néven . Ezek az egyenlőtlenségek egy további feltételt határoztak meg, hogy minden csúcshalmaz vagy üres, vagy tartalmazza az összes csúcsot, a többi csúcsgal kombinálva legalább két élen keresztül: $S\alhalmaz V$

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

minden csúcshalmazra , ahol . Ez az összeg egyenlő a csúcs és a csúcs közötti útélek hosszának összegével . A szükségtelen egyenlőtlenségek kiküszöbölésére korlátozhatjuk magunkat olyan csúcshalmazokra , amelyeknek minimum kettő és maximum csúcsa van. A mellette lévő ábrán a hosszúságú élek vastag vonallal vannak jelölve, a fennmaradó élek hossza . További feltételek (2) bevezetése a három bal oldali csúcsból álló csúcskészletre biztosítja, hogy legalább két útvonalélen keresztül, három jobb oldali csúcsgal kombinálva mindkét ciklust kiküszöböljük. A ciklust kiküszöbölő egyenlőtlenségek száma Danzig, Fulkerson és Johnson szerint . $S$ $1\leqslant |S|\leqslant |V|-1$ $i\in S$ $j\notin S$ $S$ $|V|-2$ $\{i,j\}$ $x_{ij}=1$ $x_{ij}=0$ $S$ $S$ $2^{n}-2(n-1)$

1960- ban Miller, Tucker és Zemlin alternatív feltételeket dolgozott ki az alútvonalak megszüntetésére új változók bevezetésével, amelyek meghatározzák a felkeresett városok sorrendjét, csak további egyenlőtlenségeket igényelve. Ráadásul Miller, Tucker és Zemlin megfogalmazásának kettőssége miatt az utazó eladók problémája továbbra is NP-kemény. $n$ $n^{2}-n+1$ $x_{ij}$

Így minden 0 és 1 elemű vektor, amely minden egyenlőtlenséget kielégít, egy helyes útvonalat határoz meg, amely megoldást jelent az újrafogalmazott utazó eladó problémára: számold

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

Mivel a változóknak csak 0 és 1 értéke van, az összeg megegyezik az útvonalhoz tartozó élek teljes hosszával. $x_{ij}$ $c_{ij}$ $\{i,j\}$

A (2) típusú egyenlőtlenségek száma exponenciálisan nő a városok számának növekedésével, mivel a csomópontok szinte minden részhalmaza egy egyenlőtlenséget határoz meg. Ezt a problémát a vágósík módszer alkalmazásával lehet megoldani , ami miatt az egyenlőtlenségeket csak akkor adjuk hozzá, amikor ezekre az egyenlőtlenségekre valóban szükség van. Geometriai szempontból a lineáris egyenlőtlenségek hipersíkokként ábrázolhatók a változók terében. Az ezeket az egyenlőtlenségeket kielégítő vektorok halmaza egy politópot (többdimenziós poliédert), vagy többdimenziós sokszöget alkot egy ilyen térben, a pontos alakot a hosszúságok határozzák meg, és többnyire ismeretlen. Kimutatható azonban, hogy az (1) és (2) feltételek meghatározzák a politóp lapjait (faszetáját), vagyis a legnagyobb dimenziójú politóp oldalfelületeit. Ezért ezek a legerősebb lineáris egyenlőtlenségek közé tartoznak, amelyek egy útvonalat leírhatnak. A csak néhány esetben ismert egyenlőtlenségeknek számos különböző aspektusa van. Bár (1) és (2) a megszorításokkal együtt teljes mértékben csak bináris vektorokra modellezi a problémát, ezek az egyenlőtlenségek felhasználhatók az elágazó és kötött módszerben a nem egész koordinátákkal rendelkező lineáris optimalizálási módszerekkel történő megoldások elvetésére (lásd a pontos módszerek részt). lent). $2^{|V|}$ $c_{ij}$

Algoritmikus összetettség

Mivel az utazó értékesítő minden városban szembesül azzal, hogy a következő várost válassza ki azok közül, amelyeket még nem látogatott meg, ezért vannak útvonalak az aszimmetrikus és a szimmetrikus utazó ügynök problémához. Így a keresési tér nagysága faktorosan függ a városok számától. $(n-1)!$ $(n-1)!/2$

Az utazó eladó probléma különböző változatai (metrikus, szimmetrikus és aszimmetrikus) NP-ekvivalensek. A P és NP komplexitási osztályok egyenlőtlenségére vonatkozó általános, de nem bizonyított sejtés szerint nincs olyan determinisztikus Turing-gép , amely a városok számától függően polinomiális időben képes lenne megoldani a problémapéldányokat.

Az is ismert, hogy azon feltétel mellett nincs olyan algoritmus, amely valamilyen polinomra olyan megoldásokat számolna ki az utazó eladó problémájára, amelyek egy faktorral eltérnének az optimális maximumtól . $P\neq NP$ $p$ $2^{p(n)}$

A gyakorlatban nem mindig szükséges a szigorúan optimális útvonal keresése. Léteznek algoritmusok, amelyekkel közelítő megoldásokat találhatunk egy metrikus feladatra polinomiális időben, és olyan útvonalat találhatunk, amely legfeljebb kétszer olyan hosszú, mint az optimális. Eddig nem ismert olyan polinomiális idő algoritmus, amely az optimális 1,5-énél jobb pontosságot garantálna. Feltételezzük , hogy létezik egy (ismeretlen) állandó , amelyre egyetlen polinomiális idejű algoritmus sem garantálja a pontosságot . Ahogy Arora megmutatta, az euklideszi utazó eladó problémára létezik egy polinomiális idejű PTAS séma a közelítő megoldás megtalálására. $P\neq NP$ $c>0$ $1+c$

Ezenkívül az adatoknak lehetnek olyan funkciói, amelyek segíthetik a probléma megoldását. Például a városok nem véletlenül helyezkednek el, hanem a domborzat szerint, vagy akár a régóta megtalált optimális kereskedelmi útvonal mentén. A további információk és heurisztika lehetővé teszi számunkra, hogy ésszerű időn belül elfogadható megoldásokat találjunk.

A probléma zárt és nyitott változatai

Az utazó eladó feladat zárt változatában a gráf összes csúcsát meg kell látogatni, majd vissza kell térni az eredeti csúcshoz. A nyitott változat abban különbözik a zárttól, hogy nem igényel visszatérést a kiinduló csúcsra.

A probléma nyitott változatát zárttá redukáljuk, ha a kezdőcsúcsban lévő ívek súlyait 0-ra cseréljük. Az ilyen grafikonon az optimális zárt utazó értékesítői útvonal megfelel az eredeti gráf optimális nyitott útvonalának.

Ahhoz, hogy egy zárt változatot egy nem zárttá redukáljunk, meg kell határozni egy olyan számot, amely szigorúan meghaladja az adott grafikonon lévő bármely utazó eladói útvonal súlyát (például vehetjük az egyes csúcsokból kimenő maximális súlyívek összegét 1-gyel növelve). Ezután új csúcsot kell hozzáadni a gráfhoz (feltételezzük, hogy az eredeti gráf csúcsai 0-tól ig vannak számozva , míg a kiinduló csúcs 0). A csúcsból kilépő és belépő ívek költségei a következők: $K$ $K$ $v_{n}$ $n-1$ $v_{n}$

$c_{n,i}=3K$
$c_{0,n}=3K$
$c_{i,n}=c_{i,0}+2K$ at tól ig $én$ $egy$ $n-1$

Az ilyen grafikonon az optimális, nem zárt utazó értékesítői útvonal megfelel az eredeti grafikonban szereplő optimális zárt utazó értékesítői útvonalnak, és magasabb a költsége. $2K$

Megoldási módszerek

Protozoa

kimerítő keresés
véletlenszerű felsorolás
mohó algoritmusok
- legközelebbi szomszéd módszer
- legközelebbi városbevonási módszer
- legolcsóbb módszer
minimális feszítőfa módszer
szimulált lágyítási módszer

Minden hatékony (a teljes felsorolást csökkentő) módszer az utazó eladó probléma megoldására heurisztikus módszer . A legtöbb heurisztikus módszer nem a leghatékonyabb útvonalat, hanem hozzávetőleges megoldást talál . Az úgynevezett any-time algoritmusok gyakran keresettek .[ pontosítani ] , vagyis valamilyen jelenlegi közelítő megoldás fokozatos javítása.

Példa a probléma metrikus változatának legegyszerűbb megoldására a minimális feszítőfák alkalmazása, amely közelítő tényezővel ad megoldást, és időbonyolultságú . Az ötlet az, hogy minden összekapcsolt gráf tartalmaz egy alacsonyabb költségküszöböt a részgráfjához, a minimális feszítőfához, és hogy minden olyan ciklus, amely legalább egyszer meglátogatja az egyes gráfcsúcsokat, költségoptimális útvonallá alakítható a metrika segítségével: $2$ $O(n^{2}\log n)$

Keresse meg a gráf minimális feszítőfáját . $T$ $G$
Hozzon létre egy gráfot az összes él megduplázásával . Tehát minden csúcsnak páros számú éle van. $T'$ $T$ $T'$
Keresse meg az Euler-ciklust . $T'$ $C'$
Csökkentse , kihagyja a duplázott éleket, ciklust kap . $C'$ $C$
Hozd ki . $C$

A közelítési tényező értékét a következőképpen bizonyítjuk: Legyen - a minimális feszítőfa, - ugyanaz a fa, de megkettőzött élekkel, - az Euler-ciklus a gráfon , - az algoritmus eredménye, - a minimális útvonal. Vegye figyelembe, hogy , valamint . Ekkor a közelítési tényező . $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$

A fenti módszer azonban optimalizálható, ha a páratlan számú szomszédos csúcsoknál az élek számát 1-gyel növeljük, ami megfelel az illeszkedő "páratlan" csúcsoknak. Fontos megjegyezni, hogy a "páratlan" csúcsok száma mindig páros, a kézfogási lemma alapján . Ilyen esetben az optimalizált algoritmus közelítő tényezővel és időbonyolultsággal rendelkezik . A bizonyítás előtt mutassuk meg, hogy , ahol egy illeszkedés és egy optimális útvonal: Legyen a minimális feszítőfa "páratlan" csúcsainak halmaza , és legyen a csúcsok átugrásával kapott ciklus . Nyilvánvaló, hogy páros hosszúságú, valamint két nem metsző maximális illesztése és , amelyekre és . Ebből az következik, hogy . Ez alapján megtaláljuk az algoritmus közelítési tényezőjét: . $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$

Vannak olyan beállítások is, amelyekben az utazó eladó probléma NP-teljessé válik . Az ilyen állítások általában így néznek ki: van-e olyan túra egy adott G gráfon , amelynek költsége nem haladja meg az x -et . Gyakran új megközelítéseket tesztelnek rajta a kimerítő keresés heurisztikus csökkentésére .

A gyakorlatban a hatékonyabb módszerek különféle módosításait alkalmazzák: az elágazó és kötött módszert és a genetikai algoritmusok módszerét , valamint a hangyatelep-algoritmust .

Elágazás és kötés módszer

Lehetőség van az utazó eladó problémájára pontos megoldást találni, vagyis az összes lehetséges útvonal hosszát „manuálisan” kiszámítani és a legkisebb hosszúságú útvonalat kiválasztani. Azonban még kis számú város esetében is gyakorlatilag lehetetlen így megoldani a problémát. Egy egyszerű változathoz, a városokkal szimmetrikus problémához, lehetséges útvonalak, vagyis 15 városra 43 milliárd, 18 városra pedig már 177 billió. A számítások időtartama milyen gyorsan növekszik a következő példán keresztül. Ha lenne olyan eszköz, amely 30 városra tudna megoldást találni egy óra alatt, akkor két további város ezerszer tovább tartana; vagyis több mint 40 nap. $n$ $(n-1)!/2$

A diszkrét optimalizálási módszerek, különösen az elágazó és kötött módszerek lehetővé teszik az optimális vagy közelítő megoldások megtalálását kellően nagy problémákra.

Geometriai értelmezésben ezek a módszerek a problémát konvex politópként, azaz többdimenziós sokszögként kezelik egy -dimenziós egységkockában , ahol egyenlő a gráf éleinek számával. Ennek az egységkockának minden csúcsa egy útvonalnak, azaz egy 0/1 elemű vektornak felel meg, amely kielégíti a fent leírt lineáris egyenlőtlenségeket. Az ezekkel az egyenlőtlenségekkel leírt hipersíkok levágják az egységkocka azon éleit, amelyek nem felelnek meg egyetlen útvonalnak sem. $m$ $[0,1]^{m}$ $m$

A szomszédos ábra a módszer alkalmazását mutatja három csomópont problémájára. Összhangban a három lehetséges élek között a csúcsok, bináris változók és összehasonlítjuk . Ebben az esetben csak egy lehetséges útvonal van, mégpedig az, amelyik három csúcson halad át. Ez az útvonal kielégíti az egyenlőtlenséget , amely kimondja, hogy egy útvonalnak legalább két csúcson kell áthaladnia. Ezen az útvonalon kívül, amely az (1,1,1) vektornak felel meg, ennek az egyenlőtlenségnek a pirossal jelölt részének minden pontja kielégíti az egyenlőtlenséget is. A piros vonalakon áthaladó síkok levágják a nem létező, legfeljebb egy élű pályáknak megfelelő összes sarkot, azaz nulla vektort (0, 0, 0), egységvektorokat (1, 0, 0), (0, 1, 0) és (0, 0, 1). Egy erős egyenlőtlenség mindent levág az egységkockából, kivéve az egyetlen érvényes pontot (1, 1, 1). Ebben a konkrét esetben ugyanaz a hatás érhető el három (1) típusú egyenlőtlenséggel. $x_{1},\,x_{2}$ $x_{3}$ $x_{1}+x_{2}+x_{3}\geqslant 2$ $x_{1}+x_{2}+x_{3}\geqslant 3$

A legkisebb hosszúságú megengedhető él meghatározásához olyan lineáris optimalizálási feladatsorokat kell megoldani, amelyek az egységkockából szükségtelen részeket vágnak le síkok vágásával, és az egységkockát az elágazás és kötés módszerrel kisebb politópokra kell felosztani.

Ez a módszer azonban általában nem elegendő az útvonalak gyors megtalálásához. Az egzakt módszerek fő előnye, hogy elegendő idővel a legrövidebb útvonalat számítják ki. Az optimális megoldások alsó határával megbecsülhető, hogy a talált útvonal mennyiben tér el az optimálistól. Például, ha alsó határa 100, és miután megtalálta a 102 hosszúságú útvonalat, az optimális útvonal 100 és 102 között lehet. Az úgynevezett optimalitási intervallum , vagy az optimális útvonal hossza és az útvonal közötti maximális relatív távolság. legrövidebb ismert útvonal, (102 - 100) /100 = 2%, azaz a talált 102 útvonal hossza maximum 2%-kal tér el az optimálistól. Ha a kiszámított útvonal hossza megegyezik az előző hosszával, akkor a megtalált megoldás optimálisnak tekinthető. Az elfogadható hosszúságú útvonalak megtalálásához az egzakt módszerek kombinálhatók heurisztikus módszerekkel.

Az utazó eladó probléma megoldásának elágazó és kötött módszerét 1963 -ban javasolta szerzők egy csoportja (J. Little, K. Murty, D. Sweeney, K. Carol) [3] .

Rugalmas hálózati módszer

Történelem

1987-ben Durbin és Willshaw használta, és rámutattak egy analógiára a rendezett neurális kapcsolatok létrehozásának mechanizmusaival [4] .

Az utazó eladó minden egyes útvonalát úgy tekintették, mint egy körnek a síkra való feltérképezését (e kör egy pontja a síkon minden városhoz van leképezve). A kör szomszédos pontjait a lehető legközelebbi és a síkon lévő pontokhoz kell leképezni.

Algoritmus

Egy kis kör felszerelésével kezdődik a síkon. Egyenetlenül terjeszkedik, gyűrűvé válik, amely szinte minden városon áthalad, és így létrehozza a kívánt útvonalat. A gyűrű minden mozgó pontját két összetevő befolyásolja: a pontot a legközelebbi város felé mozgatja, és a gyűrűn lévő pont szomszédai felé tolja el, hogy csökkentse a hosszát. A város végül csatlakozik a gyűrű egy bizonyos szakaszához, ahogy bővül. Ahogy egy ilyen rugalmas hálózat bővül, minden város a gyűrű egy bizonyos szakaszához kapcsolódik.

Kezdetben minden város megközelítőleg azonos befolyást gyakorol az egyes fordulópontokra. Ezt követően a nagyobb távolságok kevésbé befolyásolják, és minden város specifikusabbá válik a gyűrű hozzá legközelebb eső pontjaihoz. A specifitásnak ezt a fokozatos növekedését, amely a Kohonen hálózati tanulási módszerére emlékeztet, valamilyen effektív sugár értéke szabályozza.

Durbin és Willshaw kimutatta, hogy a Hopfield és Tank által vizsgált 30 város problémájára az elasztikus hálózati módszer körülbelül 1000 iterációban hozza létre a legrövidebb útvonalat. 100 város esetében az ezzel a módszerrel talált útvonal mindössze 1%-kal haladta meg az optimálisat.

Hangya algoritmus

Genetikai algoritmus

Dinamikus programozási algoritmus

A fő ötlet az, hogy kiszámítsuk és tároljuk az útvonalat az eredeti várostól a többi városig, majd ezt az értéket összegezzük a többi várostól a többi városig vezető útvonallal stb. Ennek a módszernek az előnye a brutális erő módszer a teljes térfogat számítások jelentős csökkenése a memória mennyiségének észrevehető növekedése miatt [5] . $D$ $F$ ${\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2},P_{F}=n!\kb. 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}$

Lásd még

Jegyzetek

↑ Gross JL, Yellen J. Gráfelmélet és alkalmazásai, 2006 , p. 275.
↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analysis Archivált : 2021. augusztus 19., a Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, p. 310-337.
↑ Kostevich L. S. Matematikai programozás: Inform. optimális megoldások technológiája: Proc. pótlék / L. S. Kostevich. - Minszk: Új ismeretek, 2003. ill., 150. o., ISBN 985-6516-83-8
↑ Richard Durbin, David Willshaw. Az utazó eladó problémájának analóg megközelítése rugalmas háló módszerrel // Természet . — 1987-04-22. — Vol. 326 , iss. 6114 . — P. 689–691 . - doi : 10.1038/326689a0 . Archiválva az eredetiből 2016. április 23-án.
↑ Korbut A. A., Finkelstein Yu. Yu. Diszkrét programozás. - M., Nauka, 1969. - C. 258-264

Irodalom

Levitin A. V. 3. fejezet: Brute Force Method: The Travelling Salesman Problem // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M .: Williams , 2006. - S. 159-160. — 576 p. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmusok: felépítés és elemzés = Introduction to Algorithms. - 2. kiadás - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
AZ ÉS. Bölcs. Az utazó eladó probléma . - M . : "Tudás" , 1969. - S. 62.
Ezhov A., Shumsky S. Neurocomputing és alkalmazásai a közgazdaságtanban és az üzleti életben . - M .: MEPhI , 1998. - S. 216.
Gross JL, Yellen J. Gráfelmélet és alkalmazásai. második kiadás. Boca Raton – London – New York: Chapman & Hall/CRC, 2006.

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma