Matkamyyjän ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.6.2022 tarkistetusta versiosta . tarkastukset vaativat 7 muokkausta .

Travelling salesman -ongelma (tai TSP englanninkielisestä travelling salesman -ongelmasta ) on yksi tunnetuimmista kombinatorisista optimointiongelmista , jossa etsitään kannattavin reitti , joka kulkee määritettyjen kaupunkien läpi vähintään kerran ja palaa sitten alkuperäiseen kaupunkiin. Ongelman olosuhteissa ilmoitetaan reitin kannattavuuskriteeri (lyhin, halvin, kumulatiivinen kriteeri jne.) ja vastaavat etäisyyksien, kustannusten ja vastaavien matriisit. Pääsääntöisesti reitin tulee kulkea jokaisen kaupungin läpi vain kerran - tässä tapauksessa valinta tehdään Hamiltonin syklien joukosta . Ongelman yleisessä muotoilussa on useita erikoistapauksia, erityisesti geometrinen matkustava myyjä -ongelma (kutsutaan myös tasomaiseksi tai euklidiseksi, kun etäisyysmatriisi heijastaa tason pisteiden välisiä etäisyyksiä), metrinen matkustava myyjä -ongelma (kun kolmion epätasa -arvo täyttyy kustannusmatriisissa ), symmetriset ja epäsymmetriset matkustava myyjäongelmat . Ongelmasta on myös yleistys, ns. yleistetty matkustava myyjä -ongelma .

Optimointiongelmalause kuuluu kuitenkin NP-kovien ongelmien luokkaan, kuten useimmat sen erityistapaukset. "Päätösongelman" versio (eli sellainen, joka kysyy, onko reittiä, joka ei ole pidempi kuin annettu arvo k ) kuuluu NP-täydellisten tehtävien luokkaan . Matkustavien myyntimiesten ongelma on yksi transcomputing-ongelmista : edes suhteellisen pienellä määrällä kaupunkeja (> 66), sitä ei voida ratkaista vaihtoehtojen luettelointimenetelmällä millään teoreettisesti ajateltavissa olevalla tietokoneella alle useiden miljardien vuoden aikana.

Historia

Matkamyyjien ongelmaan liittyy Hamiltonin syklin löytämisen ongelma . Esimerkki tällaisesta ongelmasta on ritariliikkeen ongelma , joka tunnettiin ainakin 1700-luvulta lähtien [1] . Leonhard Euler omisti hänelle suuren teoksen "Uteliaan kysymyksen ratkaisu, joka ei näytä olevan minkään tutkimuksen kohteena", päivätty 1759 [2] . Toinen esimerkki ongelmasta Hamiltonin syklin löytämisessä on ikosiaani : matemaattinen pulma, jossa sinun täytyy käydä läpi dodekaedrin (kaavio, jossa on 20 solmua), joka vierailee jokaisessa kärjessä täsmälleen kerran. Tämän ongelman ehdotti William Hamilton 1800-luvulla, hän myös määritteli luokan tällaisia polkuja.

Vuonna 1832 julkaistiin kirja, jonka otsikko oli "Matkava myyjä - kuinka hänen tulee käyttäytyä ja mitä hänen tulee tehdä voidakseen toimittaa tavarat ja menestyä asioissa - neuvoja vanhalta kuriirilta" ( saksa: 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 ), joka kuvaa ongelman, mutta ei käytä sen ratkaisemiseen matemaattista laitteistoa. Mutta se tarjoaa esimerkkejä reiteistä joillekin Saksan ja Sveitsin alueille.

Ensimmäiset maininnat matemaattisena optimointiongelmana kuuluvat Carl Mengerille , joka muotoili sen matemaattisessa kollokviossa vuonna 1930 seuraavasti:

Kutsumme sanansaattaja-ongelmaksi (koska tämä kysymys herää jokaiselle postimiehelle, erityisesti monet matkailijat ratkaisevat sen) ongelmaksi löytää lyhin reitti rajallisen joukon paikkoja välillä, joiden välinen etäisyys on tiedossa.

Pian ilmestyi tunnettu nimi matkustavamyyjäongelmasta , jota ehdotti Hassler Whitney Princetonin yliopistosta .

Määrittelyn helppouden ja hyvien ratkaisujen löytämisen suhteellisen helppouden ohella matkustava myyjä -ongelma eroaa siinä, että todella optimaalisen polun löytäminen on melko vaikea tehtävä. Nämä ominaisuudet huomioiden, 1900-luvun toiselta puoliskolta lähtien, matkustavan myyjän ongelman tutkimuksella ei ole niinkään käytännön merkitystä kuin teoreettista kuin mallia uusien optimointialgoritmien kehittämiseen.

