Problem trgovačkog putnika

Problem trgovačkog putnika postavlja sledeće pitanje: S obzirom na spisak gradova i daljina između svakog para gradova, koji je najkraći mogući put da se poseti svaki grad tačno jednom i vrati se u početni grad? To je NP-teški problem problem kombinatorne optimizacije, važno u Operacionim istraživanjima i Teoretskom računarstvu.

Problem je prvi put formulisan u 1930. godine i jedan je od najintezivnijih problema u optimizaciji. Koristi se kao reper za mnoge metode optimizacije. Iako je problem računski teži, veliki broj heurističkih i metode su poznate, tako da su neki slučajevi sa desetinama hiljada gradova biti rešeni.

TSP ima nekoliko aplikacija još u svojoj formulaciji, kao što su planiranje, logistika, a proizvodnja mikročipovi. Malo izmenjena, izgleda kao pod-problem u mnogim oblastima, kao što su DNK sekvenciranje. U ovim aplikacijama, koncept grad predstavlja, na primer, kupci, lemljenje tačkama, ili fragmenata DNK, a koncept distanca predstavlja putovanje puta ili trošak ili sličnost između fragmenata DNK. U mnogim aplikacijama, dodatna ograničenja, kao što su ograničeni resursi ili vremenski prozori koji su znatno teži. TSP je specijalni slučaj Problem trgovačkog putnika.

U Teoriji kompleksnosti, odluka verzija TSP (gde je, s obzirom na dužinu L, zadatak je da odluči da li kod grafa je postojalo putovanje kraće od L) pripada klasi NP-kompletnih problema. Dakle, vrlo je verovatno da Najbolji, najgori i prosečan slučaj vreme izvršavanja jednog algoritma za TSP eksponencijalnog rasta sa brojem gradova.

Istorija

Vilijam Rovan Hamilton

Problem porekla trgovačkog putnika je nejasan. Priručnik trgovačkog putnika od 1832. godine, pominje problem i obuhvata ture kroz primere Nemačke i Švajcarske, ali ne sadrži matematički tretman "Der Handlungsreisende - Vie er Sein und soll bio er zu Tun {sic šešir, um Auftrage zu erhalten und eines glucklichen Erfolgs u Seinen magazinov GEVISS zu sein - von einem Alten komi-Voiageur " (trgovački putnik - kako on mora da bude i šta treba da uradi kako bi bili sigurni da obavlja svoje zadatke i imaju uspeha u njegovom biznis - od visoke ko-Voiageur) trgovački putnik Problem je definisan u 1800. god., od Irskog matematičara VR Hamilton i od strane britanskog matematičar Tomas Kirkman. Hamiltonova Icosian igre je rekreativna slagalica zasnovana na pronalaženju Hamiltonovog puta diskusija početkom rada Hamilton i Kirkman mogu se naći u Graph Theori 1736-1936 opšti oblik TSP izgleda. Da ima je prvo studirao matematičari tokom 1930-ih godina u Beču i na Harvardu, naročito od strane Karl Menger, koji definiše problem, smatra da je očigledno brute-force algoritma, i posmatra ne-optimalnost najbližeg suseda heuristike: {{ Ponuda | Ćemo označiti po glasnika problemom (jer se u praksi ovo pitanje treba da se reši svaki poštar, u svakom slučaju i mnogi putnici) zadatak da pronađe, za konačno mnogo bodova čiji Pairvise rastojanja su poznata, najkraći put koji povezuje tačke. Naravno, ovaj problem je rešiv od konačno mnogo suđenja. Pravila kojima bi se broj suđenja ispod broj permutacija od datih tačaka, nisu poznata. Pravilo da se prvo ide od početne tačke do najbliže tačke, zatim do tačke zatvaranja.

Problem trgovačkog putnika je definisan u 1800. godine, od strane Irskog matematičara Vilijam Rouan-a Hamilton-a i od strane Britanskog matematičara Tomas-a Kirkman-a. Hamiltonova Icosian igre je rekreativna slagalica zasnovana na pronalaženju Hamiltonovog ciklusa, diskusija početkom rada Hamilton-a i Kirkman-a mogu se naći u Teoriji grafova 1736-1936 opšti oblik TSP izgleda. Da ima je prvo studirao matematičari tokom 1930-ih godina u Beču i na Harvardu, naročito od strane Karl Menger-a, koji definiše problem, smatra da je očigledno brute-force algoritma, i posmatra ne-optimalnost najbližeg suseda heuristike. Zadatak da pronađe, za konačno mnogo bodova čiji Pairvise rastojanja su poznati, najkraći put koji povezuje tačke. Naravno, ovaj problem je rešiv od konačno mnogo suđenja. Pravila koja bi se broj suđenja ispod broja permutacija od datih tačaka, nisu poznati. Pravilo da se prvo ide od početne tačke do najbliže tačke, zatim do tačke najbliže njoj, itd, uopšte ne daje najkraći put. Cited i engleski prevod Originalni Nemački: "Vir bezeichnen als Botenproblem' (Veil Diese Zahtevaj u von der Prakis jedem Postboten, ubrigens auch zu od vielen Reisenden losen ist) umreti Aufgabe, fur Endlich viele Punkte, Deren paarveise Abstande bekannt Sind, Den kurzesten Die točki verbindenden Veg zu finden. Dieses Problem ist Naturlich stets durch Endlich Viele Versuche losbar. Pravila, velche Die Količestvo Versuche unter die Količestvo Permutationen der gegebenen Punkte herunterdrucken vurden, sind nicht bekannt. Die Regel, čovek Solle vom Ausgangspunkt predhodno zum nachstgeleg.

Tokom 1950-ih i 1960-ih, problem je postao veoma popularan u naučnim krugovima u Evropi i SAD. Značajni doprinos dali su Džordž Dantzig, Delbert Rej Fulkerson i Selmer M. Johnson u RAND Corporation u Santa Monikci, koji je izrazio problem kao ceo broj linearni programa i razvio sečenje, metod za njegovo rešavanje. Sa ovim novim metodama su rešeni instancu sa 49 gradova u optimalnosti narednim decenijama, problem je proučavana od strane mnogih istraživača iz oblasti Matematike, informatike, hemije, fizike, i druge nauke. Ričard M. Karp pokazao je 1972. god. da Hamiltonov ciklus problem NP-kompletan, što podrazumeva Np težak problem. Ovo isporučuje matematički objašnjenje očiglednim računarskom teškoće u pronalaženju optimalnih rešenja. Veliki napredak je napravljen krajem 1970-ih i 1980-ih, kada Grotschel, Padberg, Rinaldi i drugi uspeli da tačno reši slučajeve u gradovima do 2392, korišćenjem najnovije avione i filijala-i-vezan. U 1990, Applegate, Bikbi, Vašek Chvatal-a i Vilijam-a J. Cook razvija program Konkord, koji se koristi u mnogim rešenjima. Gerhard Reinelt objavila TSPLIB 1991, kolekciju benčmark slučajeva različite težine, koja je u upotrebi od strane mnogih istraživačkih grupa za poređenje rezultata. U 2006. god., Kuk i drugi izračunava optimalanu turneju kroz 85,900 gradskom primer dao mikročipom raspored problema, trenutno najveći rešen TSPLIB instance. Za mnoge druge slučajeve sa milionima gradova, rešenje se može naći da se garantuje da se u roku od 1% od optimalne turneje.

Opis

Problem grafa

Simetrična TSP sa četiri grada

TSP je modelovan kao [neusmeren graf] ], tako da su grafovi grafikon temena, staze su na grafikonu je ivice, a put ' , a udaljenost je ivica dužine. To je problem minimizacije počinje i završava se u određenom posle posete jedni druge tačno jednom. Često, model je kompletan graf (tj.' svaki paru čvorova povezanih ivica). Ako ne postoji put između dva grafa, dodajući proizvoljno ivica će završiti graf bez uticaja na optimalnu turneju.

