Utazó eladó probléma - Travelling salesman problem

Az utazó eladó problémája (más néven utazó eladó probléma vagy TSP ) a következő kérdést teszi fel: "Tekintettel a városok listájára és az egyes várospárok közötti távolságokra, mi a legrövidebb útvonal, amely pontosan egyszer látogatja meg az egyes városokat, és visszatér a származási város? " Ez egy NP-nehéz probléma kombinatorikus optimalizálás , fontos elméleti számítógép-tudomány és operációkutatás .

Az utazó vevő és a jármű útválasztási problémája egyaránt a TSP általánosításai.

A számítási komplexitás elméletében a TSP döntési változata (ahol L hosszúság van megadva , a feladat annak eldöntése, hogy a gráfnak legfeljebb L körútja van-e ) az NP-teljes feladatok osztályába tartozik . Így lehetséges, hogy a TSP bármely algoritmusának legrosszabb futási ideje szuperpolinomálisan (de legfeljebb exponenciálisan ) nő a városok számával.

A problémát először 1930 -ban fogalmazták meg, és az egyik legintenzívebben vizsgált probléma az optimalizálás terén. Ezt használják a viszonyítási sok optimalizálási módszerek. Annak ellenére, hogy a probléma számítási szempontból nehéz, sok heurisztika és pontos algoritmus ismert, így néhány, több tízezer várossal rendelkező eset teljesen megoldható, és akár több millió város problémái is közelíthetők 1%-os töredékükön belül.

A TSP -nek még a legtisztább összetételében is számos alkalmazása van, például tervezés , logisztika és mikrochipek gyártása . Enyhén módosítva alproblémaként jelenik meg számos területen, például a DNS-szekvenálás során . Ezekben az alkalmazásokban, a koncepció város jelent, például az ügyfelek, forrasztási helyek, vagy a DNS-fragmentumok és a koncepció távolságot jelent az utazási idő és költségek vagy a hasonlósági mérték közötti DNS-fragmentumokat. A TSP megjelenik a csillagászatban is, mivel a sok forrást megfigyelő csillagászok minimalizálni akarják a távcső források közötti mozgatásával töltött időt; ilyen problémák esetén a TSP beágyazható egy optimális vezérlési problémába . Sok alkalmazásban további korlátozások, például korlátozott erőforrások vagy időablakok írhatók elő.

Történelem

Az utazó eladó problémájának eredete nem világos. Egy 1832 -ből származó kézikönyv utazó eladók számára említi a problémát, és példatúrákat tartalmaz Németországon és Svájcon keresztül , de nem tartalmaz matematikai kezelést.

Az utazó eladó problémáját a 19. században WR Hamilton ír matematikus és Thomas Kirkman brit matematikus fogalmazta meg matematikailag . Hamilton icosian játék volt rekreációs puzzle alapján találjanak Hamilton kör . Úgy tűnik, hogy a TSP általános formáját először az 1930-as években Bécsben és a Harvardon tanulmányozták matematikusok, nevezetesen Karl Menger , aki meghatározza a problémát, figyelembe veszi a nyilvánvaló nyers erő algoritmust, és figyeli a legközelebbi szomszéd heurisztikus:

Messenger problémával jelöljük (mivel a gyakorlatban ezt a kérdést minden postásnak meg kell oldania, különben is sok utazónak) azt a feladatot, hogy véges sok pont számára megtalálja a pontokat összekötő, legrövidebb útvonalat. Természetesen ez a probléma véges számú próbával megoldható. Nem ismertek azok a szabályok, amelyek a kísérletek számát az adott pontok permutációinak száma alá szorítanák. Az a szabály, hogy először a kiindulási pontról a legközelebbi pontra kell haladni, majd az ehhez legközelebb eső pontra stb., Általában nem a legrövidebb utat eredményezi.

Ezt először az 1930 -as években vette figyelembe matematikailag Merrill M. Flood, aki egy iskolabusz -útválasztási problémát akart megoldani. Hassler Whitney, a Princetoni Egyetem munkatársa felkeltette az érdeklődést a probléma iránt, amelyet "48 állam problémájának" nevezett. A legkorábbi kiadvány, amely az "utazó eladó problémája" kifejezést használta , Julia Robinson 1949 -es RAND Corporation jelentése: "A Hamilton -játékról (utazó eladó probléma").

Az 1950-es és 1960-as, a probléma egyre népszerűbb a tudományos körökben Európában és az USA-ban, miután a RAND Corporation a Santa Monica felajánlott díjakat lépéseket a probléma megoldásában. Jelentős hozzájárulás volt George Dantzig , Delbert Ray Fulkerson és Selmer M. Johnson a RAND Corporation -től, akik egész lineáris programként fejezték ki a problémát, és kidolgozták a vágási sík módszerét. Megírták azt a témát, amely az elsődleges dokumentumnak tekinthető, amelyben ezekkel az új módszerekkel 49 várossal egy példányt optimálisan megoldottak azáltal, hogy felépítettek egy turnét, és bebizonyították, hogy más túra nem lehet rövidebb. Dantzig, Fulkerson és Johnson azonban azt feltételezték, hogy egy közel optimális megoldás mellett képesek lehetünk megtalálni az optimáltságot, vagy bizonyítani az optimáltságot, ha hozzáadunk néhány extra egyenlőtlenséget (vágást). Ezt az ötletet arra használták, hogy a kezdeti 49 városi problémájukat húrmodell segítségével oldják meg. Azt találták, hogy csak 26 vágásra van szükségük ahhoz, hogy megoldást találjanak 49 városi problémájukra. Bár ez a tanulmány nem adott algoritmikus megközelítést a TSP -problémákhoz, a benne rejlő ötletek nélkülözhetetlenek voltak a későbbi pontos megoldási módszerek létrehozásához a TSP -hez, bár 15 évbe telne, amíg algoritmikus megközelítést találnak ezeknek a vágásoknak a létrehozására. A vágási sík módszerek mellett Dantzig, Fulkerson és Johnson talán először használt elágazó és kötött algoritmusokat.

1959 -ben Jillian Beardwood , JH Halton és John Hammersley közzétettek egy cikket "A legrövidebb út sok ponton keresztül" a Cambridge Philosophical Society folyóiratában. A Beardwood – Halton – Hammersley -tétel gyakorlati megoldást nyújt az utazó eladó problémájára. A szerzők aszimptotikus képletet határoztak meg annak érdekében, hogy meghatározzák a legrövidebb útvonal hosszát egy olyan eladó számára, aki otthonról vagy irodából indul, és meghatározott számú helyet keres fel, mielőtt visszatér a rajthoz.

A következő évtizedekben a matematika , az informatika , a kémia , a fizika és más tudományok számos kutatója tanulmányozta a problémát . A hatvanas években azonban új megközelítés jött létre, amely az optimális megoldások keresése helyett olyan megoldást eredményezne, amelynek hosszát bizonyíthatóan az optimális hosszúság többszöröse korlátozza, és ezáltal a probléma alsó határait hozza létre; ezeket az alsó határokat használnák elágazó és kötött megközelítésekkel. Ennek egyik módja az volt, hogy létrehoztunk egy minimális átívelő fát a gráfból, majd megduplázzuk annak minden élét, ami azt a kötöttséget eredményezi, hogy az optimális kör hossza legfeljebb kétszerese a minimális átívelő fa súlyának.

