Leveimmän polun ongelma

Levein polkuongelma  on kahden valitun kärjen välisen polun löytäminen painotetusta graafista , joka maksimoi graafin vähiten painotetun reunan painon (jos katsomme reunan painon tien leveyteen, niin ongelma on valita levein tie, joka yhdistää kaksi kärkeä). Levein polkuongelma tunnetaan myös pullonkaulaongelmana tai maksimikapasiteettiongelmana . Lyhimmän polun algoritmeja voidaan mukauttaa suorituskyvyn laskemiseen käyttämällä polun pituuden sijaan jotakin erityisarvoa [1] . Monissa tapauksissa nopeammat algoritmit ovat kuitenkin mahdollisia.

Esimerkiksi kaaviossa, joka esittää Internetin reitittimien välisiä yhteyksiä ja jossa reunan paino edustaa kahden reitittimen välisen yhteyden kaistanleveyttä , leveimmän polun löytämisen ongelma vastaa päästä to- päätepolku kahden Internet-solmun välillä, jolla on suurin mahdollinen kaistanleveys [2] [3 ] . Pienin reunapaino tällä polulla tunnetaan polun kapasiteettina tai leveydenä. Verkkoreitityksen sovellusten ohella levein polkuongelma on myös tärkeä osa Schulzen menetelmää voittajan määrittämiseksi monisuuntaisissa vaaleissa [4] , sitä on käytetty digitaalisessa kuvankohdistuksessa [5] , aineenvaihdunta-analyysissä [6] ja maksimivirtausten laskemiseen [7] .

Läheisesti liittyvä minimax - polkuongelma vaatii polkua, joka minimoi minkä tahansa reunan maksimipainon (voidaan tulkita tasaisimman tien löytämiseksi minimaalisilla ylä- ja alamäkikulmilla). Tämä ongelma löytää sovelluksen liikenteen suunnittelussa [8] . Mikä tahansa algoritmi leveimmän polun ongelmalle voidaan muuntaa minimax-polun algoritmiksi ja päinvastoin kääntämällä kaikkien algoritmissa tehtyjen painovertailujen merkitys tai vastaavasti muuttamalla painot negatiivisiksi arvoiksi.

Suuntaamattomat kaaviot

Suuntaamattomassa graafissa levein polku löytyy graafin maksimivirittävän puun kahden kärjen välisenä poluna ja minimax-polku kahden kärjen välisenä poluna minimivirittävän puussa [9] [10] [11 ] .

Missä tahansa graafissa, suunnatussa tai ei, on yksinkertainen algoritmi leveimmän polun löytämiseksi, jos minimiarvon omaavan reunan paino tunnetaan - poista yksinkertaisesti kaikki pienemmällä arvolla olevat reunat ja etsi polku jäljellä olevien reunojen joukosta käyttämällä leveyttä . -ensimmäinen haku tai syvyys -ensin haku . Tähän testiin perustuva lineaarinen aikaalgoritmi leveimmän s - t -polun löytämiseksi suuntaamattomasta graafista, joka ei käytä maksimivirittävän puuta. Algoritmin perusideana on käyttää lineaarista aikaalgoritmia, jolla etsitään polku graafin reunapainojen mediaaniin , ja sitten joko poistetaan kaikki pienemmät reunat tai kutistetaan kaikki suuret reunat sen mukaan, onko polku olemassa vai ei, ja käsittele sitten rekursiivisesti tuloksena oleva pienempi graafi [10] [12] [13] .

Fernandez, Garfinkel ja Arbiol [14] käyttivät pullonkaulaongelmaa ohjaamattomissa kaavioissa saadakseen digitaalisen ilmakuvaaliaksen , joka yhdistää useita kuvia päällekkäisistä alueista. Aliongelmassa, johon sovelletaan levein polkuongelma, kaksi kuvaa on jo muutettu samaan koordinaattijärjestelmään . Jäljelle jää vain valita sauma , käyrä, joka kulkee limityksen läpi ja erottaa kuvan toisesta. Sauman toisella puolella olevat pikselit kopioidaan yhdestä kuvasta, ja sauman toisella puolella olevat pikselit kopioidaan toisesta kuvasta. Toisin kuin muut kuvan kohdistusmenetelmät, joissa molempien kuvien pikselien keskiarvo lasketaan, tämä menetelmä ottaa todellisen valokuvauskuvan jokaisesta valokuvatun alueen osasta. Menetelmässä hilan reunoihin kohdistetaan painoja arvoilla, jotka arvioivat kuinka paljon sauma näkyy visuaalisesti reunassa ja löytävät näille painoille leveimmän polun. Tämän polun käyttäminen saumana perinteisemmän lyhimmän polun sijaan johtaa siihen, että heidän järjestelmänsä löytää sauman, jota on vaikea nähdä sen sijaan, että se parantaisi kuvan yhden osan laatua toisen kustannuksella [5] .