Monet nykypäivän yleisistä erillisistä optimointimenetelmistä , kuten cutoff , haara ja sidottu sekä erilaisia heurististen algoritmien muunnelmia, on kehitetty käyttämällä esimerkkinä matkustavan myyjän ongelmaa.

1950- ja 1960 - luvuilla matkustava myyjä -ongelma herätti tutkijoiden huomion Yhdysvalloissa ja Euroopassa. Tärkeä panos ongelman tutkimukseen kuuluu George Danzigille , Delbert Ray Fulkersonille ( eng. Delbert Ray Fulkerson ) ja Selmer Johnsonille ( eng. Selmer M. Johnson ), jotka vuonna 1954 RAND Corporation -instituutissa muotoilivat ongelman muodossa diskreetistä optimointitehtävästä ja sovellettu siihen ratkaisemaan katkaisumenetelmä . Tätä menetelmää käyttämällä he rakensivat matkustavan myyjän polun yhdelle tietylle ongelmanlausunnalle 49 kaupungissa ja perustivat sen optimaalisen. 1960- ja 1970-luvuilla monet tiedemiehet tutkivat ongelmaa sekä teoreettisesti että sen sovellusten osalta tietojenkäsittelytieteessä, taloustieteessä, kemiassa ja biologiassa.

Richard Karp vuonna 1972 osoitti Hamiltonin polkujen löytämisen ongelman NP-täydellisyyden , mikä polynomisen pelkistettävyyden ansiosta merkitsi matkustavan myyjän ongelman NP-kovuuden. Näiden ominaisuuksien perusteella hän antoi teoreettisen perustelun ongelman ratkaisujen löytämisen monimutkaisuuteen käytännössä.

Suuria menestyksiä saavutettiin 1970-luvun lopulla ja 1980-luvulla, jolloin Martin Grötschel ( saksa Martin Grötschel ), Manfred Padberg ( saksalainen Manfred Padberg ) ja Giovanni Rinaldi ( italialainen Giovanni Rinaldi ) ym. laskivat ratkaisun uusilla jakomenetelmillä taso, haarat ja rajat. 2393 kaupungin ongelmatapauksessa.

1990 -luvulla David Applegate , Robert Bixby , Vašek Chvátal ja William Cook tekivät Concorde-ohjelman ennätyksiä . Gerhard Reinelt ( saksalainen Gerhard Reinelt ) loi TSPLIB:n – joukon standardoituja tapauksia matkustavan myyjän ongelmasta, joiden monimutkaisuus on vaihtelevaa vertaillakseen eri tutkijaryhmien työn tuloksia. Maaliskuussa 2005 Concord -ohjelma ratkaisi 33 810 solmun ongelman: laskettiin polku, jonka pituus oli 66 048 945 ja lyhyempien polkujen puuttuminen todettiin. Huhtikuussa 2006 löydettiin ratkaisu 85 900 solmun esiintymälle. Hajotusmenetelmiä käyttämällä voidaan laskea ratkaisuja tapauksiin, joissa on miljoonia solmuja, joiden pituus on alle 1 % optimaalista pitempi.

Muodollinen määritelmä

Graafinen esitys

Jotta matemaattista laitteistoa voitaisiin käyttää ongelman ratkaisemiseen, se tulee esittää matemaattisen mallin muodossa . Liikkuvan myyjän ongelma voidaan esittää mallina graafissa eli käyttämällä niiden välisiä pisteitä ja reunoja. Siten graafin kärjet vastaavat kaupunkeja ja kärkien väliset reunat ja vastaavat näiden kaupunkien välisiä viestintäpolkuja. Jokaiseen reunaan voidaan liittää reitin kannattavuuskriteeri , joka voidaan ymmärtää esimerkiksi kaupunkien väliseksi etäisyydeksi, matkan kestoksi tai kustannuksiksi. $\vasen(i,j\oikea)$ $i$ $j$ $\vasen(i,j\oikea)$ $c_{ij}\geqslant 0$

Hamiltonin sykli on polku, joka sisältää tarkalleen kerran jokaisen graafin kärjen.

Tehtävän yksinkertaistamiseksi ja reitin olemassaolon takaamiseksi yleensä oletetaan, että ongelman malligraafi on täysin yhdistetty eli että mielivaltaisen kärkiparin välillä on reuna. Tapauksissa, joissa yksittäisten kaupunkien välillä ei ole yhteyttä, tämä voidaan saavuttaa ottamalla käyttöön enimmäispituisia reunoja. Suuren pituuden vuoksi tällainen reuna ei koskaan putoa optimaaliselle reitille, jos sellainen on olemassa.

Siten ratkaisu matkustavan myyjän ongelmaan on löytää Hamiltonin minimipainon sykli täydellisestä painotetusta graafista.

Riippuen siitä, mitä reitin kannattavuuskriteeriä verrataan reunojen kokoon, ongelmasta on erilaisia versioita, joista tärkeimmät ovat symmetriset ja metriset ongelmat.