1976-ban Christofides és Serdyukov egymástól függetlenül nagy előrelépést tett ebben az irányban: a Christofides-Serdyukov algoritmus olyan megoldást eredményez, amely legrosszabb esetben legfeljebb 1,5-szer hosszabb, mint az optimális megoldás. Mivel az algoritmus egyszerű és gyors volt, sokan azt remélték, hogy utat engednek a közel optimális megoldási módnak. Ez azonban a javulás reményében nem valósult meg azonnal, és Christofides-Serdyukov maradt a legjobb legrosszabb forgatókönyv szerinti módszer 2011-ig, amikor egy (nagyon) kissé javított közelítési algoritmust fejlesztettek ki a "grafikus" TSP-k részhalmazára. 2020 -ban ezt az apró javulást kiterjesztették a teljes (metrikus) TSP -re.

Richard M. Karp 1972-ben kimutatta, hogy a Hamilton-ciklus probléma NP-teljes , ami a TSP NP-keménységét jelenti. Ez matematikai magyarázatot szolgáltatott az optimális túrák megtalálásának nyilvánvaló számítási nehézségeire.

Nagy előrelépés történt az 1970 -es évek végén és 1980 -ban, amikor Grötschelnek, Padbergnek, Rinaldinak és másoknak sikerült pontosan megoldani az eseteket akár 2392 várossal, vágógépek és ágak és kötések segítségével .

A kilencvenes években az Applegate , a Bixby , a Chvátal és a Cook kifejlesztette a Concorde programot , amelyet számos újabb lemezmegoldásban használtak. Gerhard Reinelt 1991 -ben publikálta a TSPLIB -t, amely különböző nehézségű benchmark példányok gyűjteménye, amelyet számos kutatócsoport használt az eredmények összehasonlítására. 2006-ban Cook és mások optimális túrát végeztek egy 85 900 városi példányon keresztül, amelyet egy mikrochip-elrendezési probléma adott, jelenleg a legnagyobb megoldott TSPLIB-példány. Sok más, több millió városra kiterjedő esetben találhatunk olyan megoldásokat, amelyek garantáltan az optimális túra 2-3% -án belül vannak.

Leírás

Grafikus problémaként

A TSP irányítatlan súlyozott gráfként modellezhető , így a városok a gráf csúcsai , az utak a gráf élei , és az út távolsága az él súlya. Ez minimalizálását probléma a kezdő és befejező a megadott vertex miután meglátogatták egymást csúcs pontosan egyszer. Gyakran előfordul, hogy a modell egy teljes gráf (azaz minden csúcspár élekkel van összekötve). Ha nincs út két város között, akkor a kellően hosszú él hozzáadásával befejeződik a grafikon anélkül, hogy befolyásolná az optimális túrát.

Aszimmetrikus és szimmetrikus

A szimmetrikus TSP -ben két város közötti távolság minden ellenkező irányban azonos, és irányítatlan gráfot képez . Ez a szimmetria felére csökkenti a lehetséges megoldások számát. Az aszimmetrikus TSP -ben az utak mindkét irányban nem létezhetnek, vagy a távolságok eltérőek lehetnek, és irányított gráfot alkotnak . A közlekedési ütközések , az egyirányú utcák , valamint a különböző indulási és érkezési díjakkal rendelkező városok repülőjegyei példák arra, hogyan romolhat ez a szimmetria.

Kapcsolódó problémák

• Egy egyenértékű megfogalmazás a gráfelmélet szempontjából: Ha egy teljes súlyozott gráfot adunk (ahol a csúcsok a városokat, az élek az utakat, a súlyok pedig az út költségeit vagy távolságát), keressenek egy Hamilton -ciklust . a legkisebb súly.
• A kiinduló városba való visszatérés követelménye nem változtatja meg a probléma számítási összetettségét , lásd Hamilton -út problémája .
• Egy másik kapcsolódó probléma a szűk keresztmetszetű utazó eladó problémája (szűk keresztmetszetű TSP): Keressen egy Hamilton -ciklust egy súlyozott grafikonon a legnehezebb él minimális súlyával . Például elkerülve a szűk utcákat nagy buszokkal. A probléma jelentős gyakorlati jelentőséggel bír, a nyilvánvaló szállítási és logisztikai területeken kívül. Klasszikus példa a nyomtatott áramkörök gyártása: a fúrógép útvonalának ütemezése a NYÁK -ba való fúráshoz. A robotizált megmunkálási vagy fúrási alkalmazásokban a "városok" a gép alkatrészei vagy lyukak (különböző méretűek) a fúráshoz, és az "útiköltség" magában foglalja a robot újratelepítéséhez szükséges időt (egy gépi munkák sorrendjének problémája).
• Az általános utazó eladó probléma , más néven "utazó politikus probléma", olyan "államokkal" foglalkozik, amelyeknek (egy vagy több) "városa" van, és az eladónak pontosan egy "várost" kell felkeresnie minden "államból". Egy alkalmazással találkozunk, amikor megoldást rendelünk a vágókészlet problémájára a késcserék minimalizálása érdekében. Egy másik a félvezetőgyártás fúrásával foglalkozik , lásd például az US 7,054,798 számú szabadalmat . Noon és Bean bebizonyították, hogy az általános utazó eladó problémát át lehet alakítani egy szokásos utazó eladó problémává, ugyanannyi várossal, de módosított távolságmátrixszal .
• A szekvenciális rendezési probléma azzal a problémával foglalkozik, hogy olyan városokat keres fel, ahol a városok közötti elsőbbségi kapcsolatok léteznek.
• A Google -nál gyakori interjúkérdés az, hogyan lehet az adatokat adatfeldolgozó csomópontok között átirányítani; az útvonalak az adatok átvitelétől függően változnak, de a csomópontok számítási teljesítményük és tárhelyük szerint is különböznek, ami tovább súlyosbítja az adatok küldésének problémáját.
• Az utazó vásárló problémája egy olyan vevővel foglalkozik, akinek feladata egy termékcsomag megvásárlása. Ezeket a termékeket több városban is megvásárolhatja, de eltérő áron, és nem minden város kínálja ugyanazokat a termékeket. A cél egy olyan útvonal megtalálása a városok egy része között, amely minimálisra csökkenti a teljes költséget (utazási költség + beszerzési költség), és lehetővé teszi az összes szükséges termék megvásárlását.

Egész szám lineáris programozási megfogalmazások

A TSP egész lineáris programként is megfogalmazható . Számos készítmény ismert. Két figyelemre méltó készítmény a Miller – Tucker – Zemlin (MTZ) és a Dantzig – Fulkerson – Johnson (DFJ) készítmény. A DFJ készítmény erősebb, bár az MTZ készítmény még mindig hasznos bizonyos beállításokban.

