Pisimmän polun ongelma

Pisin polkuongelma on yksinkertaisen maksimipituisen polun löytäminen annetusta graafista. Polkua kutsutaan yksinkertaiseksi, jos sillä ei ole toistuvia pisteitä. Reitin pituus voidaan mitata joko reunojen lukumäärällä tai ( painotettujen graafien tapauksessa ) sen reunojen painojen summalla. Toisin kuin lyhimmän polun ongelma , joka voidaan ratkaista polynomiajassa kaavioissa, joissa ei ole negatiivisia painosyklejä, pisin polkuongelma on NP-kova eikä sitä voida ratkaista polynomiajassa mielivaltaisille kaavioille, ellei P = NP . Raskaampaan kompleksisuusluokkaan kuuluminen tarkoittaa myös, että ongelmaa on vaikea arvioida. Ongelma ratkeaa kuitenkin lineaarisessa ajassa suunnatuissa asyklisissä kaavioissa , joilla on tärkeitä sovelluksia kriittisissä polkuongelmissa ajoitusongelmissa.

NP-vaikeus

Pisimmän polun löytämisen painottamattoman ongelman NP-kovuus voidaan osoittaa vähentämällä tehtävä Hamiltonin polun löytämiseksi — graafilla G on Hamiltonin polku silloin ja vain, jos sen pisimmän polun pituus on n  − 1 , jossa n on graafin kärkien G määrä. _ Koska Hamiltonin polun löytämisen ongelma on NP-täydellinen, tämä pelkistys osoittaa, että pisimmän polun löytämisen ongelma ratkaistavassa tapauksessa on myös NP-täydellinen. Tässä ratkaistavuustehtävässä syöte on graafi G ja luku k . Odotettu tulos on "kyllä", jos G sisältää polun, jossa on vähintään k kaaria, tai ei muuten [1] .

Jos pisimmän polun löytämisen ongelma voitaisiin ratkaista polynomiajassa, sitä voitaisiin käyttää tämän ratkaistavuusongelman ratkaisemiseen etsimällä pisin polku ja vertaamalla tuloksena olevan polun pituutta numeroon k . Siten pisimmän polun löytämisen ongelma on NP-kova. Se ei ole NP-täydellinen, koska se ei ole ratkaistavuusongelma [2] .

Painotetuissa täydellisissä graafisissa ei-negatiivisilla reunapainoilla painotetun pisimmän polun löytäminen on sama ongelma kuin liikkuvan myyjän ongelma , koska pisin polku sisältää aina tämän tehtävän kaikki kärjet [3] .

Asykliset kuvaajat ja kriittiset polut

Pisin polku A kahden annetun pisteen s ja t välillä painotetussa graafissa G on sama kuin graafin − G lyhin polku, joka saadaan G :stä muuttamalla kaikki painot painoiksi, joilla on vastakkainen etumerkki. Siten, jos lyhin polku löytyy −G :stä , niin pisin polku G :stä [4] löytyy myös .

Useimmille kaavioille tämä muunnos on hyödytön, koska se luo negatiivisen pituisia syklejä -G: ssä . Mutta jos G on suunnattu asyklinen graafi , on mahdotonta luoda negatiivista sykliä ja pisin polku G :ssä voidaan löytää lineaarisessa ajassa käyttämällä lyhimmän polun algoritmia −G:ssä ( myös suunnattu asyklinen graafi), joka kulkee lineaarisessa ajassa [4] . Esimerkiksi mille tahansa suunnatun asyklisen graafin pisteelle v pisimmän polun pituus, joka päättyy v :ään, voidaan saada suorittamalla seuraavat vaiheet:

  1. Suoritamme annetun suunnatun asyklisen graafin (OAG) topologisen lajittelun .
  2. OAG:n kullekin kärjelle v topologisessa lajittelussa lasketaan pisimmän polun pituus, joka päättyy kärkeen v , katsomalla naapureista saapuvia kaaria ja lisäämällä yksi näiden naapurien tietueiden enimmäispituuteen. Jos v :llä ei ole saapuvia kaaria, aseta pisimmän v - päätteisen polun pituus nollaan.

Kun tämä on tehty, koko graafin pisin polku voidaan saada aloittamalla kärjestä v , jolla on suurin tallennettu arvo ja työstämällä taaksepäin, valitsemalla tuleva kaari, jonka aloituspisteen syöttö on suurin.

Kriittinen polkumenetelmä toimintosarjan ajoittamiseen käyttää suunnatun asyklisen graafin rakentamista, jossa kärjet edustavat projektin solmutapahtumia ja kaaret ennen ja jälkeen solmutapahtumaa tehtävää työtä. Jokaiselle kaarelle on määritetty paino, joka vastaa arvioitua työn valmistumisaikaa. Tällaisessa kaaviossa pisin polku ensimmäisestä solmutapahtumasta viimeiseen on kriittinen polku, joka määrittää projektin kokonaisvalmistumisajan [4] .