Epäsymmetriset ja symmetriset ongelmat

Yleisesti ottaen epäsymmetrinen matkustava myyjä -ongelma eroaa siinä, että se mallinnetaan suunnatulla graafilla. Siksi on myös harkittava, mihin suuntaan reunat ovat.

Symmetrisen ongelman tapauksessa kaikki samojen kärkien väliset reunaparit ovat samanpituisia, eli reunan pituudet ovat samat . Symmetrisessä tapauksessa mahdollisten reittien määrä on puolet epäsymmetrisestä tapauksesta. Symmetrinen ongelma mallinnetaan suuntaamattomalla graafilla (katso kuva). $\vasen(i,j\oikea)$ $c_{ij}=c_{ji}$

Itse asiassa matkustavan myyjän ongelma oikeissa kaupungeissa voi olla sekä symmetrinen että epäsymmetrinen riippuen reittien kestosta tai pituudesta ja liikesuunnasta.

Metrinen ongelma

Symmetristä matkustavan myyjän ongelmaa kutsutaan metriseksi , jos kolmion epäyhtälö täyttyy reunojen pituuksien suhteen . Suhteellisesti sanottuna tällaisissa ongelmissa kiertotiet ovat pidempiä kuin suorat viivat, eli reuna kärjestä kärkeen ei ole koskaan pidempi kuin polku välipisteen läpi : $i$ $j$ $k$

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

Tämä reunan pituusominaisuus määrittää mitattavan tilan reunajoukolle ja etäisyysmitan, joka tyydyttää intuitiivisen etäisyyden ymmärtämisen.

Käytännössä yleiset etäisyysfunktiot ovat myös mittareita ja täyttävät kolmio-epäyhtälön:

Euklidinen etäisyys euklidelaisen matkamyyjän ongelmassa,
Manhattanin metriikka (myös neljännesvuosittainen metriikka) suorakaiteen muotoisesta matkustavamyyjätehtävästä, jossa hilan kärkien välinen etäisyys on yhtä suuri kuin y-akselin ja abskissan etäisyyksien summa,
Maksimimetriikka , joka määrittää hilagraafin kärkien välisen etäisyyden ordinaatin ja abskissan etäisyyden maksimiarvoksi.

Kahta viimeistä mittaria käytetään esimerkiksi piirilevyjen reikien porauksessa, jolloin koneen on tehtävä enemmän reikiä mahdollisimman lyhyessä ajassa ja se voi liikuttaa poraa molempiin suuntiin siirtyäkseen reiästä toiseen. Manhattan-metriikka vastaa tapausta, jossa liike molempiin suuntiin tapahtuu peräkkäin, ja maksimi vastaa tapausta, jossa liike molempiin suuntiin tapahtuu synkronisesti, ja kokonaisaika on yhtä suuri kuin suurin liikkeen aika ordinaatta- tai abskissa-akselia pitkin.

Ei-metrinen matkustava myyjä -ongelma voi syntyä esimerkiksi siinä tapauksessa, että oleskelun kesto minimoidaan eri suuntiin valittavien ajoneuvojen läsnä ollessa. Tällöin kiertotie ilmateitse voi olla lyhyempi kuin suora yhteys autolla.

Jos käytännössä ongelman olosuhteissa sallitaan vierailla kaupungeissa useita kertoja, niin symmetrinen ongelma voidaan vähentää metriseksi. Tätä varten ongelmaa tarkastellaan ns. etäisyyskaaviossa. Tällä graafilla on samat pisteet kuin alkuperäisellä ja se on täysin yhdistetty. Piikkien välisten ja etäisyysgraafin reunojen pituus vastaa lyhimmän etäisyyden pituutta pisteiden välillä ja alkuperäisessä graafissa. Tällä tavalla määritellyillä pituuksilla kolmio-epäyhtälö pätee, ja jokainen etäisyyskaavion reitti vastaa aina reittiä, jossa on mahdollisia pisteiden toistoja alkuperäisessä kaaviossa. $c_{ij}$ $i$ $j$ $i$ $j$ $c_{ij}$

Formulointi erillisenä optimointitehtävänä

Yksi tapa ratkaista ongelma on muotoilla se diskreetiksi optimointitehtäväksi, jossa ratkaisut esitetään muuttujina ja yhteydet niiden välisinä epätasa-arvosuhteina. Näin ollen useita vaihtoehtoja on mahdollista. Esimerkiksi symmetrinen ongelma voidaan esittää joukkona reunoja . Jokaiselle reunalle on määritetty binäärimuuttuja , joka on 1, jos reuna kuuluu reittiin, ja 0 muussa tapauksessa. Satunnainen reitti voidaan esittää jäsenmuuttujien joukon arvoina, mutta jokainen tällainen joukko ei määrittele reittiä. Edellytys, että muuttujajoukon arvot määräävät reitin, ovat alla kuvatut lineaariset epäyhtälöt. $V$ $\{i,j\}$ $x_{ij}\in \{0,1\}$