Hilahilan kahden kulman välisen minimax-tehtävän ratkaisemisen avulla voidaan löytää kahden katkoviivan välinen heikko Fréchet-etäisyys . Tässä kukin hilan kärki edustaa segmenttiparia, yhtä kustakin ketjusta, ja reunapaino edustaa Fréchet-etäisyyttä, joka tarvitaan siirtymään segmentiparista toiseen [15] .

Jos kaikki suuntaamattoman graafin reunapainot ovat positiivisia , pisteparien väliset minimietäisyydet (minimax-polkujen suurimmat reunapainot) muodostavat ultrametrisen avaruuden . Sitä vastoin jokainen äärellinen ultrametrinen avaruus muodostetaan tällä tavalla minimax-etäisyyksistä [16] . Vähiten ulottuvasta puusta rakennettu tietorakenne mahdollistaa minkä tahansa kärkiparin välisen minimietäisyyden kyselyn vakioajassa käyttämällä karteesisen puun vähiten yleisiä esivanhempien kyselyitä . Karteesisen puun juuri edustaa vähiten virittävän puun raskainta reunaa, ja juuren lapset ovat karteesisia puita , jotka on muodostettu rekursiivisesti vähiten virittävien puiden alipuista, jotka on muodostettu poistamalla raskain reuna. Karteesisen puun lehdet edustavat syötegraafin kärkipisteitä, ja kahden kärjen välinen minimietäisyys on yhtä suuri kuin sen karteesisen puun solmun paino, joka on niiden vähiten yhteinen esi-isä. Kun vähiten virittävän puun reunat on lajiteltu, tämä karteesinen puu voidaan rakentaa lineaarisessa ajassa [17] .

Suunnatut kaaviot

Suunnatuissa kaavioissa suurinta virittävän puun ratkaisua ei voida käyttää. Sen sijaan tunnetaan joitain erilaisia ​​​​algoritmeja. Kysymys siitä, mikä algoritmi valitaan, riippuu siitä, ovatko polun alku- ja loppupisteet kiinteitä vai onko polkuja etsittävä useista alku- ja loppupisteistä samanaikaisesti.

Kaikki parit

Kaikkien parien laajin polkuongelma sisältää sovelluksia Schulzen menetelmässä voittajan määrittämiseksi moninkertaisissa vaaleissa , jossa äänestäjät arvioivat ehdokkaita etusijalla . Schulzen menetelmä rakentaa täydellisen suunnatun graafin , jossa kärjet edustavat ehdokkaita ja mitkä tahansa kaksi kärkeä on yhdistetty reunalla. Jokainen reuna ohjataan voittajalta häviäjälle kahden ehdokkaan välisissä kaksintaisteluissa, ja sitä leimaa voittajan etu kilpailussa. Menetelmä laskee sitten leveimmän polun kaikkien kärkiparien välillä ja voittaja on ehdokas, jolla on leveimmät polut kunkin vastustajan kanssa [4] . Vaalitulokset tällä menetelmällä ovat yhdenmukaisia ​​Condorcet-menetelmän kanssa  - kaikki taistelut voittanut ehdokas tulee automaattisesti vaalien voittajaksi, mutta menetelmän avulla voit valita voittajan, kun Condorcet-menetelmä ei toimi [18] . Schulze-menetelmää ovat käyttäneet useat organisaatiot, mukaan lukien Wikimedia Foundation [19] .

Leveimmän polun laskemiseksi kaikille solmupareille tiheissä suunnatuissa kaavioissa, kuten äänestyssovelluksissa, asymptoottisesti nopein lähestymistapa toimii ajassa , jossa on nopeiden matriisin kertolaskualgoritmien metriikka . Tunnetuimpia matriisin kertolaskualgoritmeja käytettäessä nämä aikarajat muuttuvat [20] . Varhaisista algoritmeista, jotka käyttivät myös nopeaa matriisikertomista nopeuttamaan leveimpien polkujen löytämistä kaikille pareille, katso Wassilewska, Williams ja Yuster [21] sekä Wassilewskan luku 5 [22] . Schulzen menetelmän referenssitoteutus käyttää modifioitua versiota yksinkertaisemmasta Floyd-Warshall-algoritmista , joka toimii ajassa [4] . Harvaissa kaavioissa voidaan käyttää tehokkaammin laajimman polun hakualgoritmin käyttöä yhdelle lähteelle.