Miller – Tucker – Zemlin megfogalmazása

Címkézze meg a városokat számokkal, és határozza meg: ${\ displaystyle 1, \ ldots, n}$

${\ displaystyle x_ {ij} = {\ begin {case} 1 & {\ text {az út a városból megy}} i {\ text {városba}} j \\ 0 & {\ text {egyébként}} \ end {tok }}}$

Mert , hadd legyen egy dummy változó, és végül hogy legyen a távolság a város a városban . Ekkor a TSP a következő egész lineáris programozási problémaként írható fel: ${\ displaystyle i = 1, \ ldots, n}$${\ displaystyle u_ {i}}$${\ displaystyle c_ {ij}> 0}$${\ displaystyle i}$${\ displaystyle j}$

${\ displaystyle {\ begin {aligned} \ min & \ sum _ {i = 1}^{n} \ sum _ {j \ neq i, j = 1}^{n} c_ {ij} x_ {ij} \ vastagbél && \\ & x_ {ij} \ in \ {0,1 \} && i, j = 1, \ ldots, n; \\ & u_ {i} \ in \ mathbf {Z} && i = 2, \ ldots, n; \\ & \ sum _ {i = 1, i \ neq j}^{n} x_ {ij} = 1 && j = 1, \ ldots, n; \\ & \ sum _ {j = 1, j \ neq i} ^{n} x_ {ij} = 1 && i = 1, \ ldots, n; \\ & u_ {i} -u_ {j}+nx_ {ij} \ leq n-1 && 2 \ leq i \ neq j \ leq n; \ \ & 1 \ leq u_ {i} \ leq n-1 && 2 \ leq i \ leq n. \ End {aligned}}}$

Az első egyenlőségi csoport megköveteli, hogy minden város pontosan egy másik városból érkezzen, a második egyenlőségi csoport pedig azt, hogy minden városból pontosan egy másik városba kell indulni. Az utolsó megszorítások kikényszerítik, hogy csak egyetlen túra van, amely minden várost lefed, és nem két vagy több szétválasztott túra, amelyek csak együttesen fedik le az összes várost. Ennek bizonyítására az alábbiakban bemutatjuk (1), hogy minden megvalósítható megoldás csak egy zárt várossorozatot tartalmaz, és (2) hogy minden egyes túrára, amely minden várost lefed, vannak olyan értékek a dummy változóknak, amelyek megfelelnek a korlátozásoknak. (A dummy változók a túrarendelést jelzik, ami azt jelenti , hogy a várost meglátogatták a város előtt . Ezt úgy lehet elérni, hogy minden egyes látogatás alkalmával növekszik .) ${\ displaystyle u_ {i}}$${\ displaystyle u_ {i} <u_ {j}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle u_ {i}}$

Annak bizonyítására, hogy minden megvalósítható megoldás csak egy zárt várossorozatot tartalmaz, elegendő annak bemutatása, hogy a megvalósítható megoldás minden aljárója áthalad az 1 -es városon (megjegyezve, hogy az egyenlőség biztosítja, hogy csak egy ilyen túra lehet). Ha ugyanis összegezzük az összes egyenlőtlenséget, amely megfelel k lépés bármely részének, amely nem halad át az 1 -es városon, akkor a következőket kapjuk: ${\ displaystyle x_ {ij} = 1}$

${\ displaystyle nk \ leq (n-1) k,}$

ami ellentmondás.

Most be kell mutatni, hogy minden egyes városra kiterjedő túránál vannak értékek a dummy változókhoz, amelyek megfelelnek a korlátozásoknak. ${\ displaystyle u_ {i}}$

Az általánosság elvesztése nélkül határozza meg a túrát az 1. városban indulónak (és befejezőnek). Válassza ki, hogy a várost meglátogatta -e lépésben . Azután ${\ displaystyle u_ {i} = t}$${\ displaystyle i}$${\ displaystyle t (i, t = 1,2, \ ldots, n)}$

${\ displaystyle u_ {i} -u_ {j} \ leq n-1,}$

mivel nem lehet nagyobb és nem lehet kevesebb, mint 1; így a korlátok teljesülnek, ahol A , van: ${\ displaystyle u_ {i}}$${\ displaystyle n}$${\ displaystyle u_ {j}}$${\ displaystyle x_ {ij} = 0.}$${\ displaystyle x_ {ij} = 1}$

${\ displaystyle u_ {i} -u_ {j}+nx_ {ij} = (t)-(t+1)+n = n-1,}$

kielégítve a kényszert.

Dantzig – Fulkerson – Johnson készítmény

Címkézze meg a városokat 1,…, n számokkal, és határozza meg:

${\ displaystyle x_ {ij} = {\ begin {case} 1 & {\ text {az út a városból megy}} i {\ text {városba}} j \\ 0 & {\ text {egyébként}} \ end {tok }}}$

Vegyük a távolságot az i és a j város között . Ekkor a TSP a következő egész lineáris programozási problémaként írható fel: ${\ displaystyle c_ {ij}> 0}$

${\ displaystyle {\ begin {aligned} \ min & \ sum _ {i = 1}^{n} \ sum _ {j \ neq i, j = 1}^{n} c_ {ij} x_ {ij} \ kettőspont && \\ & \ sum _ {i = 1, i \ neq j}^{n} x_ {ij} = 1 && j = 1, \ ldots, n; \\ & \ sum _ {j = 1, j \ neq i}^{n} x_ {ij} = 1 && i = 1, \ ldots, n; \\ & \ sum _ {i \ in Q} {\ sum _ {j \ neq i, j \ in Q} {x_ { ij}}} \ leq | Q | -1 && \ forall Q \ subsetneq \ {1, \ ldots, n \}, | Q | \ geq 2 \\\ end {aligned}}}$

A DFJ megfogalmazás utolsó megszorítása biztosítja, hogy egyetlen megfelelő Q részhalmaz sem tud alkörútot alkotni, így a visszaadott megoldás egyetlen körút, és nem a kisebb körök egyesítése. Mivel ez exponenciális számú lehetséges korlátozáshoz vezet, a gyakorlatban ez késleltetett oszlopgenerálással oldható meg .

Megoldás kiszámítása

Az NP-nehéz problémák hagyományos támadási vonalai a következők:

• Pontos algoritmusok kidolgozása , amelyek ésszerűen gyorsan működnek, csak kis méretű problémák esetén.
• "Szuboptimális" vagy heurisztikus algoritmusok kidolgozása , azaz olyan algoritmusok, amelyek közelítő megoldásokat nyújtanak ésszerű időn belül.
• A probléma speciális eseteinek ("alproblémák") megtalálása, amelyeknél jobb vagy pontos heurisztika lehetséges.

Pontos algoritmusok

A legközvetlenebb megoldás az lenne, ha kipróbálnánk az összes permutációt (rendezett kombinációt), és megnéznénk, melyik a legolcsóbb ( nyers erő keresés segítségével ). A futási idő ezt a megközelítést belül van polinomiális tényező , a faktoriális a városok száma, így ez a megoldás lehetetlenné válik, még csak 20 városban. ${\ displaystyle O (n!)}$

