A leghosszabb út problémája

A leghosszabb út probléma az, hogy egy adott gráfban egy maximális hosszúságú egyszerű utat találjunk. Egy útvonalat egyszerűnek nevezünk, ha nincs ismétlődő csúcsa. Egy út hosszát vagy az élek számával, vagy ( súlyozott gráfok esetén ) az élek súlyának összegével mérhetjük . Ellentétben a legrövidebb út problémával , amely polinomiális idő alatt megoldható negatív súlyú ciklusok nélküli gráfokon, a leghosszabb út probléma NP-nehéz , és tetszőleges gráfok esetén nem oldható meg polinomiális időben , hacsak nem P = NP . A nehezebb összetettségi osztályhoz való tartozás azt is jelenti, hogy a problémát nehéz közelíteni . A probléma azonban lineáris időben megoldható irányított aciklikus gráfokon , amelyeknek fontos alkalmazásai vannak az ütemezési problémák kritikus útproblémáiban.

NP-nehézség

A leghosszabb út megtalálásának súlyozatlan problémájának NP-keménysége megmutatható úgy, hogy a feladatot egy Hamilton-út megtalálására redukáljuk – egy G gráfnak akkor és csak akkor van Hamilton-útja, ha a benne lévő leghosszabb út hossza n  − 1 , ahol n a G gráf csúcsok száma . Mivel a Hamilton-út megtalálásának problémája NP-teljes, ez a redukció azt mutatja, hogy a megoldható esetben a leghosszabb út megtalálásának problémája is NP-teljes. Ebben a megoldhatósági feladatban a bemenet egy G gráf és egy k szám . A várt kimenet "igen", ha G tartalmaz egy k vagy több íves utat, vagy egyébként nincs [1] .

Ha a leghosszabb út megtalálásának problémája megoldható polinomiális időben, akkor ezt a megoldhatósági problémát úgy lehetne megoldani, hogy megtaláljuk a leghosszabb utat, és összehasonlítjuk a kapott út hosszát a k számmal . Így a leghosszabb út megtalálásának problémája NP-nehéz. Nem NP-teljes, mert nem megoldhatósági probléma [2] .

Súlyozott , nem negatív élsúlyú teljes gráfokban a súlyozott leghosszabb út megtalálásának problémája ugyanaz , mint az utazó eladó problémájával , mivel a leghosszabb út mindig ennek a feladatnak az összes csúcsát tartalmazza [3] .

Aciklikus gráfok és kritikus utak

A leghosszabb A út két adott s és t csúcs között egy súlyozott G gráfban megegyezik a gráf legrövidebb útjával − G , amelyet G-ből kapunk úgy , hogy minden súlyt ellentétes előjelű súlyokra változtatunk. Így, ha a legrövidebb út található − G -ben , akkor a leghosszabb út G -ben [4] is megtalálható .

A legtöbb gráf esetében ez a transzformáció haszontalan, mivel negatív hosszúságú ciklusokat hoz létre − G -ben . De ha G egy irányított aciklikus gráf , lehetetlen negatív ciklust létrehozni, és a leghosszabb út G -ben megtalálható lineáris időben a legrövidebb útvonal algoritmus alkalmazásával − G -ben (szintén irányított aciklikus gráf), amely lineáris időben fut. [4] . Például egy irányított aciklikus gráf bármely v csúcsához a v -re végződő leghosszabb út hosszát a következő lépések végrehajtásával kaphatjuk meg:

  1. Az adott irányított aciklikus gráfon (OAG) topológiai rendezést végzünk.
  2. Az OAG minden v csúcsához topológiai rendezésben kiszámítjuk a v csúcsnál végződő leghosszabb út hosszát úgy, hogy megnézzük a szomszédoktól bejövő íveket, és hozzáadunk egyet a szomszédok rekordjaiban található maximális hosszhoz. Ha v -nek nincsenek bejövő ívei, állítsa a v -re végződő leghosszabb út hosszát nullára.

Ha ez megtörtént, akkor a teljes gráfban a leghosszabb utat kaphatjuk meg úgy, hogy a legnagyobb rögzített értékű v csúcstól indulunk , és visszafelé haladunk, kiválasztva azt a bejövő ívet, amelynek kezdő csúcsbejegyzése a legnagyobb értékű.

A tevékenységek halmazának ütemezésére szolgáló kritikus útvonal módszer egy irányított aciklikus gráf felépítését használja, amelyben a csúcsok a projekt csomóponti eseményeit, az ívek pedig a csomóponti esemény előtt és után elvégzendő munkát jelentik. Minden ívhez hozzárendelnek egy súlyt, amely megegyezik a munka befejezéséhez szükséges becsült idővel. Egy ilyen gráfban az első csomóponti eseménytől az utolsóig a leghosszabb út a kritikus út, amely meghatározza a projekt teljes befejezési idejét [4] .

Az irányított aciklikus gráfok leghosszabb útja a gráfok rétegenkénti rajzolására is használható - egy irányított aciklikus G gráf minden v csúcsát olyan szintre helyezzük , amelynek száma megfelel a v -vel végződő leghosszabb út hosszának . Ennek eredményeként megkapjuk a csúcsok szintek szerinti elrendezését, amelynél a szintek száma minimális lesz [5] .