Asimetričnost i Simetričnost

Simetrični TSP je rastojanje između dva grada je ista u svakom suprotnom smeru, stvarajući neusmerenim grafom. Ova simetrija prepolovi broj od mogućih rešenja. U asimetrične TSP, putevi ne mogu da postoje u oba smera ili razdaljine mogu biti različite, formirajući usmereni graf. Avio karte za gradove sa različitim polaska i dolaska naknade su primeri kako ova simetrija može razbiti.

Postavka problema

Ako je dat određen broj gradova, cene putovanja od bilo kog grada do bilo kog grada, koja je najjeftinija ruta koja obilazi svaki grad tačno jednom, i vraća se u početni grad? Ekvivalentan problem izražen u terminima teorije grafova bi glasio: Dat je kompletan težinski graf (čiji čvorovi predstavljaju gradove, grane predstavljaju puteve, a težine predstavljaju cenu putovanja, ili dužinu puta) - naći Hamiltonov ciklus najmanje težine. Može se pokazati da zahtev da se vrati u početni grad ne menja računsku kompleksnost ovog problema. Rešenje ovog problema je od velikog praktičnog značaja, ne samo u pitanju saobraćaja. Dobar primer u kome je bitno na efikasan način rešiti Problem trgovačkog putnika bi mogla da bude organizacija teretne luke: Ako se u luci u svakom trenutku nalazi više hiljada kontejnera, naslaganih jedni na druge, i svakodnevno se stotine kontejnera iskrcavaju sa brodova, ili tovare na šlepere, koji je optimalan redosled kretanja kranova za utovar i istovar, i gde postaviti koji kontejner.

ILP formulaciju

TSP se može formulisati kao celobrojno programiranje.

${\begin{aligned}\min &\sum _{i\neq j}c_{ij}x_{ij}&\\0\leq &x_{ij}\leq 1&\forall i,j\\&x_{i,j}{\text{ ceo broj}}&\forall i,j\\&\sum _{i=0,i\neq j}^{n}x_{ij}=1&j=0,\ldots ,n\\&\sum _{j=0,j\neq i}^{n}x_{ij}=1&i=1,\ldots ,n\\u_{i}-u_{j}&+nx_{ij}\leq n-1&1\leq i\neq j\leq n\\u_{i}\geq 0&&1\leq i\leq n.\end{aligned}}$