A dinamikus programozás egyik legkorábbi alkalmazása a Held – Karp algoritmus, amely időben megoldja a problémát . Ezt a határértéket a kizárás-befogadás is elérte a dinamikus programozási megközelítést megelőző kísérletben. ${\ displaystyle O (n^{2} 2^{n})}$

Ezen időhatárok javítása nehéznek tűnik. Például nem határozták meg, hogy létezik -e pontos algoritmus a TSP -nek, amely időben fut . ${\ displaystyle O (1,9999^{n})}$

Egyéb megközelítések:

• Különféle elágazó és kötött algoritmusok, amelyek 40–60 várost tartalmazó TSP-k feldolgozására használhatók.

• Progresszív fejlesztési algoritmusok, amelyek lineáris programozásra emlékeztető technikákat használnak . Jól működik akár 200 városban is.
• Az ágazathoz kötött és a probléma-specifikus vágásgeneráció megvalósítása ( ág-vágás ); ez a választási módszer nagy példányok megoldására. Ez a megközelítés tartja a jelenlegi rekordot, és 85 900 várossal old meg egy példányt, lásd Applegate et al. (2006) .

2001-ben a TSPLIB-től 15 112 német városra találtak pontos megoldást George Dantzig , Ray Fulkerson és Selmer M. Johnson által 1954-ben javasolt lineáris programozáson alapuló vágási sík módszerrel . A számításokat a Rice Egyetemen és a Princetoni Egyetemen található 110 processzorból álló hálózaton végezték . A teljes számítási idő 22,6 évnek felelt meg egyetlen 500 MHz -es Alpha processzoron . 2004 májusában megoldódott az utazó eladó problémája, hogy Svédország mind a 24 978 városát meglátogassa: egy körülbelül 72 500 kilométeres túrát találtak, és bebizonyosodott, hogy nincs rövidebb túra. 2005 márciusában a Concorde TSP Solver segítségével megoldották azt az utazó eladó problémát, hogy meglátogatják az áramköri lap mind a 33 810 pontját : egy 66 048 945 egység hosszú túrát találtak, és bebizonyosodott, hogy nincs rövidebb túra. A számítás hozzávetőleg 15,7 CPU-évet vett igénybe (Cook et al. 2006). 2006 áprilisában egy 85 900 ponttal rendelkező példányt sikerült megoldani a Concorde TSP Solver segítségével , átvéve 136 CPU-évet, lásd Applegate et al. (2006) .

Heurisztikus és közelítő algoritmusok

Különféle heurisztikus és közelítő algoritmusokat dolgoztak ki, amelyek gyorsan jó megoldásokat hoznak. Ezek közé tartozik a Multi-fragment algoritmus . A modern módszerek ésszerű időn belül megoldásokat találhatnak rendkívül nagy problémákra (városok milliói), amelyek nagy valószínűséggel mindössze 2-3% -ra vannak az optimális megoldástól.

A heurisztika több kategóriáját ismerik el.

Konstruktív heurisztika

A legközelebbi szomszéd (NN) algoritmus ( mohó algoritmus ) lehetővé teszi az eladó számára, hogy a legközelebbi meglátogatott várost válassza. Ez az algoritmus gyorsan hatékonyan rövid útvonalat eredményez. N síkban véletlenszerűen elosztott városok esetében az algoritmus átlagosan 25% -kal hosszabb utat eredményez, mint a lehető legrövidebb út. Azonban sok speciálisan elrendezett városi elosztás létezik, amelyek miatt az NN algoritmus a legrosszabb útvonalat adja. Ez igaz mind az aszimmetrikus, mind a szimmetrikus TSP -re. Rosenkrantz és mtsai. megmutatta, hogy az NN algoritmus közelítő tényezővel rendelkezik a háromszög -egyenlőtlenséget kielégítő példányokra. Az NN algoritmus egyik változata, a legközelebbi töredék (NF) operátor, amely a legközelebbi meg nem látogatott városok csoportját (töredékét) köti össze, rövidebb útvonalakat találhat egymást követő iterációkkal. Az NF operátor alkalmazható az NN algoritmus által kapott kezdeti megoldásra is az elitista modell további javítása érdekében, ahol csak jobb megoldásokat fogadnak el. ${\ displaystyle \ Theta (\ log | V |)}$

A pontok halmazának bitonikus körútja a minimális kerületű monoton sokszög , amelynek csúcsai a pontok; dinamikus programozással hatékonyan kiszámítható .

Egy másik konstruktív heurisztika , a Match Twice and Stitch (MTS) két szekvenciális illesztést hajt végre , ahol a második illesztést az első illesztés összes szélének törlése után hajtják végre, hogy ciklusokat kapjanak. A ciklusokat ezután összevarrják, hogy elkészüljön az utolsó túra.

Christofides és Serdyukov algoritmusa

Az algoritmus Christofides és Serdyukov következik egy hasonló vázlatot, de ötvözi a minimális feszítőfa oldattal másik probléma, minimális súlyú teljes párosítás . Ez egy TSP túrát eredményez, amely legfeljebb 1,5 -szerese az optimálisnak. Ez volt az egyik első közelítő algoritmus , és részben azért volt felelős, hogy felhívja a figyelmet a közelítő algoritmusokra, mint a megoldhatatlan problémák gyakorlati megközelítésére. Ami azt illeti, az "algoritmus" kifejezést általában csak később terjesztették ki közelítő algoritmusokra; a Christofides algoritmust kezdetben Christofides heurisztikusnak nevezték.

Ez az algoritmus másként tekint a dolgokra a gráfelmélet eredményének felhasználásával, amely segít javítani a TSP alsó határán, amely a minimális átfedő fa költségeinek duplázásából származik. Adott egy Euler -grafikon , időben találunk egy Euler -túrát . Tehát ha rendelkeznénk egy Euler -gráffal, amelynek csúcsai a TSP -ből származó városok, akkor könnyen beláthatjuk, hogy egy ilyen módszert használhatnánk egy Euler -túra keresésére a TSP -megoldás megtalálásához. By háromszög egyenlőtlenség tudjuk, hogy a TSP túra nem lehet hosszabb, mint az Euler-túra, és mint ilyen, van egy alsó korlátot a TSP. Az alábbiakban egy ilyen módszert ismertetünk. ${\ displaystyle O (n)}$

1. Keressen egy minimális átfogó fát a problémához
2. Hozzon létre duplikátumokat minden élhez, hogy Euler -gráfot hozzon létre
3. Ehhez a grafikonhoz keressen egy Euler -túrát
4. Konvertálás TSP -re: ha egy várost kétszer látogatnak meg, hozzon létre egy parancsikont a városból ezt megelőzően a túrában az ezt követőhöz.

Az alsó határ javításához jobb módszerre van szükség az Euler -gráf létrehozásához. Háromszög egyenlőtlenség szerint a legjobb Euler -gráfnak ugyanolyan költségekkel kell rendelkeznie, mint a legjobb utazó értékesítő túrának, ezért az optimális Euler -gráfok megtalálása legalább olyan nehéz, mint a TSP. Az egyik módja ennek az, melyet a legkisebb súly megfelelő algoritmusok segítségével a . ${\ displaystyle O (n^{3})}$

