Problemet med den længste vej

Det længste vejproblem er problemet med at finde en simpel vej med maksimal længde i en given graf. En sti kaldes simpel, hvis den ikke har gentagne hjørner. Længden af ​​en sti kan måles enten ved antallet af kanter eller (i tilfælde af vægtede grafer ) ved summen af ​​vægtene af dens kanter. I modsætning til det korteste vejproblem , som kan løses i polynomiel tid på grafer uden negative vægtcyklusser, er det længste vejproblem NP-hårdt og kan ikke løses i polynomiel tid for vilkårlige grafer, medmindre P = NP . At tilhøre en tungere kompleksitetsklasse betyder også, at problemet er svært at tilnærme sig. Problemet er dog løst i lineær tid på rettede acykliske grafer , som har vigtige anvendelser i kritiske vejproblemer i planlægningsproblemer.

NP-sværhedsgrad

NP-hårdheden af ​​det uvægtede problem med at finde den længste vej kan vises ved at reducere problemet til at finde en Hamiltonsk bane — en graf G har en Hamiltonsk bane, hvis og kun hvis den længste vej i den har længden n  − 1 , hvor n er antallet af grafens toppunkter G. _ Da problemet med at finde en Hamiltonsk vej er NP-komplet, viser denne reduktion, at problemet med at finde den længste vej i det løselige tilfælde også er NP-komplet. I dette løselighedsproblem er input en graf G og et tal k . Det forventede output er "ja", hvis G indeholder en sti med k eller flere buer, eller på anden måde nej [1] .

Hvis problemet med at finde den længste vej kunne løses i polynomisk tid, kunne det bruges til at løse dette løselighedsproblem ved at finde den længste vej og sammenligne længden af ​​den resulterende vej med tallet k . Problemet med at finde den længste vej er således NP-hårdt. Det er ikke NP-komplet, fordi det ikke er et løselighedsproblem [2] .

I vægtede komplette grafer med ikke-negative kantvægte er problemet med at finde den vægtede længste vej det samme problem som det rejsende sælgerproblem , da den længste vej altid inkluderer alle hjørnerne af dette problem [3] .

Acykliske grafer og kritiske stier

Den længste vej A mellem to givne toppunkter s og t i en vægtet graf G er den samme som den korteste vej i grafen − G opnået fra G ved at ændre alle vægte til vægte med modsat fortegn. Således, hvis den korteste vej kan findes i − G , så kan den længste vej i G [4] også findes .

For de fleste grafer er denne transformation ubrugelig, da den skaber cyklusser med negativ længde i − G . Men hvis G er en rettet acyklisk graf , er det umuligt at skabe en negativ cyklus, og den længste vej i G kan findes i lineær tid ved at anvende den korteste vejalgoritme i − G (også en rettet acyklisk graf), der løber i lineær tid [4] . For et hvilket som helst toppunkt v i en rettet acyklisk graf kan længden af ​​den længste vej, der slutter ved v , f.eks. opnås ved at udføre følgende trin:

  1. Vi udfører topologisk sortering af den givne rettede acykliske graf (OAG).
  2. For hvert toppunkt v af OAG i en topologisk sortering beregner vi længden af ​​den længste vej, der slutter ved toppunkt v ved at se på de indkommende buer fra naboerne og lægge en til den maksimale længde i disse naboers optegnelser. Hvis v ikke har nogen indgående buer, skal du indstille længden af ​​den længste sti, der ender på v , til nul.

Når dette er gjort, kan den længste vej i hele grafen opnås ved at starte ved toppunktet v med den største registrerede værdi og arbejde baglæns, vælge den indkommende bue, hvis startpunktindgang har den største værdi.

Den kritiske sti-metode til at planlægge et sæt aktiviteter bruger konstruktionen af ​​en rettet acyklisk graf, hvor knudepunkterne repræsenterer projektets knudepunkter, og buerne repræsenterer det arbejde, der skal udføres før og efter knudehændelsen. Hver bue tildeles en vægt svarende til den estimerede tid til at fuldføre arbejdet. I en sådan graf er den længste vej fra den første knudehændelse til den sidste den kritiske vej, som bestemmer projektets samlede gennemførelsestid [4] .

Den længste vej af rettede acykliske grafer kan også bruges til lag-for- lag tegning af grafer - vi placerer hvert toppunkt v af en rettet acyklisk graf G på et niveau, hvis nummer svarer til længden af ​​den længste vej, der slutter på v . Som et resultat får vi opstillingen af ​​hjørner efter niveauer, hvor antallet af niveauer vil være minimalt [5] .

Tilnærmelse