Jokaisen kärjen on kommunikoitava reunaparin kautta muiden kärkien kanssa, eli tulo- ja lähtöreunojen kautta:

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

Yhteensä kukin termi on joko 1 (kuuluu reitille) tai 0 (ei kuulu). Toisin sanoen tuloksena saatu summa on yhtä suuri kuin niiden reitin reunojen lukumäärä, joiden toisessa päässä on kärki. Se on yhtä suuri kuin 2, koska jokaisella kärjellä on tulo- ja lähtöreuna. Viereisessä kuvassa kärki on esitetty tulo- ja lähtöreunoilla ja reitin reunat paksuina viivoina. Kylkiluiden vieressä ovat pituudet , jotka on sovellettu yllä olevaan määrään. $x_{ij}$ $i$ $i$ $x_{ij}$

Aiemmin kuvatut moninkertaisuusehdot täyttyvät paitsi reitit, myös yksittäisiä syklejä vastaavien muuttujien arvot, joissa kukin huippu kuuluu vain yhteen sykliin (katso kuva). Tällaisten tapausten välttämiseksi on täytettävä niin sanotut silmukkaepäyhtälöt (tai alireitityksen eliminointiehdot), jotka Danzig, Fulkerson ja Johnson määrittelivät vuonna 1954 nimellä silmukkaehdot . Nämä epäyhtälöt määrittelivät lisäehdon, että jokainen kärkijoukko on joko tyhjä tai sisältää kaikki pisteet yhdistettynä muihin pisteisiin vähintään kahden reunan kautta: $S\alajoukko V$

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

kaikille kärkijoukoille , missä . Tämä summa on yhtä suuri kuin kärjen ja kärjen välisten polun reunojen pituuksien summa . Tarpeettomien epätasa-arvojen poistamiseksi voimme rajoittua ryhmiin, joissa on vähintään kaksi ja enintään pisteitä. Viereisessä kuvassa reunat , joiden pituus on merkitty paksuilla viivoilla, muilla reunoilla on pituus . Lisäehtojen (2) käyttöönotto kolmesta vasemmasta kärjestä koostuvalle kärkijoukolle varmistaa, että se yhdistetään vähintään kahden polun reunan kautta, joissa on kolme kärkeä oikealla molempien syklien eliminoimiseksi. Danzigin, Fulkersonin ja Johnsonin mukaan sykliä eliminoivien epätasa-arvojen lukumäärä on . $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)$

Vuonna 1960 Miller, Tucker ja Zemlin kehittivät vaihtoehtoisia ehtoja alireittien poistamiseksi ottamalla käyttöön uusia muuttujia, jotka määrittävät vierailtujen kaupunkien järjestyksen ja vaativat vain lisäepätasa- arvoa. Lisäksi Millerin, Tuckerin ja Zemlinin muotoilujen kaksinaisuuden vuoksi matkustava myyjä -ongelma on edelleen NP-kova. $n$ $n^{2}-n+1$ $x_{ij}$

Siten jokainen vektori, jonka elementit ovat yhtä suuria kuin 0 ja 1 ja joka täyttää kaikki epäyhtälöt, määrittelee oikean reitin, joka on ratkaisu uudelleen muotoiltuun matkustavamyyjän ongelmaan: laske

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

Koska muuttujilla on vain arvot 0 ja 1, summa on yhtä suuri kuin reittiin kuuluvien reunojen kokonaispituus. $x_{ij}$ $c_{ij}$ $\{i,j\}$

Tyypin (2) epäyhtälöiden määrä kasvaa eksponentiaalisesti kaupunkien määrän kasvaessa, koska melkein jokainen solmujen osajoukko määrittelee yhden epäyhtälön. Tämä ongelma voidaan ratkaista käyttämällä leikkaustasomenetelmää , jonka vuoksi epäyhtälöitä lisätään vain silloin, kun niitä todella tarvitaan. Geometrialta katsottuna lineaariset epäyhtälöt voidaan esittää hypertasoina muuttujien avaruudessa. Nämä epäyhtälöt tyydyttävät vektorit muodostavat polytoopin (moniulotteisen polyhedronin) tai moniulotteisen polygonin sellaisessa avaruudessa, jonka tarkka muoto määräytyy pituuksien mukaan ja on enimmäkseen tuntematon. Voidaan kuitenkin osoittaa, että ehdot (1) ja (2) määrittävät polytoopin pinnat (fasetti), eli polytoopin suurimman ulottuvuuden sivupinnat. Siksi ne ovat yksi vahvimmista lineaarisista epäyhtälöistä, jotka voivat kuvata reittiä. Vain harvoissa tapauksissa tunnetuilla epätasa-arvoilla on myös monia eri puolia. Vaikka (1) ja (2) yhdessä rajoitusten kanssa mallintavat ongelman täysin vain binäärivektoreille, näitä epäyhtälöitä voidaan käyttää haara- ja sidottumenetelmässä ratkaisujen hylkäämiseen lineaarisilla optimointimenetelmillä ei-kokonaislukukoordinaateilla (katso tarkat menetelmät -osio alla). $2^{|V|}$ $c_{ij}$