I navedenom formulacijom, $c_{ij}$ odgovara udaljenosti između gradova $i$ and $j$ and $x_{ij}$ označava da li je put od grada i do grada j je uključen u turneji. Poslednja prepreka nameće da postoji samo jedna tura. Da bismo to dokazali, mora se dokazati da je (1) svako moguće rešenje je turneja i (2) da za svaku mogućem turneju, postoje vrednosti za $u_{i}$ that satisfy the constraints. Da bi dokazao da je svaki izvodljivo rešenje turneje, dovoljno je pokazati da je svaki subtour u prihvatljivom rešenju prolazi kroz grad 0 jer to implicira da može da postoji samo jedna tura koja obuhvata sve gradove. Da bismo to dokazali, pretpostavimo niz gradova $i_{1},\ldots ,i_{k}$ formira subtour koji ne uključuje Siti 0. Sumirajući odgovarajuća ograničenja za ove grafove,

${\begin{aligned}u_{i_{j}}-u_{i_{j+1}}+n&\leq n-1\qquad j=1,\ldots ,k-1\\u_{i_{k}}-u_{i_{1}}+n&\leq n-1\end{aligned}}$

daje

$kn\leq kn-k,$

što je kontradikcija. Dakle, svaki subtour u prihvatljivom rešenju prolazi kroz graf i tako svaki 0 izvodljivo rešenje. Sada mora da se pokaže da za svaku moguću turu postoje vrednosti za $u_{i}$koji zadovoljavaju ograničenja. Neka redosleda gradova $i_{0},\ldots ,i_{n}$ biti neka $u_{i_{t}}=t$ for $t=0,\ldots ,n$. onda je $x_{i_{j},i_{k}}=0$,

$u_{i_{j}}-u_{i_{k}}\leq n-1,$

koja ima osim u slučaju $u_{i_{j}}=n$ i $u_{i_{k}}=0$. Međutim, ovaj slučaj se isključuje jer je put od grafa $i_{n}$ to city $i_{0}$ is in the tour. If $x_{i_{j},i_{k}}=1$, onda mora biti zadovoljan

$u_{i_{j}}-u_{i_{k}}+n\leq n-1.$

To važi, jer $x_{i_{j},i_{k}}=1$ only if $i_{j}$ and $i_{k}$ uzastopni su grafovi (and $i_{j}\neq n,i_{k}\neq 0$) i onda $u_{i_{j}}-u_{i_{k}}=-1$.

Computing rešenje

Tradicionalne linije napada za NP-teških problema su sledeći: . * Izrada algoritama za traženje tačne rešenja (oni će raditi razumno brzo samo za mali problem veličine) * Izrada heuristickog algoritma , odnosno, algoritmi koji pružaju bilo naizgled ili verovatno dobra rešenja, ali koja ne može da se pokazao kao optimalan. * Pronalaženje posebne slučajeve za problem ("subproblems") za koje je bio bolji ili tačan heuristike su moguće.

Složenost izračunavanja

Problem je pokazala da je NP-težak (preciznije, to je potpuna i zbog kompleksnosti klase FPNP), a problem odlučivanja verzija ("s obzirom na troškove i broj k, odlučiti da li postoji tura put jeftinije od k ") je NP-kompletan. Usko grlo problem trgovačkog putnika je NP-težak. Problem ostaje NP-težak čak i za slučaj kada su gradovi su u ravni sa Euklidskih udaljenostima, kao i u brojnim drugim slučajevima restriktivne. Uklanjanje stanje poseti svaki grad "samo jednom" ne ukloni NP-tvrdoće, jer se lako može videti da je u planarna slučaju postoji optimalan turneje koja posećuje svaki grad samo jednom (inače, po trougao nejednakost, prečica koja preskače ponavljanjem posetu ne bi povećanje dužine turneje).

Složenost aproksimacije

U opštem slučaju, pronalaženje najkraće trgovačkog putnika turneju je NPO-kompletan. Ako je udaljenost mera metrički i simetrični, problem postaje APKS-kompletan i Christofides algoritam je približan u 1.5.

Ako su rastojanja ograničena na 1 i 2 (ali i dalje su metrička) aproksimacija odnos postaje 7/6. U slučaju asimetrične, metrički slučaj, poznati su samo logaritamske performanse garancije, najbolji trenutni algoritam postiže odnos performanse 0,814 log n, to je otvoreno pitanje da li postoji stalni faktor aproksimacija.

Odgovarajući maksimizacija problem nalaženja najdužih trgovačkog putnika je aproksimirati turneju u 63/38. Ako rastojanje funkcija je simetrična, najduža turneja može aproksimirati u 4/3 od deterministički algoritam $(33+\epsilon )/25$ od slučajnog algoritma.

Tačni algoritmi

Najdirektnije rešenje bi bilo da probate sve permutacije (poređani kombinacije) i videli koji je najjeftiniji (koristeći brutalnu silu pretragu). Vreme izvršavanja ovog pristupa leži u polinoma faktora $O(n!)$, broja gradova, tako da je ovo rešenje postaje nepraktično i za samo 20 gradova. Jedna od prvih primena dinamičkog programiranja je Held-Karp algoritam koji rešava problem na vreme $O(n^{2}2^{n})$ od slučajnog algoritma.