Bjorklund, Hasfeldt og Kanna skrev, at problemet med at finde den længste vej i en uvægtet urettet graf er "berygtet for sin vanskelighed med at forstå dens tilnærmelsessværhed" [6] . Den bedst kendte polynomielle runtime approksimationsalgoritme giver kun en meget svag tilnærmelse, [7] . Det er ikke muligt for nogen at tilnærme den længste vej med en faktor mindre end , medmindre NP tilhører kvasi-polynomielle deterministiske tidsproblemer . Der er dog et stort hul mellem dette tilnærmelsesresultat og kendte tilnærmelsesalgoritmer for dette problem [8] .

I tilfælde af uvægtede men rettede grafer er der velkendte stærke tilnærmelsesresultater. For nogen , kan problemet ikke tilnærmes inden for , medmindre P = NP, og under stærke teoretiske antagelser kan problemet ikke tilnærmes inden for [6] . Du kan bruge farvekodningsteknikken til at finde en logaritmisk længdesti, hvis den findes, men denne teknik giver kun en tilnærmelsesfaktor [ 9] .

Parameteriseret kompleksitet

Problemet med at finde den længste vej er fast-parametrisk løses , hvis det er parametriseret af længden af ​​stien. For eksempel kan problemet løses i tid, der er lineær i størrelsen af ​​inputgrafen (men i eksponentiel tid i længden af ​​stien) med en algoritme, der tager følgende trin:

  1. Vi udfører en dybde-først søgning på grafen. Lad være dybden af ​​det resulterende søgetræ dybt ind i .
  2. Vi bruger stierne fra roden til søgetræets blade i dybden i den rækkefølge, de søges i, i modsætning til stigrafnedbrydning med stibredde .
  3. Vi bruger dynamisk programmering til denne stinedbrydning for at finde den længste sti i tiden , hvor er antallet af grafens toppunkter.

Da udgangsvejen har en længde på mindst , vil køretiden også være begrænset af , hvor er længden af ​​den længste vej [10] . Ved hjælp af farvekodning kan vejlængdeafhængigheden reduceres til en enkelt eksponentiel [11] [12] [13] . En lignende dynamisk programmeringsteknik viser, at det længste vejproblem også er fast-parametrisk løseligt i grafens træbredde .

For grafer med begrænset klikbredde kan det længste vejproblem løses i polynomiel tid ved hjælp af en dynamisk programmeringsalgoritme. Graden af ​​polynomiet afhænger dog af grafens klikbredde, så disse algoritmer kan ikke bestemmes med faste parametre. Opgaven med at finde den længste vej parametriseret af klikbredde er vanskelig for klassen af ​​parameteriseret kompleksitet , hvilket betyder, at der næppe findes en fast-parametrisk løselig algoritme [14] .

Særlige tilfælde af grafer

Det længste vejproblem kan løses i polynomisk tid på komplementerne af sammenlignelighedsgrafer [15] . Det kan også løses i polynomisk tid på enhver klasse af grafer med afgrænset træbredde eller afgrænset klikbredde, såsom afstandsarvede grafer . Problemet er dog NP-svært, selvom vi begrænser os til delte grafer , cirkelgrafer eller plane grafer [16] .

Se også

Noter

  1. ↑ Schrijver, 2003 , s. 114.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , s. 978.
  3. ↑ Lawler, 2001 , s. 64.
  4. ↑ 1 2 3 Sedgewick, Wayne, 2011 , s. 661-666.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 265-302.
  6. ↑ 1 2 Björklund, Husfeldt, Khanna, 2004 , s. 222-233.
  7. ↑ ( Gabow, Nie 2008 ). For tidligere arbejde, selv med en svagere tilnærmelse, se artiklerne af Gabow ( Gabow 2007 ) og Björklund og Hasfeldt ( Björklund, Husfeldt 2003 ).
  8. ↑ Karger, Motwani & Ramkumar, 1997 , s. 82-98.
  9. ↑ Alon, Yuster, Zwick, 1995 .
  10. ↑ ( Bodlaender 1993 ). For en tidligere fast-parameter afgørbar algoritme med lidt bedre afhængighed af vejlængde men værre afhængighed af graflængde, se Monien 1985 .
  11. ↑ Chen, Lu, Sze, Zhang, 2007 , s. 298-307.
  12. ↑ Koutis, 2008 , s. 575-586.
  13. ↑ Williams, 2009 , s. 315-318.
  14. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2009 , s. 825-834.
  15. ↑ ( Ioannidou og Nikolopoulos 2011 ). For tidligere arbejde om mere begrænsede klasser, se ( Ioannidou, Mertzios, Nikolopoulos 2011 ) og ( Uehara, Valiente 2007 ).
  16. ↑ Ioannidou, Mertzios, Nikolopoulos, 2011 .

Litteratur

Links