Algoritminen monimutkaisuus

Koska jokaisessa kaupungissa liikkuva myyjä joutuu valitsemaan seuraavan kaupungin niistä, joissa hän ei ole vielä käynyt, on olemassa reitit epäsymmetriselle ja symmetriselle matkustavamyyjä-ongelmalle. Hakutilan koko riippuu siis tekijällisesti kaupunkien lukumäärästä. $(n-1)!$ $(n-1)!/2$

Useat versiot matkustavan myyjän ongelmasta (metrinen, symmetrinen ja epäsymmetrinen) ovat NP-ekvivalentteja. Monimutkaisuusluokkien P ja NP epätasa-arvoa koskevan yleisen mutta todistamattoman arvelun mukaan ei ole olemassa determinististä Turingin konetta , joka kykenisi ratkaisemaan ongelman ilmentymiä polynomiajassa kaupunkien lukumäärästä riippuen.

Tiedetään myös, että ehdolla ei ole algoritmia, joka jollekin polynomille laskeisi sellaisia ratkaisuja liikkuvan myyjän tehtävään, jotka poikkeaisivat optimaalisesta maksimista kertoimella . $P\neq NP$ $s$ $2^{p(n)}$

Käytännössä ehdottoman optimaalisen reitin etsiminen ei aina ole välttämätöntä. On olemassa algoritmeja, joilla voidaan löytää likimääräisiä ratkaisuja metriikkaongelmaan polynomiajassa ja löytää reitti, joka on enintään kaksi kertaa optimaalista pidempi. Toistaiseksi ei tunneta polynomiaikaalgoritmia, joka takaa paremman tarkkuuden kuin 1,5 optimaalisesta. Oletuksena on, että on olemassa (tuntematon) vakio , jonka tarkkuutta mikään polynomi-aika-algoritmi ei voi taata . Kuten Arora on osoittanut, euklidiselle matkustavamyyjä-ongelmalle on olemassa polynomiaikainen PTAS-kaavio likimääräisen ratkaisun löytämiseksi. $P\neq NP$ $c>0$ $1+c$

Lisäksi tiedoissa voi olla ominaisuuksia, jotka voivat auttaa ratkaisemaan ongelman. Esimerkiksi kaupungit eivät sijaitse sattumalta, vaan maaston mukaan tai jopa pitkään löydetyn optimaalisen kauppareitin varrella. Lisätietojen ja heuristiikan avulla voimme löytää hyväksyttävät ratkaisut kohtuullisessa ajassa.

Ongelman suljetut ja avoimet versiot

Liikkuvan myyjän tehtävän suljetussa versiossa vaaditaan vierailemaan graafin kaikissa pisteissä ja palaamaan sitten alkuperäiseen huippupisteeseen. Avoin variantti eroaa suljetusta siitä, että se ei vaadi paluuta lähtöpisteeseen.

Tehtävän avoin versio pelkistetään suljetuksi korvaamalla aloituspisteeseen sisältyvien kaarien painot luvulla 0. Optimaalinen suljettu matkamyyjän reitti tällaisessa kaaviossa vastaa optimaalista avointa reittiä alkuperäisessä kaaviossa.

Suljetun muunnelman pelkistämiseksi ei-suljetuksi on määritettävä luku , joka ylittää tiukasti minkä tahansa liikkuvan myyjäreitin painon tietyssä kaaviossa (voit esimerkiksi ottaa kustakin kärjestä lähtevien enimmäispainokaarien summan , lisätty 1). Sitten sinun on lisättävä graafiin uusi kärki (oletetaan, että alkuperäisen graafin kärjet on numeroitu välillä 0 - , kun taas aloituspisteen numero on 0). Huippupisteestä lähtevien ja siihen tulojen kaarien kustannukset määritellään seuraavasti: $K$ $K$ $v_{n}$ $n-1$ $v_{n}$

$c_{n,i}=3 kt$
$c_{0,n}=3 kt$
$c_{i,n}=c_{i,0}+2 kt$ klo alkaen _ $i$ $yksi$ $n-1$

Optimaalinen ei-suljettu matkustava myyjäreitti tällaisessa kaaviossa vastaa alkuperäisen kaavion optimaalista suljettua matkustavamyyjän reittiä ja sillä on korkeammat kustannukset. $2K$