Yksi lähde

Jos reunat lajitellaan niiden painojen mukaan, Dijkstran algoritmin modifioitu versio voi laskea pullonkaulat osoitetun aloituspisteen ja kaikkien muiden graafin kärkien välillä lineaarisessa ajassa. Dijkstran algoritmin tavanomaisella versiolla nopeuttamisen avainajatuksena on, että pullonkaulojen sarja jokaiseen kärkeen asti siinä järjestyksessä, jossa kyseiset pisteet esiintyvät algoritmissa, on monotoninen osasekvenssi, joka on lajiteltu reunasekvenssin painojen mukaan. Siksi Dijkstran algoritmin prioriteettijono voidaan toteuttaa konttijonona , taulukko, jonka numero on 1 - m (kuvaajan reunojen lukumäärä), jossa taulukon solu i sisältää pisteitä, joiden "pullonkaulat" ovat yhtä suuria kuin paino. reunasta, jossa sijainti i on lajiteltu. Tämä menetelmä ratkaisee leveimmän polun ongelman samalla nopeudella kuin lajittelu . Jos esimerkiksi reunapainot ovat kokonaislukuja, niin kokonaislukulajittelun sidottu aika m kokonaisluvun listalle on myös arvio tälle ongelmalle [13] .

Yksi lähde ja yksi kohde

Berman ja Handler [23] ehdottivat, että hätäajoneuvojen ja ambulanssien tulisi käyttää minimax-polkua palatessaan hälytyspisteestä tukikohtaan. Näissä tapauksissa paluuaika on vähemmän tärkeä kuin vastausaika, jos toinen puhelu tapahtuu, kun kone on palaamassa. Käytettäessä minimax-polkua, jossa paino on maksimi matka-aika reunasta mahdollisen kutsun kaukaisimpaan pisteeseen, on mahdollista suunnitella reitti niin, että puhelun vastaanottamisen ja auton saapumisen välillä on mahdollisimman suuri viive. on minimaalinen [8] . Ulla, Lee ja Hassoon [24] käyttivät maksimaalisia polkuja mallintaakseen hallitsevien reaktioiden ketjua metabolisissa verkostoissa . Heidän mallissaan reunan paino on reunan edustama metabolisen reaktion vapaa energia [6] .

Toinen leveimpien reittien sovellus syntyy Ford-Fulkerson - algoritmissa maksimivirtausongelmalle . Virtauksen asteittainen lisääminen reitillä, jolla on maksimikapasiteetti jäännösvirtausverkossa, johtaa pieneen rajaan maksimivirtauksen löytämiseen tarvittavien lisäysten lukumäärälle. Tässä reunakapasiteetit oletetaan kokonaislukuina, jotka eivät ylitä U . Tämä analyysi ei kuitenkaan riipu tarkan maksimikapasitanssin löytämisestä. Mikä tahansa polku, jonka kapasiteetti poikkeaa maksimista vakiokertoimella, on sopiva. Yhdistämällä nämä approksimaatioideat Edmonds-Karp- algoritmin lyhimmän polun lisäysmenetelmään saadaan aikaan maksimivirtausalgoritmi ajoajalla [7] .

Maksimikapasiteetin polkuja ja minimax-polkuja yhdestä lähteestä ja yhdestä kohteesta on mahdollista löytää erittäin tehokkaasti myös sellaisissa laskentamalleissa, jotka mahdollistavat vain syötettyjen graafin reunojen painojen vertailun, ei aritmeettista niiden kanssa [13] [25] . Algoritmi toimii joukolla S reunoja, joiden tiedetään sisältävän optimaalisen polun pullonkaulan reunan. Aluksi S koostuu graafin kaikista m :stä reunasta. Algoritmin jokaisessa iteraatiossa S jaetaan suunnilleen samankokoisten osajoukkojen järjestykseen. Tämän osion osajoukkojen määrä valitaan siten, että kaikki osajoukkojen väliset osiopisteet voidaan löytää etsimällä mediaanit useita kertoja O ( m ) ajassa . Sitten algoritmi laskee uudelleen graafin kaikkien reunojen painot reunan sisältävän osajoukon indeksillä ja käyttää muokattua Dijkstra-algoritmia graafissa päivitetyillä painoilla. Näiden laskelmien tulosten perusteella on mahdollista laskea lineaarisessa ajassa, mikä osajoukoista sisältää pullonkaulan reunapainon. Sitten algoritmi korvaa S : n osajoukolla Si , joka sisältää pullonkaulan painon, ja aloittaa uuden iteroinnin tällä joukolla S . Niiden osajoukkojen määrä, joihin S voidaan jakaa , voi kasvaa eksponentiaalisesti jokaisessa vaiheessa, jolloin iteraatioiden määrä on verrannollinen iteroituun logaritmiin ja kokonaissuoritusaika on [25] . Laskentamallissa, jossa jokaisen reunan paino on koneen kokonaisluku, iteratiivisten logaritmien käyttö tässä algoritmissa voidaan korvata Hahnin ja Thorupin [26] listaosiotekniikalla , joka mahdollistaa S:n osioinnin pienempiin osiin s S i . yhdessä vaiheessa, jolloin tuloksena on lineaarinen yhteinen aikaraja [27] .

