Hamiltonsk vejproblem

Det Hamiltonske stiproblem og det Hamiltonske cyklusproblem  er problemer med at bestemme, om der er en Hamiltonsk sti eller en Hamiltonsk cyklus i en given graf ( rettet eller ikke- rettet ). Begge problemer er NP-komplette [1] .

Forholdet mellem problemer på den Hamiltonske vej og den Hamiltonske cyklus

Der er et simpelt forhold mellem problemerne med at finde en Hamilton-sti og at finde en Hamilton-cyklus. I den ene retning svarer problemet med en Hamiltonsk bane til en graf til problemet med en Hamiltonsk cyklus i en graf H opnået fra en graf G ved at tilføje et nyt toppunkt og forbinde det med alle toppunkter i grafen G. Finder således en Hamiltonsk sti kan ikke være væsentligt langsommere (i værste fald, , som funktion af antallet af toppunkter) end at lede efter en Hamiltonsk cyklus.

I den modsatte retning er problemet med en Hamiltonsk cyklus for en graf G ækvivalent med problemet med en Hamiltonsk bane i en graf H opnået ved at kopiere et toppunkt v af grafen G (ind i v'), det vil sige toppunktet v ' vil have samme naboskab som v, og tilføjelse af to hjælpehjørner af grad en, hvoraf den ene er forbundet med v og den anden til v' [2] .

Hamilton-cyklusproblemet er også et specialtilfælde af rejsende sælgerproblem , opnået ved at indstille alle afstande mellem to punkter til et, hvis de er tilstødende, og to ellers. Efter at have løst problemet med den rejsende sælger, skal du kontrollere, at den samlede afstand er lig med n (hvis ja, er ruten en Hamilton-cyklus, hvis der ikke er nogen Hamilton-cyklus, vil den korteste vej være længere end denne værdi).

Algoritmer

Der er n ! forskellige sekvenser af toppunkter, som kunne være Hamiltonske stier i en given graf med n toppunkter (og der er så mange i hele grafen ), så en brute-force algoritme , der prøver alle mulige sekvenser, ville være meget langsom.

En tidlig eksakt algoritme til at finde en Hamiltonsk cyklus i en rettet graf var optællingsalgoritmen (Martellos algoritme) [3] .

Søgeproceduren for Frank Rubin [4] opdeler grafkanterne i tre klasser - dem, der skal være på stien, dem, der ikke kan tilhøre stien, og kanter, for hvilke der ikke er truffet en beslutning. Under søgningen klassificerer et sæt beslutningsregler de kanter, for hvilke der ikke er truffet nogen beslutning, og bestemmer, om søgningen skal stoppes eller fortsættes. Algoritmen opdeler grafen i komponenter, der kan behandles separat.

For at løse problemet i tide kan den dynamiske programmeringsalgoritme fra Bellman, Held og Karp bruges . Denne metode bestemmer, for hvert sæt S af toppunkter og hvert toppunkt v af S , om der er en sti, der passerer gennem alle toppunkterne af S og ender ved v . For hvert par ( S , v ) eksisterer der en sti, hvis og kun hvis v har et nabopunkt w , således at der er en sti for , som kan fås fra den dynamiske programmeringsinformation, der allerede er opnået [5] [6] .

Andreas Björklund giver en alternativ tilgang ved hjælp af inklusion/udelukkelsesprincippet for at reducere antallet af Hamiltonske cyklusser, der gentages, og cyklustællingsproblemet kan løses ved at beregne determinanten for en eller anden matrix.

Ved hjælp af denne metode viste han, hvordan man løser Hamiltons cyklusproblem for vilkårlige grafer med n toppunkter ved hjælp af Monte Carlo-algoritmen i tid . For todelte grafer kan denne algoritme forbedres op til tiden [7] .

For grafer med maksimal grad tre kan en nøjagtig tilbagesporingssøgning finde en Hamilton-cyklus (hvis en findes) i tid [8] .

Hamiltonske stier og cykler kan findes ved hjælp af SAT-løseren .

På grund af kompleksiteten ved at løse Hamiltonske sti- og cyklusproblemer på almindelige computere, blev de undersøgt for ikke-standardiserede beregningsmodeller. For eksempel viste Leonard Adleman , at Hamiltonske stiproblemer kunne løses med en DNA-computer . Ved at bruge paralleliteten i kemiske reaktioner kan problemet løses ved hjælp af flere trin af kemiske reaktioner, der afhænger lineært af antallet af grafens toppunkter. Dette kræver dog et faktorielt antal DNA-molekyler involveret i reaktionen [9] .

Den optiske løsning af Hamilton-problemet blev foreslået af Oltean [10] . Ideen er at skabe en graflignende struktur af optiske kabler og stråledelere, hvorigennem en stråle føres for at løse problemet. Det svage punkt ved denne tilgang er den eksponentielle vækst af den nødvendige energi fra antallet af noder.

Sværhedsgrad

Problemet med at finde en Hamiltonsk cykel eller sti er FNP . Et lignende afgørelighedsproblem  er at kontrollere, om der er en Hamiltonsk cykel- eller sti. Direkte og urettede Hamiltonske cyklusproblemer var to af Karps 21 NP-komplette problemer . De forbliver NP-komplette selv for urettede plane grafer af maksimal grad tre [11] , for rettede plane grafer med input og output halvgrader højst to [12] , for urettede plane 3-regulære todelte grafer uden broer, for 3-forbundne 3 -regulære todelte grafer [13] , undergrafer af et kvadratisk gitter [14] og for kubiske undergrafer af et kvadratisk gitter [15] .

4-forbundne plane grafer er dog altid Hamiltonske, ifølge Tutts resultat, og problemet med at finde en Hamiltonsk cyklus i disse grafer kan gøres i lineær tid [16] ved at beregne den såkaldte Tutt-bane. Tutt beviste dette resultat ved at vise, at enhver 2-forbundet plan graf indeholder Tutts vej. Tutt-baner kan til gengæld beregnes i kvadratisk tid selv for 2-forbundne plane grafer [17] , som kan bruges til at finde Hamiltonske cyklusser og lange cyklusser i generaliserede plane grafer.

Når man sætter det hele sammen, er det stadig et åbent spørgsmål, om 3-forbundne 3-regulære todelte plane grafer altid skal indeholde en Hamilton-cyklus, og hvis det er tilfældet, vil problemet afgrænset af disse grafer ikke være NP-komplet (se artiklen " Barnetts formodning ").

I grafer, hvor alle hjørner er af ulige grad, viser handshake lemma- argumentet , at antallet af Hamilton-cyklusser gennem en fast kant altid er lige, så hvis en Hamilton-cyklus er givet, så skal der eksistere en anden [18] . Men at finde denne anden cyklus ligner ikke en simpel beregningsopgave. Papadimitriou definerede kompleksitetsklassen PPA for at samle problemer som denne [19] .

Noter

  1. ↑ Garey og Johnson 1979 , s. 199-200, A1.3: GT37 - 39.
  2. ↑ grafteori - Reduktion fra Hamiltonsk cyklus til Hamiltonsk sti - Mathematics Stack Exchange . Hentet 18. februar 2019. Arkiveret fra originalen 23. april 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.

Litteratur