Ratkaisumenetelmät

Alkueläimet

kattava haku
satunnainen luettelointi
ahneita algoritmeja
- lähin naapuri menetelmä
- lähin kaupunkikuvausmenetelmä
- halvin menetelmä
minimivirittävän puun menetelmä
simuloitu hehkutusmenetelmä

Kaikki tehokkaat (täydellistä luettelointia vähentävät) menetelmät matkustavan myyjän ongelman ratkaisemiseksi ovat heuristisia menetelmiä . Useimmat heuristiset menetelmät eivät löydä tehokkainta reittiä, vaan likimääräistä ratkaisua . Niin kutsutuilla tahansa aika-algoritmeilla on usein kysyntää .[ selventää ] eli asteittain parantamalla jotakin nykyistä likimääräistä ratkaisua.

Yksi esimerkki yksinkertaisimmasta menetelmästä ongelman metrisen version ratkaisemiseksi on minimivirittävän puiden käyttö, joka antaa ratkaisun approksimaatiokertoimella ja on aikamonimutkainen . Ajatuksena on, että jokainen yhdistetty graafi sisältää alhaisemman kustannuskynnyksen aligraafilleen, vähimmäisvirittävän puun, ja että mikä tahansa sykli, joka vierailee kussakin graafin kärjessä vähintään kerran, voidaan muuntaa kustannusoptimaaliseksi reitiksi käyttämällä metriikkaa: $2$ $O(n^{2}\log n)$

Etsi kaavion pienin virittävä puu . $T$ $G$
Luo kaavio kaksinkertaistamalla kaikki reunat . Joten kaikilla pisteillä on parillinen määrä reunoja. $T'$ $T$ $T'$
Etsi Eulerin sykli . $T'$ $C'$
Pienennä , ohita kaksinkertaiset reunat, saat syklin . $C'$ $C$
Tuo esiin . $C$

Approksimaatiokertoimen arvo todistetaan seuraavasti: Olkoon - pienin virittävä puu, - sama puu, mutta kaksinkertaisilla reunoilla, - Eulerin sykli graafissa , - algoritmin tulos, - minimireitti. Huomaa , että sekä . Sitten approksimaatiokerroin on . $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$

Yllä oleva menetelmä voidaan kuitenkin optimoida lisäämällä reunojen määrää pisteissä, joissa on pariton määrä naapureita, 1:llä, mikä vastaa yhteensopivia "parittomat" kärjet. On tärkeää huomata, että "parittomien" pisteiden määrä on aina parillinen, perustuen kättelylemmaan . Siinä tapauksessa optimoidulla algoritmilla on approksimaatiokerroin ja aikamonimutkaisuus . Osoitetaan ennen todistetta, että , missä on täsmäys ja on optimaalinen reitti: Antaa olla vähimmäisvirittävän puun "parittomien" kärkien joukko ja olla sykli, joka saadaan ohittamalla pisteitä . Ilmeisesti sillä on tasainen pituus sekä kaksi ei-leikkautuvaa maksimivastaavuutta ja , joille ja . Tästä seuraa, että ja näin ollen . Tämän perusteella löydämme algoritmin approksimaatiokertoimen: . $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$

On myös asetuksia, joissa matkustavan myyjän ongelmasta tulee NP-täydellinen . Yleensä tällaiset lausunnot näyttävät tältä: onko annetussa graafissa G sellaista kiertomatkaa, jonka hinta ei ylitä x . Usein siinä testataan uusia lähestymistapoja tyhjentävän haun heuristiseen vähentämiseen .

Käytännössä käytetään erilaisia muunnelmia tehokkaammista menetelmistä: haara- ja sidottumenetelmä sekä geneettisten algoritmien menetelmä sekä muurahaisyhdyskuntaalgoritmi .

Branch and Bound Method

Matkamyyjän ongelmaan on mahdollista löytää tarkka ratkaisu eli laskea "manuaalisesti" kaikkien mahdollisten reittien pituudet ja valita pienin reitti. Jopa pienelle määrälle kaupunkeja on kuitenkin käytännössä mahdotonta ratkaista ongelma tällä tavalla. Yksinkertaiselle variantille, kaupunkien symmetriselle ongelmalle, on mahdollisia reittejä, eli 15 kaupungissa on 43 miljardia reittiä ja 18 kaupungissa on jo 177 biljoonaa. Kuinka nopeasti laskennan kesto kasvaa, voidaan osoittaa seuraavalla esimerkillä. Jos olisi laite, joka voisi löytää ratkaisun 30 kaupunkiin tunnissa, kaksi muuta kaupunkia kestäisi tuhat kertaa kauemmin; eli yli 40 päivää. $n$ $(n-1)!/2$