Suunnattujen asyklisten graafien pisintä polkua voidaan käyttää myös graafien kerros kerrokselta piirtämiseen - sijoitamme suunnatun asyklisen graafin G kukin kärki v tasolle, jonka numero vastaa pisimmän v päättyvän polun pituutta . Tuloksena saadaan huippupisteiden järjestely tasoittain, jolloin tasojen määrä on minimaalinen [5] .

Arviointi

Bjorklund, Hasfeldt ja Kanna kirjoittivat, että pisimmän polun löytämisen ongelma painottamattomassa suuntaamattomassa graafissa on "pahamaines siitä, että sen approksimaatiovaikeus on vaikea ymmärtää" [6] . Tunnetuin polynomin ajonaikaisen approksimaatioalgoritmi antaa vain erittäin heikon approksimation, [7] . Mikään ei voi approksimoida pisintä polkua kertoimella, joka on pienempi kuin , ellei NP kuulu kvasipolynomisiin deterministisiin aikaongelmiin . Tämän approksimaatiotuloksen ja tämän ongelman tunnettujen approksimaatioalgoritmien välillä on kuitenkin suuri ero [8] .

Painottamattomien mutta suunnattujen graafien tapauksessa on olemassa hyvin tunnettuja vahvoja approksimiteettituloksia. Kun kyseessä on , ongelmaa ei voida approksimoida sisällä , ellei P = NP, ja vahvojen teoreettisten oletusten mukaan ongelmaa ei voida approksimoida sisällä [6] . Voit käyttää värikoodaustekniikkaa löytääksesi logaritmisen pituuspolun, jos sellainen on olemassa, mutta tämä tekniikka antaa vain likimääräisen kertoimen [ 9] .

Parametrisoitu monimutkaisuus

Pisimmän polun löytämisen ongelma on kiinteä-parametrisesti ratkaistava , jos se parametroidaan polun pituudella. Ongelma voidaan ratkaista esimerkiksi ajassa, joka on lineaarinen syötekaavion koossa (mutta eksponentiaalisessa ajassa polun pituudessa) algoritmilla, joka suorittaa seuraavat vaiheet:

  1. Suoritamme kaavion syvyyshaun . Antaa olla syvyys tuloksena haku puu syvälle .
  2. Käytämme polkuja juuresta lehtiin hakupuun syvyydessä siinä järjestyksessä, jossa ne on haettu, toisin kuin polkukaavion jaottelu polunleveydellä .
  3. Käytämme dynaamista ohjelmointia tähän polun hajotteluun löytääksemme pisimmän polun ajassa , jossa on graafin kärkien lukumäärä.

Koska lähtöpolun pituus on vähintään , ajoaikaa rajoittaa myös , jossa on pisimmän polun pituus [10] . Värikoodausta käyttämällä polun pituuden riippuvuus voidaan vähentää yhteen eksponentiaaliin [11] [12] [13] . Samanlainen dynaaminen ohjelmointitekniikka osoittaa, että pisin polkuongelma on myös kiinteäparametrisesti ratkaistavissa graafin puun leveydellä .

Graafeissa, joilla on rajoitettu klikkin leveys , pisin polkuongelma voidaan ratkaista polynomiajassa käyttämällä dynaamista ohjelmointialgoritmia. Polynomin aste riippuu kuitenkin graafin klikkin leveydestä, joten nämä algoritmit eivät ole kiinteillä parametreilla päätettäviä. Tehtävä löytää klikin leveydellä parametroitu pisin polku on vaikea parametrisoidun kompleksisuuden luokalle , mikä tarkoittaa, että kiinteän parametrin ratkaisevaa algoritmia tuskin on olemassa [14] .

Kaavioiden erikoistapaukset

Pisin reittiongelma voidaan ratkaista polynomiajassa vertailtavuusgraafien komplementeilla [15] . Se voidaan myös ratkaista polynomiajassa missä tahansa graafiluokissa, joilla on rajoitettu puun leveys tai rajattu klikkin leveys, kuten etäisyyden periytyvissä kaavioissa . Ongelma on kuitenkin NP-kova, vaikka rajoittuisimme jaettuihin kaavioihin , ympyräkaavioihin tai tasokaavioihin [16] .

Katso myös

Muistiinpanot

  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 ). Katso aikaisemmat työt, jopa heikoimmalla approksimaatiolla, Gabowin ( Gabow 2007 ) sekä Björklundin ja Hasfeldtin ( Björklund, Husfeldt 2003 ) artikkeleista.
  8. ↑ Karger, Motwani & Ramkumar, 1997 , s. 82–98.
  9. ↑ Alon, Yuster, Zwick, 1995 .
  10. ↑ ( Bodlaender 1993 ). Katso Monien 1985 :stä aikaisempi kiinteän parametrin päätettävä algoritmi, jonka riippuvuus polun pituudesta oli hieman parempi, mutta huonompi riippuvuus graafin pituudesta .
  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 ja Nikolopoulos 2011 ). Aiempi työ rajoitetuista luokista, katso ( Ioannidou, Mertzios, Nikolopoulos 2011 ) ja ( Uehara, Valiente 2007 ).
  16. ↑ Ioannidou, Mertzios, Nikolopoulos, 2011 .

Kirjallisuus

Linkit