[[Датотека:Bruteforce.gif|framed|center|

Rešenje na TSP sa 7 gradova koji koriste brutalnu silu pretragu. Napomena: Broj permutacija: (7-1)!/2 = 360

Dinamičko programiranje rešenje zahteva eksponencijalni prostor. Korišćenje uključivanja u isključenosti, problem se može rešiti na vreme u okviru polinoma faktor $2^{n}$ polinoma i prostora. Poboljšanje ove vremenske granice izgleda teško. Na primer, još uvek nije utvrđeno da li je tačan algoritam za TSP koji radi na vreme $O(1.9999^{n})$ postoji.

Drugi pristupi uključuju:

• Razni filijala-i-vezane algoritmi, koji se mogu koristiti za obradu TSP-a sadrže 40-60 gradova.

Rešenje o TSP sa 7 gradova koristeći jednostavan Grane i vezan algoritam. Napomena: broj permutacija je mnogo manje nego grubom silom pretragu

• Progresivno poboljšanje algoritama koji koriste tehnike koje podsećaju linearnog programiranja. Radi dobro za do 200 gradova.
• Implementacija grane-i-vezan i problema specifičnih rez generacije (filijala-i-rez), to je metoda izbora za rešavanje velikih slučajeva. Ovaj pristup ima trenutni rekord, rešavanje instancu sa 85.900 gradovima.

Tačan rešenje za 15.112 nemačkih gradova od TSPLIB pronađen je u 2001 koristeći najsavremenije metode avion koji je predložio Džordž Dantzig, Rai Fulkerson i Selmer M. Johnson 1954, na osnovu linearnog programiranja.

Heuristički algoritmi i aproksimacija

Razni heuristike, algoritmi i aproksimacija koja će brzo dati dobra rešenja su osmišljena. Savremene metode mogu pronaći rešenja za izuzetno velike probleme (milioni gradova) u razumnom vremenskom periodu koji su sa velikom verovatnoćom samo 2-3% daleko od optimalnog rešenja. Nekoliko kategorija heuristike priznaju.

Konstruktivne heuristike

Najbliži sused algoritam za TSP sa 7 gradova. Rešenje promene kao polazna tačka se menja

Najbliži komšija (NN) algoritam (ili tzv. pohlepni algoritam) omogućava prodavac odabrati najbližu neposećeni grad kao svoj sledeći potez. Ovaj algoritam brzo prinosi efikasno kratak put. Za N gradova nasumično raspoređenih u avionu, algoritam na prosečnih prinosa put 25% duži od najkraći mogući put. Međutim, postoje mnoge posebno organizovan gradski sistemi koji čine NN algoritam daje najgori put (Gutin, Jeo , i Zverovich, 2002). Ovo važi i za asimetrične i simetrične TSP-a (Gutin i Ieo, 2007). Pokazali su da algoritam ima aproksimacije faktor $\Theta (\log |V|)$ slučajevima za zadovoljavanje nejednakost trougla. Varijacija NN algoritma, pozvao Najbliža fragment (NF) operatora, koji povezuje grupu (odlomak) od najbližih neposećeni gradova, možete naći kraći put sa uzastopnih iteracija. NF operater može se primeniti i na početnoj rešenja dobijenog NN algoritma za dalje usavršavanje u elitistički model, gde se prihvataju samo bolja rešenja. Izgradnju na osnovu rrazapinjućeg stabla minimalnog stepena imaju približan odnos 2. Christofides algoritam postiže odnos od 1,5. Bitonic turneja skup tačaka je minimalna-perimetar monoton poligon koji ima tačke kao svoje čvorova, može da se efikasno izračuna pomoću dinamičkog programiranja. Još jedan konstruktivan heuristički, meč dva puta i Stitch (MTS) (Kahng, Reda 2004), obavlja dve uzastopne matchings, gde se drugi podudaranja izvršava nakon brisanja sve ivice prvog uparivanja, da daju niz ciklusa. Ciklusi su tada zašili da proizvede finalni turneju.

Iterativno poboljšanje

Pairvise razmena

Pojava udvojenih razmena ili 2-opt tehnika podrazumeva iterativno uklanjanje dve oštrice i zamene ih sa dve različite ivice da ponovo uspostavi fragmente nastale uklanjanjem ivice u novu i kraće turneje. Ovo je specijalni slučaj k-opt metodom. Imajte na umu da oznaka Lin-Kernighan je često pogrešno čuo za 2-opt. Lin-Kernighan je zapravo opštiji k-opt metoda.

k-opt heuristički, ili Lin-Kernighan heuristike

Uzmite dati obilazak i brisanje k međusobno nepovezane ivice. Ponovo preostale fragmente na turneji, i ne ostavlja iščašen subtours (to jest, ne povezuju krajnje tačke fragment je). Ovaj efekat u pojednostavljuje TSP koji razmatramo u mnogo jednostavniji problem. Svaki fragment krajnja tačka može biti povezan sa 2k - 2 druge mogućnosti: od fragmenata 2k ukupnih raspoloživih krajnjih tačaka, dve krajnje tačke u fragmentu koji se razmatra je nedopušteno. Takva otežana 2k-grad TSP se mogu rešiti sa brutalnim metodama da pronađu bar-cost rekombinacijom originalnih fragmenata. K-opt tehnika je specijalni slučaj V-izuzimanje ili promenljiva opt-tehnike. Najpopularniji k-opt metode su 3-opt, i oni su uvedene od strane Shen Lina iz Bell Labs 1965. Postoji poseban slučaj 3-opt gde ivice nisu iščašen (dva od ivice susedni jedni drugima). U praksi, često je moguće da se ostvari značajan napredak u odnosu na 2-opt bez kombinatorne štetu opštih 3-opt ograničavanjem 3-promene u ovom posebnom podgrupom kojoj dva od uklonjenih ivica susedni. Ovaj takozvani dva-i-po-opredeljuju obično pada oko pola puta između 2-opt i 3-opt, kako u pogledu kvaliteta ture postignutih i vreme potrebno za postizanje te ture.

V-opt heuristički

Promenljiva-opt metod je povezana i generalizacija k-opt metodom. Dok k-opt metode uklonite fiksni broj (k) od ivica iz originalnog turneje, promenljiva-opt metode ne popravi veličinu ivice postavljen za uklanjanje. Umesto toga, oni rastu kao skup pretraživanje proces se nastavlja. Najpoznatiji metod u ovoj porodici je Lin-Kernighan metod (gore pomenuto kao pogrešno upotrebljava za 2-opt). Šen Lin i Brajan Kernighan prvi objavio svoj metod u 1972, a to je najpouzdaniji heuristike za rešavanje problema trgovačkog putnika skoro dve decenije. Napredniji promenljiva opt-metode su razvijene u Bell Labs u kasnim 1980 Dejvid Džonson i njegov istraživački tim. Ove metode (ponekad se naziva Lin-Kernighan-Džonson) grade na Lin-Kernighan metodom, dodajući ideje tabu pretraživanje i evolutivnog računarstva. Osnovni Lin-Kernighan tehnika daje rezultate koji su garantovano da bude najmanje 3-opt. LIN-Kernighan-Johnson metoda izračuna Lin-Kernighan turneju, a zatim Perturb turneju po onome što je opisano kao mutacijom koja uklanja najmanje četiri ivice i ponovno povezivanje turneju na drugačiji način, a zatim V-odluče na novu turneju. Mutacija je često dovoljno da se kreće u obilazak od lokalnog minimuma prepoznaje po Lin-Kernighan. V-opt metode se široko smatra kao najmoćnije heuristike za problem, i da su mogli da se bave posebnim slučajevima, kao što je Hamilton ciklusa problema i drugih ne-metričkih TSP-a koji ne uspevaju na druge heuristike. Dugi niz godina, Lin-Kernighan-Džonson je utvrdila optimalna rešenja za sve TSP-a gde je optimalno rešenje poznatih i identifikovana su najpoznatije rešenja za sve ostale TSP na koji je način je suđeno.

Randomizirano poboljšanje

Optimizovani Markovljevi lanci algoritmi koji koriste lokalne potrazi heuristika pod-algoritmi mogu naći put veoma blizu optimalnog puta za 700 i 800 gradova. TSP je probni kamen za mnoge opšte heuristike stvorenim za kombinatorne optimizacije, kao što su genetskih algoritama, simulirano žarenje, Tabu traženje, kolonija mrava optimizacija i dinamika formiranje.

Optimizacija kolonije mrava

Veštačka inteligencija istraživač Marko Dorigo je opisao 1997. godine heuristički metod generisanja "dobrih rešenja" za TSP koristeći mravlji algoritam (енгл. Ant colony optimization algorithms, ACO). Kao osnovu je iskoristio ponašanje realnih mrava, koje je primetio u prirodi. Naći kratke staze između izvora hrane i svoje gnezdo, hitno ponašanje uzrokovano želji svakog mrava da prati trag feromona deponovana od strane drugih mrava. ACS šalje veliki broj virtuelnih mrava agenata za istraživanje mnogih moguće trase na mapi. Svaki mrav probabilistički bira sledeći grad da poseti osnovu heuristike kombinuje razdaljinu do grada i iznos virtuelnog feromona deponovana na ivici do grada. Mravi istražuju, deponovanje feromona na svakoj ivici da pređe, dok svi oni su završili turneju. U ovom trenutku mrav koji završi najkraćem turneje depozita virtuelni feromona duž svoje trase potpune turneje (globalna ruta ažuriranje). Iznos deponovanih feromona je obrnuto proporcionalna dužini turneje: kraće turneje, viši depoziti.

Ant Coloni Optimization Algoritam za TSP sa 7 gradova: crveno i debele linije u feromona karte ukazuju na prisustvo više feromona

Posebni slučajevi

Metrički TSP

U metrike TSP, takođe poznat kao Delta ili TSP-Δ-TSP, međumesni rastojanja zadovoljiti trougao nejednakost. vrlo prirodno ograničenje TSP je da zahteva da se udaljenost između gradova formiraju metriku da zadovolji trougao nejednakost, koji je direktna veza od A do B nikad dalje od pravca preko C: $d_{AB}\leq d_{AC}+d_{CB}$.

Edge obuhvata zatim izgraditi metriku na skupu temena. Kada su se gradovi posmatraju kao tačke u ravni, mnogi prirodni rastojanje funkcija a su metrike, a toliko prirodni slučajevi zadovoljavaju TSP to ograničenje. Slede neki primeri metričkih TSPs za razne metrike. * U Euklidov TSP (vidi dole) rastojanje između dva grada je Euklidovo rastojanje između odgovarajućih tačaka. * U pravolinijskom TSP rastojanje između dva grada je zbir razlike u njihovimx i y-koordinatama.

Ova metrika se često naziva Menhetn rastojanje ili grad-blok metrike. * U maksimum metrički, rastojanje između dve tačke je maksimum apsolutnih vrednosti razlika od svojih x i y-koordinata. Poslednje dve metrike se pojavljuju na primer u rutiranje mašinu koja bušilice dati skup rupa u štampana ploča. Manhattan metrika odgovara mašinu koja podešava prvi koji koordinira, a zatim drugi, pa je vreme da se presele u nove tačke je zbir oba pokreta. Maksimalne metričkih odgovara mašinu koja istovremeno podešava obe koordinate, tako da je vreme da se presele u nove tačke je sporiji od ova dva pokreta.

U svojoj definiciji, TSP ne dozvoljava gradovima da se dva puta posete, ali mnogim aplikacijama ne treba to ograničenje. U takvim slučajevima, simetrični, nemetričkim instancama može se svesti na jedan metrički. Ovo zamenjuje originalni graf sa kompletnim grafom koji racuna gracko rastojanje $d_{AB}$ zamenjuje najkraći put između $A$ i $B$ i originalnog grafa.

Raspon minimalne mreže $G$je donja granica razmaka od optimalne trase, jer brisanje bilo koje ivice u optimalnoj ruti prinose Hamiltonova putanja, koji je u spanning tree $G$.U TSP sa [[]] trougao neravnopravnosti slučaj je moguće dokazati preko gornje granice u pogledu minimalnog spanning tree i dizajn algoritam koji ima dokazivi gornja granica raspona trase. Prva objavljena (i najjednostavnija) primer sledi:

1. Izgraditi minimalnu Spanning Tree $T$ for $G$.
2. Duplirati sve ivice $T$. To je, gde god postoji ivica od U da V, dodajte Druga prednost od V da u. To nam daje Ojlerov graf $H$.
3. Pronađi Ojlerov krug $C$ u $H$. Jasno, raspona dva puta raspon od drveta.
4. Konvertovati Ojlerov krug u Hamiltonov ciklusa na sledeći način: šetnja, a svaki put kad treba da dođu u već posećena temena, preskočite ga i idu na sledeći.

Lako je dokazati da je poslednji korak radi. Štaviše, zahvaljujući nejednakosti trougla, svaka preskakanje u koraku 4 u stvari prečica, odnosno, dužina ciklusa ne povećava. Stoga nam daje TSP turneju ne više od dva puta duže od optimalan.

Christofides algoritam sledi sličan nacrt već kombinuje minimalni Spanning Tree rastvorom drugog problema, minimalna težina-savršeno podudaranje. Ovo daje TSP turneju koja je najviše 1,5 puta optimalna. Christofides algoritam je bio jedan od prvih aproksimacija algoritma a, i bio je delimično odgovorna za skretanje pažnje na približavanja algoritmima kao praktičan pristup nerešivi problemi. U stvari, izraz "algoritam" nije uobičajeno produžen do približavanja algoritama kasnije, Christofides algoritam je u početku naziva Christofides heuristike.

U slucaju da je udaljenost između gradova su sve ili jedan ili dva (a time i nejednakost trougla je nužno zadovoljan), postoji polinom-vreme aproksimacija algoritam koji pronalazi obilazak dužine najviše 8/7 puta optimalna tura dužine Berman , Karpinski.P. Berman (2006). Marek Karpinski, "Algoritam za 8/7-Approkimation (1,2)-TSP", Proc. 17. ACM-SIAM soda (2006), str 641-648.</ref> Međutim, to je dugogodišnji (od 1975) otvoren problem da se poboljša Christofides faktor približavanja od 1,5 za opšte metrički TSP na manje konstante. Poznato je da, ukoliko P = NP,najbolje da polinom-algoritam može naći obilazak dužine 123/122 puta Optimalna dužina ture Karpinski, Lampis i Schmied. Za asimetrične TSP je osnovna granica iznosi 75/74 . U slučaju ograničenja pokazalo se da je najbolje vreme polinom algoritam može da uradi je da se izgradi turneju dužine 337/336 puta optimalnoj dužini Tour, osim akoP = NP Za slučaj asimetrične granica je 135/134.

Euklidov TSP

Euklidska TSP, ili planarna TSP, je TSP sa distance sada običan euklidska distanca. Euklidov TSP je pojedinačan slučaj metričkih TSP, jer razdaljine u avionu poštuju nejednakost trougla. Kao opšte TSP, euklidska TSP (a samim tim i opšte metrički TSP) je NP-kompletan. Međutim, u nekim aspektima se čini da je lakše nego opšte metrike kašičice. Na primer, minimalno razapinjuće stablo grafa je povezano sa instancom Evklidovog TSP-a, to je Euklidska minimalno rayapinjuće stablo, pa se može izračunati u očekivanom O (n log n) za n tačaka (znatno manji od broja ivica). Ovo omogućava jednostavnu 2-aproksimacije algoritam za TSP sa nejednakosti trougla gore da radi brže. U principu, za svako c > 0, gde je d broj dimenzija u Euklidov prostor, postoji polinom-algoritam koji pronalazi obilazak dužine najviše (1 + 1 / c) puta optimalna za geometrijskih slučajeva TSP u $O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)$ vremenu; to se zove polinom-vreme aproksimacija šema (PTAS) Sanjev Arora i Josif SB Mičel je dobio nagradu u 2010 Gedel za njihovo istovremeno otkriće PTAS za Euklidov TSP. U praksi, heuristike sa lošijim garancije i dalje da se koristi.

Asimetrična TSP

U većini slučajeva, rastojanje između dva čvora u mreži TSP je isti u oba smera. Slučaj kada je rastojanje od A do B nije jednaka udaljenosti od B do A asimetrični TSP. Praktična primena asimetričnog TSP je put optimizaciji korišćenja uličnih rutiranje (koji je napravljen od asimetričnih jednosmerne ulice, klizanje-puteva, autoputeva i sl).

Rešavanje konverzijom u simetrični TSP

Rešavanje asimetričnu TSP grafikon može biti donekle složen. Sledi 3 × 3 matrica koja sadrži sve moguće putanje težine između čvorova A, B i C. Jedna od opcija je da se okrenu asimetričnu matricu veličine N u simmetričeskoj matrice veličine 2N.

Asimetrični put težine

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

Da bi udvostručio veličinu, svaki od čvorova u grafu je duplirana, kreirajući drugi duh čvor. Korišćenje duple poene sa veoma niskim težine, kao što su - ∞, pruža jeftin put "povezivanje" vrati na pravi čvor i simetrična evaluacija omogućava da se nastavi. Originalni 3 × 3 matrica prikazan gore je vidljiv u donjem levom i obrnuto od originala u vrhu desno. Oba primerka su matrice su njihovi dijagonale zamenjene deševie hop stazama, predstavljaju - ∞.

Simetrični put težine

	A	B	C	A′	B′	C′
A				−∞	6	5
B				1	−∞	4
C				2	3	−∞
A′	−∞	1	2
B′	6	−∞	3
C′	5	4	−∞

Originalni 3 × 3 matrica će proizvoditi dva Hamiltonovih ciklusa (put da poseti jednom svaki čvor), odnosno ABCA [ocena 9] i ACBA [ocena 12]. Procena 6 × 6 simetrična verzija istog problema sada proizvodi mnogo puteva, uključujući AA'-BB'-CC'-, AB'-CA'-, AA'-BC'-[sve ocena 9 - ∞] . Važna stvar u vezi sa svakom novom nizu je da će biti smenjivanje isprekidana (', B', C ') i UN-isprekidana čvorova (A, B, C) i da su povezane na "skok" ; vezi između jednog para (AA) je efikasno besplatno. Verzija algoritma može da koristi bilo koju težinu za put na AA ', dok je težina manja od svih drugih putanja pondera prisutne u grafikonu. Kao put težinu da "skoči" mora da bude efikasno "slobodan", vrednost nula (0) može da se koristi za predstavljanje ove troškova nula ukoliko se ne koristi u druge svrhe već (kao što su određivanje nevažeće putanje). U dva gore navedenim primerima, nepostojeće staze između čvorova su prikazani kao prazan kvadrat.