Euklidisten pisteiden joukot

Minimax-polun ongelman muunnelmaa otettiin huomioon joukolle pisteitä euklidisessa tasossa . Kuten suuntaamattomassa graafitehtävässä, tämä euklidinen minimax-polkuongelma voidaan ratkaista tehokkaasti etsimällä euklidinen minimivirittävä puu  – mikä tahansa polku puussa on minimax-polku. Ongelmasta tulee kuitenkin monimutkaisempi, jos polun halutaan minimoivan ylemmän pituuden lisäksi myös saman ylemmän pituuden omaavien polkujen joukossa minimoivan tai karkeasti minimoivan polun kokonaispituuden. Ratkaisu voidaan approksimoida geometrisen virittävän puun avulla [28] .

Lukuteoriassa ratkaisematon Gaussin moat - tehtävä kysyy, onko Gaussin alkulukujen minimax-polkujen minimipituus rajoitettu . Toisin sanoen, onko olemassa sellaista vakiota B , että mille tahansa parille p ja q Gaussin alkulukujen määrittelemässä äärettömässä euklidisten pisteiden joukossa minimax-polun p :n ja q :n välisellä Gaussin alkuluvuilla on reunan pituus enintään B ? [29] .

Muistiinpanot

  1. ↑ Pollack, 1960 , s. 733–736.
  2. ↑ Shacham, 1992 , s. 1217–1221.
  3. ↑ Wang, Crowcroft, 1995 , s. 2129–2133.
  4. ↑ 1 2 3 Schulze, 2011 , s. 267-303.
  5. ↑ 1 2 Fernandez, Garfinkel, Arbiol, 1998 , s. 293–304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009 , s. 144-150.
  7. ↑ 1 2 Ahuja, Magnanti ja Orlin, 1993 , s. 210–212.
  8. ↑ 1 2 Berman, Handler, 1987 , s. 115-122.
  9. ↑ Hu, 1961 , s. 898–900.
  10. ↑ 12 Punnen , 1991 , s. 402–404.
  11. ↑ Malpani, Chen, 2002 , s. 175-180.
  12. ↑ Camerini, 1978 , s. 10-14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006 .
  14. ↑ Fernandez, Garfinkel, Arbiol, 1998 .
  15. ↑ Alt, Godau, 1995 , s. 75–91.
  16. ↑ Leclerc, 1981 , s. 5–37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009 , s. 341-353.
  18. ↑ Tarkemmin sanottuna ainoa mahdollisuus, jossa Schulzen menetelmä epäonnistuu, on, kun kahdella ehdokkaalla on yhtä leveät polut toisiinsa nähden.
  19. ↑ Katso Jesse Plamondon-Willard, hallituksen valinta etuoikeusäänestyksen käyttämiseksi , toukokuu 2008; Mark Ryan, 2008 Wikimedian hallituksen vaalien tulokset , kesäkuu 2008; Vuoden 2008 hallituksen vaalit , kesäkuu 2008; ja hallituksen vaalit 2009, elokuu 2009.
  20. ↑ Duan, Pettie, 2009 , s. 384-391.
  21. ↑ Vassilevska, Williams, Yuster, 2007 , s. 585–589.
  22. ↑ Vassilevska, 2008 .
  23. ↑ Berman, Handler, 1987 .
  24. ↑ Ullah, Lee, Hassoun, 2009 .
  25. ↑ 1 2 Gabow, Tarjan, 1988 , s. 411–417.
  26. ↑ Han, Thorup, 2002 .
  27. ↑ Han, Thorup, 2002 , s. 135-144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004 , s. 233-249.
  29. ↑ Gethner, Wagon, Wick, 1998 , s. 327-337.

Kirjallisuus