A gráf Euler -gráffá alakítása a minimális átfogó fával kezdődik. Ezután a páratlan rendű csúcsokat párossá kell tenni. Tehát hozzá kell adni a páratlan fokú csúcsok illesztését, ami eggyel növeli minden páratlan fokú csúcs sorrendjét. Ezzel egy gráfot kapunk, ahol minden csúcs egyenletes rendű, tehát Eulerianus. A fenti módszer adaptálása Christofides és Serdyukov algoritmusát adja.

1. Keressen egy minimális átfogó fát a problémához
2. Hozzon létre párosítást a problémához a páratlan rendű városok halmazával.
3. Ehhez a grafikonhoz keressen egy Euler -túrát
4. Konvertáljon TSP -re parancsikonok segítségével.

Páros csere

A páronkénti csere vagy a 2-optika technika magában foglalja két szélének iteratív eltávolítását, és két különböző él helyettesítését, amelyek újra összekötik az élek eltávolításával létrehozott töredékeket egy új és rövidebb túrává. Hasonlóképpen, a 3-optikai technika eltávolít 3 élt, és újra összekapcsolja őket, hogy rövidebb túrát alkosson. Ezek a k -opt módszer speciális esetei . A Lin – Kernighan címke gyakran hallható téves megnevezés a 2-opt. A Lin – Kernighan valójában az általánosabb k-opt módszer.

Az euklideszi példák esetében a 2 optikai heurisztika átlagosan körülbelül 5% -kal jobb megoldásokat ad, mint Christofides algoritmusa. Ha egy mohó algoritmussal készített kezdeti megoldással kezdjük, akkor az átmozdulások átlagos száma ismét jelentősen csökken . Véletlenszerű indítások esetén azonban az átlagos mozgások száma . Annak ellenére, hogy ez csak kis méretnövekedés, a kezdeti lépések száma kisebb problémák esetén 10 -szer nagyobb a véletlenszerű induláshoz képest, mint a mohó heurisztikából. Ez azért van, mert az ilyen 2 optikai heurisztika a megoldás „rossz” részeit használja ki, például az átkelőhelyeket. Az ilyen típusú heurisztikákat gyakran használják a jármű -útválasztási problémák heurisztikájában az útvonal -megoldások újraoptimalizálására. ${\ displaystyle O (n)}$${\ displaystyle O (n \ log (n))}$

k -opt heurisztika, vagy Lin – Kernighan heurisztika

A Lin – Kernighan heurisztika a V -opt vagy változó -opt technika speciális esete . A következő lépéseket tartalmazza:

1. Egy körbejárás után törölje k egymást kölcsönösen szétválasztó élét.
2. Szerelje össze a fennmaradó töredékeket túrává, ne hagyjon szétválasztott részeket (vagyis ne kösse össze a töredék végpontjait). Ez valójában leegyszerűsíti a vizsgált TSP -t egy sokkal egyszerűbb problémává.
3. Minden töredékvégpont 2 k  - 2 másik lehetőséghez kapcsolható : a rendelkezésre álló 2 k töredék végpont közül a vizsgált töredék két végpontja nem engedélyezett. Egy ilyen korlátozott 2 k -város TSP -t ezután nyers erő módszerekkel lehet megoldani, hogy megtaláljuk az eredeti fragmentumok legkevésbé költséges rekombinációját.

A k -opt módszerek közül a legnépszerűbbek a 3-opt, amelyet Shen Lin, a Bell Labs 1965-ben mutatott be. A 3-opt különleges esete az, hogy az élek nem különülnek el (két él egymás mellett) . A gyakorlatban gyakran lehet jelentős javulást elérni a 2-opcióhoz képest az általános 3-opt kombinációs költségei nélkül, ha a 3-változtatásokat erre a speciális részhalmazra korlátozzák, ahol az eltávolított élek közül kettő szomszédos. Ez az úgynevezett két és fél opció jellemzően nagyjából félúton esik a 2 és a 3 opt között, mind az elért túrák minősége, mind a túrák eléréséhez szükséges idő tekintetében.

V -opt heurisztikus

A változó -opt módszer a k -opt metódushoz kapcsolódik és általánosít . Míg a k -opt metódusok rögzített számú ( k ) élt távolítanak el az eredeti körútból , addig a változó -opt módszerek nem határozzák meg az eltávolítandó élhalmaz méretét. Ehelyett a keresési folyamat során a készletet gyarapítják. Ebben a családban a legismertebb módszer a Lin – Kernighan módszer (fent említettük, mint a 2-opt félreértését). Shen Lin és Brian Kernighan először 1972 -ben tették közzé módszerüket, amely közel két évtizeden keresztül volt a legmegbízhatóbb heurisztika az utazó eladó problémáinak megoldására. David Johnson és kutatócsoportja fejlettebb, változó optikai módszereket fejlesztett ki a Bell Labs-ban az 1980-as évek végén. Ezek a módszerek (más néven Lin – Kernighan – Johnson ) a Lin – Kernighan módszerre építenek, és ötleteket adnak hozzá a tabu keresésből és az evolúciós számítástechnikából . Az alapvető Lin – Kernighan technika olyan eredményeket ad, amelyek garantáltan legalább 3 opt. A Lin – Kernighan – Johnson módszerek kiszámítják a Lin – Kernighan körutat, majd megzavarják a túrát azzal a mutációval, amelyet legalább négy élt eltávolítanak, és a túrát más módon kapcsolják vissza , majd V -az új túra kiválasztása. A mutáció gyakran elegendő ahhoz, hogy a turnét a Lin – Kernighan által azonosított helyi minimumtól elmozdítsuk . A V -opt módszereket széles körben a probléma legerősebb heurisztikájának tekintik, és képesek speciális esetek kezelésére, mint például a Hamilton -ciklus probléma és más nem metrikus TSP -k, amelyek más heurisztikáknál sikertelenek. Lin -Kernighan -Johnson sok éven át azonosított optimális megoldásokat minden olyan TSP -hez, ahol az optimális megoldás ismert, és azonosította a legismertebb megoldásokat az összes többi TSP -hez, amelyeken a módszert kipróbálták.

Véletlenszerű javulás

Az optimalizált Markov-lánc- algoritmusok, amelyek helyi keresési heurisztikus alalgoritmusokat használnak, rendkívül közel találhatók az optimális útvonalhoz 700-800 városban.

A TSP egy próbakő számos általános heurisztika számára, amelyeket kombinatorikus optimalizálásra terveztek, mint például a genetikai algoritmusok , a szimulált lágyítás , a tabu keresés , a hangyakolonia optimalizálása , a folyóképződés dinamikája (lásd rajrajz ) és a kereszt entrópia módszer .

Hangya kolónia optimalizálása