Merila

Za benchmarking TSP algoritama, TSPLIB je biblioteka uzoraka instanci TSP i srodnih problema se održava, pogledajte TSPLIB spoljnu referencu. Mnogi od njih su liste stvarnih gradova i rasporeda stvarnih štampanih ploča.

Ljudska predstava o TSP

TSP, posebno evklidova varijanti problema, privukao je pažnju istraživača u kognitivnoj psihologiji. Primećuje se da su ljudi u stanju da brzo dati dobre kvalitetna rešenja. Prvi broj časopisa za rešavanje problema je posvećen temi ljudske performanse na kašičice.

TSP Dužina puta po random pointset u kvadrat

Pretpostavimo N tačke su nasumično raspoređeni u 1 × 1 kvadrat sa N >> 1. Razmislite mnogo takvih kvadrata. Pretpostavimo da želimo da znamo prosek najkraći put dužine (tj. rešenje TSP) za svaki kvadrat.

Donja granica

${\frac {1}{2}}{\sqrt {N}}$ je donja granica koja se dobija pretpostavljajući Ja biti tačka u nizu i ja je njegov sledeći Komšija kao njegova drug u putu.

$\left({{\frac {1}{4}}+{\frac {3}{8}}}\right){\sqrt {N}}$ Ima bolju donju granicu koju dobija pretpostavljajući I 'a ovo drugo je I , sledi, i ja' 'bivsi je ja je nakon sledećeg.