Diskreetit optimointimenetelmät, erityisesti haara- ja sidotut menetelmät, mahdollistavat optimaalisen tai likimääräisen ratkaisun löytämisen riittävän suuriin ongelmiin.

Geometrisessä tulkinnassa nämä menetelmät käsittelevät ongelmaa kuperana polytooppina, eli moniulotteisena monikulmiona -ulotteisessa yksikkökuutiossa , jossa on yhtä suuri kuin graafin reunojen lukumäärä. Tämän yksikkökuution kukin kärki vastaa reittiä, eli vektoria, jonka elementit ovat 0/1 ja joka täyttää edellä kuvatut lineaariset epäyhtälöt. Näiden epäyhtälöiden kuvaamat hypertasot leikkaavat yksikkökuution reunat, jotka eivät vastaa mitään reittiä. $m$ $[0,1]^{m}$ $m$

Viereisessä kuvassa on esitetty menetelmän soveltaminen kolmen solmun ongelmaan. Mukaisesti kolmen mahdollisen reunan välillä vertices, binäärimuuttujat ja verrataan . Tässä tapauksessa on vain yksi mahdollinen reitti, nimittäin se, joka kulkee kolmen kärjen kautta. Tämä reitti täyttää epäyhtälön , jonka mukaan reitin tulee kulkea vähintään kahden kärjen kautta. Tämän vektoria (1,1,1) vastaavan polun lisäksi kaikki tämän epäyhtälön punaisella merkityssä osassa olevat pisteet täyttävät myös epäyhtälön. Punaisten viivojen läpi kulkevat tasot leikkaavat kaikki kulmat, jotka vastaavat ei-olemattomia polkuja, joissa on enintään yksi reuna, nimittäin nollavektori (0, 0, 0), yksikkövektorit (1, 0, 0), (0, 1, 0) ja (0, 0, 1). Vahva epäyhtälö katkaisee yksikkökuutiosta kaiken paitsi ainoan kelvollisen pisteen (1, 1, 1). Tässä nimenomaisessa tapauksessa sama vaikutus voidaan saada kolmella tyypin (1) epäyhtälöllä. $x_{1},\,x_{2}$ $x_{3}$ $x_{1}+x_{2}+x_{3}\geqslant 2$ $x_{1}+x_{2}+x_{3}\geqslant 3$

Pienimmän pituisen sallitun reunan määrittämiseksi tulee ratkaista lineaariset optimointitehtävät, jotka leikkaavat yksikkökuutiosta tarpeettomia osia leikkaamalla tasoja ja yrittää jakaa yksikkökuutio pienempiin polytooppeihin haara- ja sidomenetelmällä.

Tämä menetelmä ei kuitenkaan yleensä riitä reittien nopeaan löytämiseen. Tarkkojen menetelmien tärkein etu on, että ne laskevat lyhimmän reitin riittävän ajan myötä. Kun optimaalisille ratkaisuille on alaraja, voidaan arvioida kuinka paljon löydetty reitti poikkeaa optimaalisesta. Esimerkiksi, kun alaraja on 100 ja kun on löydetty reitti, jonka pituus on 102, optimaalinen reitti voi olla välillä 100 ja 102. Niin kutsuttu optimiväli eli suurin suhteellinen etäisyys optimaalisen reitin pituuden ja reitin välillä lyhin tunnettu reitti on (102 - 100) /100 = 2%, eli löydetyn reitin 102 pituus poikkeaa enintään 2% optimaalisesta. Kun lasketun reitin pituus on yhtä pitkä kuin edellisen, katsotaan, että löydetty ratkaisu on optimaalinen. Hyväksyttävän pituisten reittien löytämiseksi tarkat menetelmät voidaan yhdistää heuristisiin menetelmiin.

Haaroittunutta ja sidottua menetelmää matkustavan myyjän ongelman ratkaisemiseksi ehdotti vuonna 1963 joukko kirjailijoita (J. Little, K. Murty, D. Sweeney, K. Carol) [3] .

Elastinen verkkomenetelmä

Historia

Vuonna 1987 sitä käyttivät Durbin ja Willshaw, jotka toivat esiin analogian järjestetyn hermoyhteyksien muodostamismekanismien kanssa [4] .

Jokaista matkustavan myyjän reittiä pidettiin ympyrän kartoittamisena tasoon (jokin piste tästä ympyrästä on kartoitettu jokaiseen lentokoneen kaupunkiin). Ympyrän viereiset pisteet tulee kartoittaa mahdollisuuksien mukaan lähimpiin ja tasossa oleviin pisteisiin.

Algoritmi