A mesterséges intelligencia kutatója, Marco Dorigo 1993 -ban leírt egy módszert, amellyel heurisztikus módon "jó megoldásokat" hozhat létre a TSP -hez az ACS ( hangyakolónia rendszer ) nevű hangya -kolónia szimulációja segítségével . Ez modellek megfigyelt viselkedés valós hangyák, hogy a rövid utak között az élelmiszer-források és a fészket, egy kialakulóban eredő viselkedés egyes hangya előnyben követni trail feromonok által letétbe helyezett más hangyák.

Az ACS nagyszámú virtuális hangya -ügynököt küld ki, hogy feltérképezze a térképen lehetséges útvonalakat. Valószínűleg minden hangya a heurisztika alapján választja ki a következő várost, amelyet meg kell látogatnia. A hangyák felfedezik, és feromont raknak le minden egyes peremükön, amíg át nem mennek. Ezen a ponton a hangya, aki befejezte a legrövidebb túrát, virtuális feromont rak le teljes körútvonalán ( globális nyomvonal frissítés ). A lerakott feromon mennyisége fordítottan arányos a túra hosszával: minél rövidebb a túra, annál több lerakódik.

Különleges esetek

Metrikus

A metrikus TSP-ben , más néven delta-TSP vagy Δ-TSP, a helyközi távolságok kielégítik a háromszög egyenlőtlenségét .

A TSP természetes korlátozása, hogy megköveteli, hogy a városok közötti távolságok metrikát képezzenek a háromszög -egyenlőtlenség kielégítésére ; hogy a közvetlen kapcsolatot a A , hogy a B sohasem távolabb, mint a az útvonalon keresztül közbenső C :

${\ displaystyle d_ {AB} \ leq d_ {AC}+d_ {CB}}$.

Az élek átívelnek, majd metrikát építenek a csúcsok halmazára. Ha a városokat a sík pontjainak tekintjük, sok természetes távolságfüggvény metrika, és a TSP sok természetes példája kielégíti ezt a korlátozást.

Az alábbiakban bemutatunk néhány példát a metrikus TSP -kre a különböző mutatókhoz.

• Az euklideszi TSP -ben (lásd alább) a két város közötti távolság a megfelelő pontok közötti euklideszi távolság .
• Az egyenes vonalú TSP -ben a két város közötti távolság az x - és y - koordinátáik különbségeinek abszolút értékeinek összege . Ezt a metrikát gyakran Manhattan távolság- vagy városrész-metrikának nevezik .
• A maximális metrikában a két pont közötti távolság az x - és y - koordinátáik különbségeinek abszolút értékeinek maximuma .

Az utolsó két mutató például egy olyan gép irányításakor jelenik meg, amely meghatározott lyukakat fúr a nyomtatott áramköri lapra . A manhattani metrika egy olyan gépnek felel meg, amely először az egyik, majd a másik koordinátát állítja be, így az új pontra való átállás ideje mindkét mozgás összege. A maximális metrika egy olyan gépnek felel meg, amely mindkét koordinátát egyidejűleg állítja be, így az új pontra való átállás ideje a két mozgás közül a lassabb.

Definíciójában a TSP nem teszi lehetővé a városok kétszeri látogatását, de sok alkalmazásnak nincs szüksége erre a korlátozásra. Ilyen esetekben a szimmetrikus, nem metrikus példány metrikusra redukálható. Ez az eredeti gráfot egy teljes gráffal helyettesíti, amelyben a városok közötti távolságot az eredeti gráf A és B közötti legrövidebb útvonala váltja fel . ${\ displaystyle d_ {AB}}$

Euklideszi

Ha a bemeneti számok tetszőleges valós számok lehetnek, akkor az euklideszi TSP a metrikus TSP sajátos esete, mivel a síkban mért távolságok engedelmeskednek a háromszög -egyenlőtlenségnek. Ha a bemeneti számoknak egésznek kell lenniük, akkor a túrák hosszának összehasonlítása magában foglalja a négyzetgyökösszegek összehasonlítását is.

Az általános TSP-hez hasonlóan az euklideszi TSP mindkét esetben NP-kemény. Racionális koordinátákkal és diszkretizált metrikával (a távolságok egész számra kerekítve) a probléma NP-teljes. A racionális koordinátákkal és a tényleges euklideszi metrikával az Euklideszi TSP a számlálási hierarchiában, a PSPACE alosztályában ismert. Önkényes valós koordinátákkal az euklideszi TSP nem lehet ilyen osztályokban, mivel számtalan lehetséges bemenet létezik. Azonban az euklideszi TSP valószínűleg a legegyszerűbb verzió a közelítéshez. Például az euklideszi TSP egy példányához társított gráf minimális átfedési fája egy euklideszi minimális átfedési fa , és így kiszámítható a várható O ( n log n ) időben n pontért (lényegesen kevesebb, mint az élek száma) ). Ez lehetővé teszi, hogy a TSP egyszerű, 2-közelítő algoritmusa gyorsabban működjön a fenti háromszög-egyenlőtlenségekkel.

Általánosságban elmondható, hogy minden c > 0 esetén, ahol d az euklideszi tér dimenzióinak száma, létezik egy polinom-idejű algoritmus, amely legfeljebb (1 + 1/ c ) -kor találja meg az optimális geometriai példányok hosszát . TSP be

${\ displaystyle O \ left (n (\ log n)^{(O (c {\ sqrt {d}})))^{d-1}} \ right),}$

idő; ezt polinomiális idő közelítési sémának (PTAS) nevezik. Sanjeev Arora és Joseph SB Mitchell 2010 -ben elnyerték a Gödel -díjat azért, mert egyidejűleg felfedezték az euklideszi TSP PTAS -ját.

A gyakorlatban továbbra is egyszerűbb heurisztikákat alkalmaznak gyengébb garanciákkal.

Aszimmetrikus

A legtöbb esetben a TSP hálózat két csomópontja közötti távolság mindkét irányban azonos. A esetben, ha a távolság a A és B nem egyenlő a távolság a B , hogy egy úgynevezett aszimmetrikus TSP. Az aszimmetrikus TSP gyakorlati alkalmazása az útvonal-optimalizálás utcaszintű útválasztással (amelyet aszimmetrikusak az egyirányú utcák, csúszópályák, autópályák stb.).

Átalakítás szimmetrikusra

Az aszimmetrikus TSP gráf megoldása némileg összetett lehet. Az alábbiakban egy 3 × 3 -as mátrixot találunk, amely tartalmazza az A , B és C csomópontok közötti lehetséges útvonalakat . Az egyik lehetőség az, hogy egy N méretű aszimmetrikus mátrixot 2 N méretű szimmetrikus mátrixsá alakítunk .

Aszimmetrikus pályasúlyok

	A	B	C
A		1	2
B	6		3
C	5	4