${\sqrt {\frac {N}{2}}}$ je još bolja od donje granice koja se dobija deljenjem putanji sekvence na dva dela, kao before_i' i' sa behind_i svaki deo sadrži N / 2 boda, a zatim brisanja before_i' deo formirati razblaženim pointset.

• David S. Džonson dobiti donju granicu od računara eksperimenta:

$0.7080{\sqrt {N}}+0.522$, odakle potiče od 0.522 tačaka u blizini trga granice koje imaju manje susede.

• Kristina L. Valenzuela i Antonia J. Jones dobio još jedan donje granice od računara eksperimenta:

$0.7078{\sqrt {N}}+0.551$

Gornja granica

Primenom metode na simulirani žarenja uzoraka N = 40000, kompjuterska analiza pokazuje gornje granice

$\left({\sqrt {\frac {N}{2}}}+0.72\right)\cdot 1.015$, odakle dolazi 0,72 od granične efekta.

Pošto stvarni rešenje je samo najkraći put, za potrebe programskog potrazi drugi gornju granicu je dužina jednog prethodno otkrio aproksimacije.

Trgovački putnik analitičara problema

Postoji problem u analogan geometrijskoj teoriji meri koja pita sledeće: pod kojim uslovima može podskup e Euklidov prostor se nalazi u otklonjiva krivini (to jest, kada je tu kriva sa konačne dužine koje posećuje svaki poen u E)? Ovaj problem je poznat kao trgovačkog putnika analitičara problem ili geometrijskog problema trgovačkog putnika.