Se alkaa pienen ympyrän asentamisesta koneeseen. Se laajenee epätasaisesti ja muodostuu renkaaksi, joka kulkee lähes kaikkien kaupunkien ohi ja muodostaa siten halutun reitin. Kuhunkin renkaan liikkuvaan pisteeseen vaikuttaa kaksi komponenttia: pisteen siirtäminen kohti lähintä kaupunkia ja siirtyminen renkaan pisteen naapureita kohti sen pituuden lyhentämiseksi. Kaupunki yhdistyy lopulta renkaan tiettyyn osaan sen laajentuessa. Kun tällainen elastinen verkosto laajenee, jokainen kaupunki liittyy tiettyyn renkaan osaan.

Alussa kaikilla kaupungeilla on suunnilleen sama vaikutus kuhunkin reittipisteeseen. Myöhemmin suuremmilla etäisyyksillä on vähemmän vaikutusta, ja jokainen kaupunki muuttuu tarkemmin sitä lähimpänä olevien renkaan pisteiden suhteen. Tätä Kohosen verkkooppimismenetelmää muistuttavaa spesifisyyden asteittaista kasvua ohjaa jonkin tehollisen säteen arvo.

Durbin ja Willshaw osoittivat, että Hopfieldin ja Tankin harkitsemassa 30 kaupungin ongelmassa elastinen verkkomenetelmä tuottaa lyhimmän reitin noin 1000 iteraatiossa. 100 kaupungin kohdalla tällä menetelmällä löydetty reitti oli vain 1 % korkeampi kuin optimaalinen.

Ant-algoritmi

Geneettinen algoritmi

Dynaaminen ohjelmointialgoritmi

Pääajatuksena on laskea ja tallentaa polku alkuperäisestä kaupungista kuhunkin muuhun kaupunkiin, sitten summaa tämä arvo polulla kustakin muusta kaupungista jäljellä oleviin kaupunkeihin jne. Tämän menetelmän etu raa'aan voimamenetelmä on merkittävä vähennys kokonaisvolyymilaskelmissa , koska muistin määrä on kasvanut huomattavasti [5] . $D$ $F$ ${\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2},P_{F}=n!\noin 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}$

Katso myös

Muistiinpanot

↑ Gross JL, Yellen J. Graafiteoria ja sen sovellukset, 2006 , s. 275.
↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analysis Arkistoitu 19. elokuuta 2021, Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, s. 310-337.
↑ Kostevich L. S. Matemaattinen ohjelmointi: Inform. optimaalisten ratkaisujen tekniikka: Proc. korvaus / L. S. Kostevich. - Minsk: Uusi tieto, 2003. ill., s. 150, ISBN 985-6516-83-8
↑ Richard Durbin, David Willshaw. Analoginen lähestymistapa matkustavan myyjän ongelmaan elastisen verkon menetelmällä // Luonto . – 22.4.1987. — Voi. 326 , iss. 6114 . — s. 689–691 . - doi : 10.1038/326689a0 . Arkistoitu alkuperäisestä 23. huhtikuuta 2016.
↑ Korbut A. A., Finkelstein Yu. Yu. Diskreetti ohjelmointi. - M., Nauka, 1969. - C. 258-264

Kirjallisuus

Levitin A. V. Luku 3. Brute Force Method: The Travelling Salesman Problem // Algoritmit. Johdatus kehitykseen ja analyysiin - M . : Williams , 2006. - S. 159-160. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
IN JA. Viisas. Matkamyyjän ongelma . - M . : "Tieto" , 1969. - S. 62.
Ezhov A., Shumsky S. Neurocomputing ja sen sovellukset taloustieteessä ja liiketoiminnassa . - M .: MEPhI , 1998. - S. 216.
Gross JL, Yellen J. Graafiteoria ja sen sovellukset. toinen painos. Boca Raton – Lontoo – New York: Chapman & Hall/CRC, 2006.

NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma	Pakkaus säiliöihin kaksiulotteinen pakkaus lineaarinen pakkaus pakkaus painon mukaan pakkaus arvon mukaan Reppu ongelma
graafiteorian joukkoteoria	Vertex-kannen ongelma Napsauta ongelma Itsenäisen joukon (joukon) ongelma Aseta peittoongelma Steinerin ongelma Matkamyyjän ongelma Yleinen matkamyyjän ongelma
Algoritmiset ongelmat	Boolen kaavojen tyydyttävyysongelma (konjunktiivisessa normaalimuodossa)
Logiikkapelejä ja pulmia	Yleiset tunnisteet (peli N 2 -1:ssä) lyhin ratkaisu ongelma Ongelmat, joiden ratkaisuja käytetään Tetrisissä Yleistynyt Sudoku-ongelma Latinalaisen neliön täyttöongelma Kakuron tehtävä
Vaikeusluokat Toimintatutkimus Optimointi Kombinatorinen optimointi Sovellettu matematiikka Algoritmien teoria Dynaaminen ohjelmointi 21 NP-täydellinen Karp-ongelma