A méret megduplázásához a grafikon minden csomópontja megismétlődik, létrehozva egy második szellemcsomópontot , amely az eredeti csomóponthoz kapcsolódik, nagyon alacsony (esetleg negatív) súlyú "szellem" éllel, itt jelölve - w . (Alternatívaként a szellemélek súlya 0, és a w súly hozzáadódik az összes többi élhez.) A fent látható eredeti 3 × 3 mátrix látható a bal alsó sarokban, és az eredeti transzponálása a jobb felső sarokban. A mátrix mindkét példányának átlóját az alacsony költségű ugrási utak váltották fel, amelyeket- w jelöl . Az új gráfban egyetlen él sem kapcsolja össze közvetlenül az eredeti csomópontokat, és egyetlen él sem közvetlenül a szellemcsomópontokat.

Szimmetrikus pályasúlyok

	A	B	C	A ′	B '	C '
A				- w	6	5
B				1	- w	4
C				2	3	- w
A ′	- w	1	2
B '	6	- w	3
C '	5	4	- w

A tömeg - w a „szellem” élek összeköti a szellem csomópontok a megfelelő eredeti csomópontok elég alacsonynak kell lennie, hogy biztosítsa, hogy minden szellem élek kell tartozniuk minden optimális szimmetrikus TSP megoldás az új gráf (w = 0 nem mindig elég alacsony ). Ennek eredményeként az optimális szimmetrikus körmenetben minden eredeti csomópont megjelenik a szellemcsomópontja mellett (pl. Lehetséges útvonal ), és az eredeti és szellemcsomópontok újbóli egyesítésével (optimális) megoldást kapunk az eredeti aszimmetrikus problémára ( példa, ). ${\ displaystyle \ mathrm {A \ to A '\ to C \ to C' \ to B \ to B '\ to A}}$${\ displaystyle \ mathrm {A \ to C \ to B \ to A}}$

Elemző probléma

Hasonló probléma merül fel a geometriai méréselméletben is, amely a következőket kérdezi: milyen feltételek mellett lehet az euklideszi tér E részhalmazát tartalmazni egy korrigálható görbében (azaz mikor létezik véges hosszúságú görbe, amely E minden pontját felkeresi )? Ezt a problémát az elemző utazó eladó problémájának nevezik .

Útvonal hossza négyzetben lévő véletlenszerű ponthalmazokhoz

Tegyük fel, hogy független véletlen változók, amelyek egyenletes eloszlása ​​van a négyzetben , és legyen a legrövidebb úthossz (azaz TSP megoldás) ehhez a ponthalmazhoz, a szokásos euklideszi távolságnak megfelelően . Ismeretes, hogy szinte biztosan, ${\ displaystyle X_ {1}, \ ldots, X_ {n}}$${\ displaystyle n}$${\ displaystyle [0,1]^{2}}$${\ displaystyle L_ {n}^{\ ast}}$

${\ displaystyle {\ frac {L_ {n}^{*}} {\ sqrt {n}}} \ rightarrow \ beta \ qquad {\ text {when}} n \ to \ infty,}$

ahol van egy pozitív állandó, amelyet nem ismerünk kifejezetten. Mivel (lásd alább) a korlátozott konvergencia -tételből következik, hogy ezért az alsó és felső határok a határoktól kezdve következnek . ${\ displaystyle \ beta}$${\ displaystyle L_ {n}^{*} \ leq 2 {\ sqrt {n}}+2}$${\ displaystyle \ beta = \ lim _ {n \ to \ infty} \ mathbb {E} [L_ {n}^{*}]/{\ sqrt {n}}}$${\ displaystyle \ beta}$${\ displaystyle \ mathbb {E} [L_ {n}^{*}]}$

Az szinte biztos, korlát , mint nem létezik, ha a független helyeken vannak helyettesítve megfigyeléseit stacionárius ergodikus folyamat egységes marginális. ${\ displaystyle {\ frac {L_ {n}^{*}} {\ sqrt {n}}} \ rightarrow \ beta}$${\ displaystyle n \ to \ infty}$${\ displaystyle X_ {1}, \ ldots, X_ {n}}$

Felső korlát

• Az egyik az , ezért úgy, hogy egy naiv úton, amely látogatók monoton pontok belül minden szelet szélessége a téren.${\ displaystyle L^{*} \ leq 2 {\ sqrt {n}}+2}$${\ displaystyle \ beta \ leq 2}$${\ displaystyle {\ sqrt {n}}}$${\ displaystyle 1/{\ sqrt {n}}}$
• Kevés bizonyult , így , később javult Karloff (1987): .${\ displaystyle L_ {n}^{*} \ leq {\ sqrt {2n}}+1,75}$${\ displaystyle \ beta \ leq {\ sqrt {2}}}$${\ displaystyle \ beta \ leq 0.984 {\ sqrt {2}}}$
• Egyes tanulmányok felső határról számoltak be .${\ displaystyle \ beta \ leq 0.73 \ dots}$

Alsó határ

• Ha megfigyeljük, hogy nagyobb, mint a távolság a legközelebbi pont közötti távolság , akkor kapunk (rövid számítás után)${\ displaystyle \ mathbb {E} [L_ {n}^{*}]}$${\ displaystyle n}$${\ displaystyle X_ {0}}$${\ displaystyle X_ {i} \ neq X_ {0}}$

${\ displaystyle \ mathbb {E} [L_ {n}^{*}] \ geq {\ tfrac {1} {2}} {\ sqrt {n}}.}$

• Jobb alsó korlátot kapunk, ha megfigyeljük, hogy nagyobb, mint a szorzata a legközelebbi és második legközelebbi pont közötti távolság összegének , ami${\ displaystyle \ mathbb {E} [L_ {n}^{*}]}$${\ displaystyle {\ tfrac {1} {2}} n}$${\ displaystyle X_ {0}}$${\ displaystyle X_ {i}, X_ {j} \ neq X_ {0}}$

${\ displaystyle \ mathbb {E} [L_ {n}^{*}] \ geq \ left ({\ tfrac {1} {4}}+{\ tfrac {3} {8}} \ jobb) {\ sqrt {n}} = {\ tfrac {5} {8}} {\ sqrt {n}},}$

• Jelenleg a legjobb alsó határ

${\ displaystyle \ mathbb {E} [L_ {n}^{*}] \ geq ({\ tfrac {5} {8}}+{\ tfrac {19} {5184}}) {\ sqrt {n}} ,}$

• Held és Karp olyan polinom-idő algoritmust adott, amely számszerű alsó határokat biztosít , és így többé-kevésbé 1%-ig jónak tűnik. Különösen David S. Johnson kapott alsó határt számítógépes kísérlettel:${\ displaystyle L_ {n}^{*}}$${\ displaystyle \ beta (\ simeq L_ {n}^{*}/{\ sqrt {n}})}$

${\ displaystyle L_ {n}^{*} \ gtrsim 0,7080 {\ sqrt {n}}+0,522,}$

ahol 0,522 a négyzethatár közeli pontokból származik, amelyeknek kevesebb szomszédja van, és Christine L. Valenzuela és Antonia J. Jones a következő számszerű alsó határt kapta:

${\ displaystyle L_ {n}^{*} \ gtrsim 0.7078 {\ sqrt {n}}+0.551}$.

Számítási komplexitás

A probléma NP-nehéznek bizonyult (pontosabban az FP ^NP komplexitási osztályra teljes ; lásd függvényfeladat ), és a döntési probléma verziója ("tekintettel a költségekre és az x számra , döntse el, hogy van-e forduló -útvonal olcsóbb, mint x ") NP-teljes . A szűk keresztmetszetű utazó eladó problémája szintén NP-nehéz. A probléma akkor is NP-nehéz marad, ha a városok euklideszi távolságú síkban vannak , valamint számos más korlátozó esetben. Az egyes városok „csak egyszer” meglátogatásának feltételének megszüntetése nem szünteti meg az NP-keménységet, mivel síkban van egy optimális túra, amely csak egyszer látogatja meg az egyes városokat (különben a háromszög egyenlőtlensége miatt egy parancsikon, amely kihagyja az ismételt látogatást nem növelné a túra hosszát).

A közelítés összetettsége

Általánosságban elmondható, hogy a legrövidebb utazó értékesítő túra megtalálása nonprofit szervezet . Ha a távolságmérő metrikus (és így szimmetrikus), akkor a probléma APX -teljessé válik, és Christofides és Serdyukov algoritmusa 1,5 -en belül közelíti meg. A 2020 -as előnyomtatás ezt javítja . A legismertebb megközelíthetetlenségi korlát a 123/122. ${\ displaystyle 1.5-10^{-36}}$

Ha a távolságok 1 -re és 2 -re vannak korlátozva (de metrikusak), akkor a közelítési arány 8/7 lesz. A háromszög -egyenlőtlenségű aszimmetrikus esetben a közelmúltig csak logaritmikus teljesítménygaranciák voltak ismertek. 2018 -ban állandó tényező közelítést dolgoztak ki Svensson, Tarnawski és Végh. A legjobb jelenlegi algoritmus, Traub és Vygen, eléri a teljesítményarányt . A legismertebb megközelíthetetlenségi korlát a 75/74. ${\ displaystyle 22+ \ varepsilon}$

A leghosszabb utazó értékesítő túra megtalálásának megfelelő maximalizálási problémája megközelítőleg 63/38. Ha a távolságfüggvény szimmetrikus, akkor a leghosszabb túra 4/3 -on belül determinisztikus algoritmussal, belül pedig randomizált algoritmussal közelíthető meg . ${\ displaystyle {\ tfrac {1} {25}} (33+ \ varepsilon)}$

Emberi és állati teljesítmény

A TSP, különösen a probléma euklideszi változata felkeltette a kognitív pszichológia kutatóinak figyelmét . Megfigyelték, hogy az emberek képesek az optimálishoz közeli megoldásokat gyorsan, közel lineáris módon előállítani, a teljesítményük 1% -kal alacsonyabb a 10-20 csomóponttal rendelkező grafikonoknál, és 11% -kal kevésbé hatékony a grafikonoknál. 120 csomópont. A látszólagos könnyedség, amellyel az emberek pontosan generálnak optimális megközelítésű megoldásokat a problémára, arra késztette a kutatókat, hogy feltételezzék, hogy az emberek egy vagy több heurisztikát alkalmaznak, a két legnépszerűbb elmélet vitathatatlanul a domború hajótest hipotézise és a keresztezés elkerülése heurisztika. További bizonyítékok azonban arra utalnak, hogy az emberi teljesítmény meglehetősen változatos, és úgy tűnik, hogy az egyéni különbségek, valamint a gráf geometriája befolyásolja a feladat teljesítményét. Mindazonáltal az eredmények azt sugallják, hogy a számítógép teljesítménye a TSP -n javítható az emberek által ezekhez a problémákhoz használt módszerek megértésével és emulálásával, és új ismeretekhez vezetett az emberi gondolkodás mechanizmusairól. A Journal of Problem Solving első száma a TSP -n az emberi teljesítmény témakörével foglalkozott, és egy 2011 -es áttekintés tucatnyi dokumentumot sorolt ​​fel a témában.

Egy 2011 -es tanulmány az állatok megismeréséről "Hadd vezesse a buszt a galamb" címmel, amely a Gyermek ne engedd, hogy a galamb vezessen buszt című gyermekkönyvről kapta a nevét . , a galambok térbeli megismerését vizsgálta azáltal, hogy tanulmányozta repülési szokásaikat több etető között egy laboratóriumban az utazó eladó problémájával kapcsolatban. Az első kísérletben galambokat helyeztek el egy laboratóriumi szoba sarkában, és hagyták őket repülni a közeli, borsót tartalmazó etetőkhöz. A kutatók azt találták, hogy a galambok nagyrészt a közelséget használták annak eldöntésére, hogy melyik etetőt választják legközelebb. A második kísérletben az etetőket úgy rendezték el, hogy a lehető legközelebbi etetőhöz való repülés minden alkalommal nagymértékben hatástalan lenne, ha a galamboknak szükségük lenne minden etető meglátogatására. A második kísérlet eredményei azt mutatják, hogy a galambok, bár továbbra is a közelségen alapuló megoldásokat részesítik előnyben, "több lépést tudnak előre tervezni az útvonal mentén, amikor a közelségen alapuló hatékony és kevésbé hatékony útvonalak közötti utazási költségek különbségei nagyobbak lesznek". Ezek az eredmények összhangban vannak más, nem főemlősökkel végzett kísérletekkel, amelyek bebizonyították, hogy egyes nem főemlősök képesek voltak összetett utazási útvonalak megtervezésére. Ez arra utal, hogy a nem főemlősök viszonylag kifinomult térbeli kognitív képességekkel rendelkeznek.

Természetes számítás

Ha az élelmiszerforrások térbeli konfigurációját mutatják be, az amőboid Physarum polycephalum alakítja a morfológiáját, hogy hatékony utat hozzon létre az élelmiszerforrások között, amely szintén megközelítő megoldás lehet a TSP -nek.

Referenciaértékek

A TSP algoritmusok benchmarkingjához a TSPLIB a TSP mintapéldányainak könyvtára, és a kapcsolódó problémák fennmaradnak, lásd a TSPLIB külső hivatkozást. Sok közülük a tényleges városok listája és a tényleges nyomtatott áramkörök elrendezése .

Népszerű kultúra

• Az utazó értékesítő , Timothy Lanzone rendező, négy matematikus története, akiket az amerikai kormány bérelt fel, hogy megoldja a számítástechnika történetének legmegfoghatatlanabb problémáját: P kontra NP .

Lásd még

• Kanadai utazói probléma
• Pontos algoritmus
• Útvonal -ellenőrzési probléma (más néven "kínai postás probléma")
• Állítsa be a TSP problémát
• Königsberg hét hídja
• Steiner utazó eladó problémája
• Metró kihívás
• Tube Challenge
• Jármű útválasztási probléma
• Grafikon feltárása

Megjegyzések

Hivatkozások

További irodalom

Külső linkek

• Utazó eladó problémája a Wayback Machine -nél (archiválva 2013. december 17 -én) a Waterloo Egyetemen
• TSPLIB a Heidelbergi Egyetemen
• Utazó eladó problémája , Jon McLoone a Wolfram demonstrációs projektben
• TSP vizualizációs eszköz