Pogledaj još

Problem rutiranja vozila

Notes

• Der Handlungsreisende - vie er Sein und soll bio er zu Tun [sic] šešir, um Auftrage zu erhalten und eines glucklichen Erfolgs u Seinen magazinov GEVISS zu sein - von einem Alten komi-Voiageur" (trgovački putnik - kako on mora da bude i šta treba da uradi kako bi bili sigurni da obavlja svoje zadatke i da uspeh u svom poslu - od strane Visokog komesarijata-voiageur) ^ diskusija ranog rada Hamilton i Kirkman mogu se naći u Graph Theori 1736-1936 ^ Citirano i engleski prevod u Schrijver (2005).
• Originalni Nemački: "Vir bezeichnen als Botenproblem (Veil Diese Zahtevaj u von der Prakis jedem Postboten, ubrigens auch von vielen Reisenden zu losen ist) fur die Aufgabe, endlich viele Punkte, Deren paarveise Abstande bekannt sind die, Den kurzesten Punkte verbindenden Veg zu finden. Dieses Problem ist Naturlich stets durch Endlich Viele Versuche losbar. Pravila, velche Die Količestvo Versuche unter die Količestvo Permutationen der gegebenen Punkte herunterdrucken vurden, sind nicht bekannt.
• Die Regel, čovek Solle vom Ausgangspunkt predhodno zum nachstgelegenen Punkt, Dann zu dem diesem nachstgelegenen Punkt gehen etc, liefert im allgemeinen nicht den Veg kurzesten.. " ^ detaljan tretman povezanosti Menger i Vitni, kao i rast u proučavanju TSP se može naći u 2005 papiru Aleksandra Schrijver je "o istoriji kombinatorne optimizacije (do 1960). Priručnik o diskretnoj Optimization (K. Aardal, GL Nemhauser, Veismantel R., ur.), Elsevier, Amsterdam, 2005, str 1-68.PS, PDF ^ Behzad, Arash, Modarres, Muhamed (2002), " ; novi efikasni Transformacija generalizovane trgovačkog putnika problema u problem trgovačkog putnika ", Zbornik radova 15. Međunarodne konferencije sistemski inženjering (Las Vegas) ^ Papadimitriou, CH; Steiglitz, K. (1998). Kombinatorne optimizacije: Algoritmi i složenost. Mineola, NI: Dover. ^ Orponen

