Hamiltonin polun ongelma

Hamiltonin polkuongelma ja Hamiltonin sykliongelma  ovat ongelmia sen määrittämiseksi, onko tietyssä graafissa Hamiltonin polku vai Hamiltonin sykli ( suunnattu vai suuntaamaton ). Molemmat ongelmat ovat NP-täydellisiä [1] .

Hamiltonin polun ja Hamiltonin syklin ongelmien suhde

Hamiltonin polun ja Hamiltonin syklin löytämisen ongelmien välillä on yksinkertainen suhde. Yhdessä suunnassa graafin Hamiltonin polun ongelma vastaa Hamiltonin syklin ongelmaa graafissa H, joka saadaan graafista G lisäämällä uusi kärki ja yhdistämällä se kaikkiin graafin G kärkiin. Hamiltonin polku ei voi olla merkittävästi hitaampi (pahimmassa tapauksessa , kärkien lukumäärän funktiona) kuin Hamiltonin syklin etsiminen.

Päinvastaisessa suunnassa Hamiltonin syklin ongelma graafille G vastaa Hamiltonin polun ongelmaa graafissa H, joka saadaan kopioimalla graafin G yksi kärki v (osaksi v'), eli kärki v. ' on samassa naapurustossa kuin v, ja lisäämällä kaksi yhden asteen apupistettä, joista toinen on kytketty v:ään ja toinen v:ään [2] .

Hamiltonin sykliongelma on myös erikoistapaus matkustavamyyjäongelmasta , joka saadaan asettamalla kaikki kahden pisteen väliset etäisyydet yhdeksi, jos ne ovat vierekkäin, ja kahdeksi muussa tapauksessa. Kun matkamyyjätehtävä on ratkaistu, tarkista, että kokonaisetäisyys on yhtä suuri kuin n (jos on, reitti on Hamiltonin sykli, jos Hamiltonin kiertoa ei ole, lyhin polku on tätä arvoa pidempi).

Algoritmit

Niitä on n ! erilaisia ​​kärkijonoja, jotka voisivat olla Hamiltonin polkuja annetussa graafissa, jossa on n kärkeä (ja niitä on niin paljon täydessä graafissa ), joten raakavoima- algoritmi , joka kokeilee kaikkia mahdollisia sekvenssejä, olisi hyvin hidas.

Varhainen tarkka algoritmi Hamiltonin syklin löytämiseksi suunnatusta graafista oli numeraatioalgoritmi (Martellon algoritmi) [3] .

Frank Rubinin [4] hakumenettely jakaa graafin reunat kolmeen luokkaan - niihin, joiden täytyy olla polulla, niihin, jotka eivät voi kuulua polulle, ja reunat, joista ei ole tehty päätöstä. Haun aikana joukko päätössääntöjä luokittelee reunat, joista ei ole tehty päätöstä, ja määrittää, lopetetaanko vai jatketaanko haku. Algoritmi jakaa graafin osiin, jotka voidaan käsitellä erikseen.

Ongelman ratkaisemiseksi ajoissa voidaan käyttää Bellmanin, Heldin ja Karpin dynaamista ohjelmointialgoritmia . Tämä menetelmä määrittää kullekin S :n kärkijoukolle ja kullekin S :n kärjelle v , onko olemassa polku, joka kulkee S :n kaikkien kärkien läpi ja päättyy kohtaan v . Jokaiselle parille ( S , v ) on olemassa polku silloin ja vain, jos v :llä on naapuripiste w siten, että on olemassa polku kohteelle , joka voidaan saada jo hankitusta dynaamisesta ohjelmointitiedosta [5] [6] .

Andreas Björklund antaa vaihtoehtoisen lähestymistavan inkluusio/poissulkemisperiaatteella vähentämään yli iteroitujen Hamiltonin syklien määrää, ja syklien laskentaongelma voidaan ratkaista laskemalla jonkin matriisin determinantti.

Tällä menetelmällä hän osoitti, kuinka Hamiltonin sykliongelma ratkaistaan ​​mielivaltaisille n - pisteisille graafille käyttämällä Monte Carlo -algoritmia ajassa . Kaksiosaisten graafien tapauksessa tätä algoritmia voidaan parantaa ajan myötä [7] .

Graafeille, joilla on maksimiaste kolme, tarkka backtracking - haku voi löytää Hamiltonin syklin (jos sellainen on) ajassa [8] .

Hamiltonin polut ja syklit löytyvät SAT-ratkaisijalla .

Koska Hamiltonin polku- ja sykliongelmien ratkaiseminen tavallisilla tietokoneilla oli monimutkainen, niitä tutkittiin ei-standardeille laskennallisille malleille. Esimerkiksi Leonard Adleman osoitti, että Hamiltonin polun ongelmat voidaan ratkaista DNA-tietokoneella . Kemiallisille reaktioille ominaista rinnakkaisuutta käyttämällä ongelma voidaan ratkaista useilla kemiallisten reaktioiden vaiheilla, jotka riippuvat lineaarisesti graafin kärkien lukumäärästä. Tämä vaatii kuitenkin tekijämäärän DNA-molekyylejä, jotka osallistuvat reaktioon [9] .

Hamiltonin ongelman optista ratkaisua ehdotti Oltean [10] . Ajatuksena on luoda optisista kaapeleista ja säteenjakajista graafinen rakenne, jonka läpi ajetaan säde ongelman ratkaisemiseksi. Tämän lähestymistavan heikko kohta on tarvittavan energian eksponentiaalinen kasvu solmujen lukumäärästä.

Vaikeus

Hamiltonin pyöräilyn tai polun löytämisen ongelma on FNP . Samanlainen ratkaistavuusongelma  on tarkistaa, onko olemassa Hamiltonin pyörää tai polkua. Suunnatut ja ohjaamattomat Hamiltonin sykliongelmat olivat kaksi Karpin 21 NP-täydellisesta ongelmasta . Ne pysyvät NP-täydellisinä jopa suuntaamattomille tasograafisille maksimiasteen kolmelle [11] , suunnatuille tasograafisille, joiden tulo- ja lähtöpuoliasteet enintään kaksi [12] , suuntaamattomille tasomaisille 3-säännöllisille kaksiosaisille graafeille ilman siltoja, 3-liitetyille 3 -säännölliset kaksiosaiset graafit [13] , neliöhilan aligraafit [14] ja neliöhilan kuutioalagraafit [15] .

Kuitenkin 4-liitetyt tasograafit ovat Tuttin tuloksen mukaan aina Hamiltonin kaavioita, ja ongelma Hamiltonin syklin löytämisestä näissä kaavioissa voidaan tehdä lineaarisessa ajassa [16] laskemalla ns. Tutt-polku. Tutt todisti tämän tuloksen osoittamalla, että mikä tahansa 2-liitetty tasograafi sisältää Tuttin polun. Tutt-polut puolestaan ​​voidaan laskea kvadraattisessa ajassa jopa 2-liitetyille tasograafisille [17] , joiden avulla voidaan löytää Hamiltonin jaksoja ja pitkiä jaksoja yleistetyistä tasograafista.

Kun kaikki yhteen lasketaan, jää avoimeksi kysymykseksi, pitääkö 3-liitettävien 3-säännöllisten kaksiosaisten tasograafien aina sisältää Hamiltonin sykli, ja jos on, näiden graafien rajoittama ongelma ei ole NP-täydellinen (katso artikkeli " Barnettin arvaus ").

Graafeissa, joissa kaikki kärjet ovat parittomia, kättelylemma- argumentti osoittaa, että Hamiltonin syklien määrä kiinteän reunan läpi on aina parillinen, joten jos yksi Hamiltonin sykli on annettu, niin toisen täytyy olla olemassa [18] . Tämän toisen syklin löytäminen ei kuitenkaan näytä yksinkertaiselta laskentatehtävältä. Papadimitriou määritteli monimutkaisuusluokan PPA tuomaan yhteen tämän kaltaiset ongelmat [19] .

Muistiinpanot

  1. ↑ Garey ja Johnson 1979 , s. 199-200, A1.3: GT37 - 39.
  2. ↑ graafiteoria - pelkistys Hamiltonin syklistä Hamiltonin polulle - Mathematics Stack Exchange . Haettu 18. helmikuuta 2019. Arkistoitu alkuperäisestä 23. huhtikuuta 2019.
  3. ↑ Martello, 1983 , s. 131-138.
  4. ↑ Rubin, 1974 , s. 576–80.
  5. ↑ Bellman, 1962 , s. 61–63.
  6. ↑ Held, Karp, 1962 , s. 196-210.
  7. ↑ Björklund, 2010 , s. 173-182.
  8. ↑ Iwama, Nakashima, 2007 , s. 108-117.
  9. ↑ Adleman, 1994 , s. 1021–1024.
  10. ↑ Oltean, 2006 , s. 217-227.
  11. ↑ Garey, Johnson & Stockmeyer, 1974 , s. 47–63.
  12. ↑ Plesńik, 1979 , s. 199-201.
  13. ↑ Akiyama, Nishizeki, Saito, 1980-1981 , s. 73–76.
  14. ↑ Itai, Papadimitriou, Szwarcfiter, 1982 , s. 676–686.
  15. ↑ Buro, 2000 , s. 250–261.
  16. ↑ Chiba, Nishizeki, 1989 , s. 187–211.
  17. ↑ Schmid, Schmidt, 2018 .
  18. ↑ Thomason, 1978 , s. 259–268.
  19. ↑ Papadimitriou, 1994 , s. 498–532.

Kirjallisuus