Közelítés

Bjorklund, Hasfeldt és Kanna azt írták, hogy a súlyozatlan irányítatlan gráfban a leghosszabb út megtalálásának problémája "hírhedt arról, hogy nehéz megérteni a közelítési nehézséget" [6] . A legismertebb polinomiális futásidejű közelítési algoritmus csak nagyon gyenge közelítést ad, [7] . A leghosszabb utat egyiknél sem közelítheti meg kisebb tényezővel , hacsak NP nem tartozik kvázipolinomiális determinisztikus időproblémák közé . A közelítési eredmény és a probléma ismert közelítési algoritmusai között azonban nagy a szakadék [8] .

Súlyozatlan, de irányított gráfok esetében jól ismert erős közelítési eredmények vannak. Bármelyik esetén a probléma nem közelíthető -on belül , hacsak nem P = NP, és erős elméleti feltevések mellett a probléma nem közelíthető [6] -on belül . A színkódolási technikával megkeresheti a logaritmikus hosszútvonalat, ha létezik, de ez a technika csak közelítő tényezőt ad [9] .

Paraméterezett komplexitás

A leghosszabb út megtalálásának problémája fix-parametrikusan megoldható , ha az út hosszával paraméterezzük. Például a probléma megoldható időben lineárisan a bemeneti gráf méretében (de exponenciális időben az út hosszában) egy olyan algoritmussal, amely a következő lépéseket hajtja végre:

  1. A grafikonon mélységi keresést végzünk . Legyen az eredményül kapott keresési fa mélysége a .
  2. A keresési fa gyökerétől a levelekig tartó útvonalakat mélységben használjuk a keresés sorrendjében, ellentétben a görbe szélességével .
  3. Dinamikus programozást használunk ehhez az útvonalbontáshoz, hogy megtaláljuk a leghosszabb utat az időben , ahol a gráf csúcsainak száma.

Mivel a kimeneti út hossza legalább , a futási időt is korlátozza , ahol a leghosszabb út hossza [10] . Színkódolás segítségével az úthossz-függőség egyetlen exponenciálisra csökkenthető [11] [12] [13] . Egy hasonló dinamikus programozási technika azt mutatja, hogy a leghosszabb útprobléma is fix paraméterekkel megoldható a gráf faszélességében .

A korlátozott kattintásszélességű gráfok esetében a leghosszabb útprobléma megoldható polinomiális időben egy dinamikus programozási algoritmus segítségével. A polinom mértéke azonban a gráf klikkszélességétől függ, így ezek az algoritmusok nem fix paraméterekkel határozhatók meg. A klikk szélességgel paraméterezett leghosszabb út megtalálása nehézkes a paraméterezett komplexitás osztályának , ami azt jelenti, hogy alig van fix paraméterű megoldható algoritmus [14] .

A grafikonok speciális esetei

A leghosszabb út probléma megoldható polinomiális időben az összehasonlíthatósági gráfok komplementerein [15] . Polinomiális időben is megoldható a korlátos faszélességű vagy korlátos klikkszélességű gráfok bármely osztályán, például távolságöröklött gráfokon . A probléma azonban NP-nehéz, még akkor is, ha osztott gráfokra , körgráfokra vagy síkgráfokra szorítkozunk [16] .

Lásd még

Jegyzetek

  1. ↑ Schrijver, 2003 , p. 114.
  2. ↑ Cormen, Leiserson, Rivest, Stein, 2001 , p. 978.
  3. ↑ Lawler, 2001 , p. 64.
  4. ↑ 1 2 3 Sedgewick, Wayne, 2011 , p. 661–666.
  5. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 265–302.
  6. ↑ 1 2 Björklund, Husfeldt, Khanna, 2004 , p. 222–233.
  7. ↑ ( Gabow, Nie 2008 ). A korábbi munkákhoz még gyengébb közelítéssel is lásd Gabow ( Gabow 2007 ), valamint Björklund és Hasfeldt ( Björklund, Husfeldt 2003 ) cikkét.
  8. ↑ Karger, Motwani & Ramkumar, 1997 , p. 82–98.
  9. ↑ Alon, Yuster, Zwick, 1995 .
  10. ↑ ( Bodlaender 1993 ). Egy korábbi, rögzített paraméterű eldönthető algoritmushoz, amely az úthossztól valamivel jobb, de a gráfhossztól rosszabbul függött, lásd Monien 1985 .
  11. ↑ Chen, Lu, Sze, Zhang, 2007 , p. 298-307.
  12. ↑ Koutis, 2008 , p. 575-586.
  13. ↑ Williams, 2009 , p. 315-318.
  14. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2009 , p. 825–834.
  15. ↑ ( Ioannidou és Nikolopoulos 2011 ). A korlátozottabb osztályokkal kapcsolatos korábbi munkákat lásd ( Ioannidou, Mertzios, Nikolopoulos 2011 ) és ( Uehara, Valiente 2007 ).
  16. ↑ Ioannidou, Mertzios, Nikolopoulos, 2011 .

Irodalom

Linkek