Literatura

• Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. (2006), The Traveling Salesman Problem, ISBN 0-691-12993-2 .
• Bellman, R. (1960), „Combinatorial Processes and Dynamic Programming”, Ур.: Bellman, R.; Hall, M., Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10, American Mathematical Society, стр. 217—249 .
• Bellman, R. (1962), „Dynamic Programming Treatment of the Travelling Salesman Problem”, J. Assoc. Comput. Mach., 9: 61—63, S2CID 15649582, doi:10.1145/321105.321111 .
• Christofides, N. (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh .
• Hassin, R.; Rubinstein, S. (2000), „Better approximations for max TSP”, Information Processing Letters, 75 (4): 181—186, doi:10.1016/S0020-0190(00)00097-1 .
• Held, M.; Karp, R. M. (1962), „A Dynamic Programming Approach to Sequencing Problems”, Journal of the Society for Industrial and Applied Mathematics, 10 (1): 196—210, doi:10.1137/0110015 .
• Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), „Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs”, In Proc. 44th IEEE Symp. on Foundations of Comput. Sci, стр. 56—65 .
• Karp, R.M. (1982), „Dynamic Programming Meets the Principle of Inclusion and Exclusion”, Oper. Res. Lett., 1 (2): 49—51, doi:10.1016/0167-6377(82)90044-X .
• Kohn, S.; Gottlieb, A.; Kohn, M. (1977), „A Generating Function Approach to the Traveling Salesman Problem”, ACM Annual Conference, ACM Press, стр. 294—300 .
• Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), „Long tours and short superstrings'”, Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci, IEEE Computer Society, стр. 166—177 .
• Orponen, P.; Mannila, H. (1987), „On approximation preserving reductions: Complete problems and robust measures'”, Technical Report C-1987–28, Department of Computer Science, University of Helsinki .
• Papadimitriou, C. H.; Yannakakis, M. (1993), „The traveling salesman problem with distances one and two”, Math. Oper. Res., 18: 1—11, doi:10.1287/moor.18.1.1 .
• Serdyukov, A. I. (1984), „An algorithm with an estimate for the traveling salesman problem of the maximum'”, Upravlyaemye Sistemy, 25: 80—86 .
• Woeginger, G.J. (2003), „Exact Algorithms for NP-Hard Problems: A Survey”, Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, стр. 185—207 .

Спољашње везе

• Traveling Salesman Problem Архивирано на сајту Wayback Machine (26. децембар 2008) at Georgia Institute of Technology
• TSPLIB at the University of Heidelberg
• Traveling Salesman Problem by Jon McLoone at the Wolfram Demonstrations Project
• Source code library for the travelling salesman problem Архивирано на сајту Wayback Machine (21. мај 2013)