A legszélesebb út problémája

A legszélesebb útprobléma  az a probléma, hogy egy súlyozott gráfban két kiválasztott csúcs között találunk olyan útvonalat , amely maximalizálja a gráf legkisebb súlyozott élének súlyát (ha az él súlyát tekintjük az út szélességének, akkor a probléma a két csúcsot összekötő legszélesebb út kiválasztása). A legszélesebb útproblémát szűk keresztmetszeti problémának vagy maximális kapacitásproblémának is nevezik . Lehetőség van a legrövidebb út algoritmusainak adaptálására az átviteli sebesség kiszámítására úgy, hogy az úthossz helyett valamilyen speciális értéket használnak [1] . Sok esetben azonban gyorsabb algoritmusok is lehetségesek.

Például egy olyan grafikonon, amely az interneten lévő útválasztók közötti kapcsolatokat ábrázolja , és amelyben egy él súlya a két útválasztó közötti kapcsolat sávszélességét jelenti , a legszélesebb út megtalálásának problémája megfelel a végpontok közötti kapcsolat megtalálásának problémájának. a lehető legszélesebb sávszélességű két internetes csomópont közötti út végét [2] [3] . Ezen a görbén a legkisebb élsúly az útvonal kapacitása vagy szélessége. A hálózati útválasztásban alkalmazott alkalmazások mellett a legszélesebb útprobléma is fontos eleme a Schulze -féle módszernek a többutas választások győztesének meghatározására [4] , alkalmazták digitális képillesztésben [5] , metabolikus áramlási elemzésben [6] és a maximális áramlások kiszámításához [7] .

A szorosan összefüggő minimax útprobléma olyan pályát kér , amely minimalizálja bármelyik él maximális súlyát (ez úgy értelmezhető, hogy megtalálja a legsimább utat minimális emelkedő és lejtési szögekkel). Ez a probléma a forgalomtervezésben is alkalmazható [8] . Bármelyik algoritmus a legszélesebb útvonalproblémára konvertálható minimax útvonal algoritmussá és fordítva az algoritmusban elvégzett összes súlyösszehasonlítás jelentésének megfordításával, vagy ennek megfelelő módon a súlyok negatív értékekre történő megváltoztatásával.

Irányítatlan grafikonok

Irányítatlan gráfban a legszélesebb útvonal két csúcs között található a gráf maximális feszítőfájában , a minimax elérési út pedig két csúcs között található a minimális feszítőfában [9] [10] [11 ] .

Bármely gráfban, akár irányított, akár nem, van egy egyszerű algoritmus a legszélesebb út megtalálására, ha a minimális értékű él súlya ismert - egyszerűen távolítsa el az összes kisebb értékű élt, és keressen utat a fennmaradó élek között a szélesség segítségével. -első keresés vagy mélység -első keresés . Létezik egy lineáris idő algoritmus , amely ezen a teszten alapul, hogy megtalálja a legszélesebb s - t útvonalat egy olyan irányítatlan gráfban, amely nem használ maximális feszítőfát. Az algoritmus alapötlete, hogy egy lineáris idő algoritmust alkalmazunk, hogy megtaláljuk a gráf élsúlyainak mediánjához vezető utat, majd vagy eltávolítjuk az összes kisebb élt, vagy összezsugorítjuk az összes nagyobb élt aszerint, hogy az út létezik-e vagy sem, és majd rekurzívan dolgozzuk fel a kapott kisebbet.gráf [10] [12] [13] .

Fernandez, Garfinkel és Arbiol [14] a szűk keresztmetszetek problémáját használták az irányítatlan gráfokban, hogy digitális légikép -aliasing-et kapjanak , amely az átfedő területek több képét egyesíti. Abban a részproblémában, amelyre a legszélesebb útprobléma vonatkozik, a két kép már át lett konvertálva ugyanabba a koordinátarendszerbe . Csak egy varrást kell kiválasztani , egy görbét, amely átmegy az átfedésen, és elválasztja az egyik képet a másiktól. A varrás egyik oldalán lévő képpontok egy képről, a varrás másik oldalán lévő képpontok pedig egy másik képről kerülnek másolásra. Ellentétben más képigazítási módszerekkel, amelyekben mindkét kép képpontjait átlagolják, ez a módszer valódi fényképes képet készít a fényképezett terület minden részéről. A módszerben súlyokat rendelnek a rács széleihez olyan értékekkel, amelyek megbecsülik, hogy a varrás mennyit fog vizuálisan megjelenni az élen, és megtalálja a legszélesebb utat ezekhez a súlyokhoz. Ha ezt az utat varratként használják a hagyományos legrövidebb út helyett, akkor a rendszerük egy nehezen látható varratot talál, ahelyett, hogy a kép egyik részének minőségét egy másik rovására javítaná [5] .

A rácsrács két sarka közötti minimax feladat megoldásával megkereshetjük a két szaggatott vonal közötti gyenge Fréchet távolságot . Itt a rács minden csúcsa egy-egy szegmenspárt képvisel, mindegyik láncból egyet, az élsúly pedig azt a Fréchet-távolságot, amely az egyik szegmenspárból a másikba való eljutáshoz szükséges [15] .

Ha egy irányítatlan gráf minden élsúlya pozitív , akkor a pontpárok közötti minimális távolságok (a minimális utak maximális élsúlyai) egy ultrametrikus teret alkotnak . Ezzel szemben minden véges ultrametrikus tér minimax távolságokból alakul így [16] . A legkevesebb feszítőfából épített adatstruktúra lehetővé teszi, hogy a csúcspárok közötti minimális távolságot konstans időben lekérdezzük a legkevésbé gyakori őslekérdezések használatával egy derékszögű fában . A derékszögű fa gyökere a legkevésbé feszülő fa legnehezebb élét képviseli, a gyökér gyermekei pedig a legkevésbé feszülő fák részfáiból rekurzív módon összeállított derékszögű fák, amelyeket a legnehezebb él eltávolításával alakítottak ki. A Descartes-fa levelei a bemeneti gráf csúcsait képviselik, és a két csúcs közötti minimális távolság egyenlő a Descartes-fa csomópontjának súlyával, amely a legkevésbé közös ősük. Ha a legkevésbé feszülő fa éleit rendeztük, ez a derékszögű fa lineáris időben felépíthető [17] .

Irányított grafikonok

Irányított gráfokban a maximális feszítőfa megoldás nem használható. Ehelyett néhány különböző algoritmus ismert. Az a kérdés, hogy melyik algoritmust válasszuk, attól függ, hogy az útvonal kezdő- és végpontja rögzített-e, vagy egyszerre több kezdő- és végpontból kell utat keresni.

Minden pár

Az összes pár esetében a legszélesebb útprobléma Schulze módszerében alkalmazható a többoldalú választások győztesének meghatározására , amelyben a választók preferenciális szavazással értékelik a jelölteket . Schulze módszere egy teljes irányított gráfot konstruál , ahol a csúcsok jelölteket jelölnek, és bármely két csúcsot egy él köti össze. Minden él a győztestől a vesztes felé irányul két jelölt párharcában, és a győztes előnye a versenyben. A módszer ezután kiszámítja a legszélesebb utat az összes csúcspár között, és az a jelölt nyer, akinek a legszélesebb útvonala van az egyes ellenfelekkel [4] . Az ezzel a módszerrel végzett választási eredmények összhangban vannak a Condorcet-módszerrel  - az összes küzdelmet megnyerő jelölt automatikusan a választás győztese lesz, de a módszer lehetővé teszi a győztes kiválasztását, ha a Condorcet-módszer nem működik [18] . A Schulze-módszert több szervezet is alkalmazta, köztük a Wikimedia Foundation [19] .

Az összes csomópontpár legszélesebb útvonalának kiszámításához sűrű irányított gráfokban, például szavazó alkalmazásokban, az aszimptotikusan leggyorsabb megközelítés fut az időben , ahol a gyors mátrixszorzó algoritmusok metrikája . A legismertebb mátrixszorzó algoritmusok használatakor ezek az időkorlátok [20] -ba fordulnak . Azokat a korai algoritmusokat, amelyek gyors mátrixszorzást is alkalmaztak, hogy felgyorsítsák az összes pár legszélesebb útvonalának megtalálását, lásd Wassilewska, Williams és Yuster [21] , valamint a Wassilewska [22] 5. fejezetét . A Schulze-módszer referencia implementációja az egyszerűbb Floyd-Warshall algoritmus módosított változatát használja , amely időben fut [4] . Ritka gráfok esetén hatékonyabban használható a legszélesebb útvonalkereső algoritmus egyetlen forráshoz való többszöri alkalmazása.

Egy forrás

Ha az éleket súlyuk szerint rendezzük, akkor a Dijkstra-algoritmus egy módosított változata lineáris időben ki tudja számítani a szűk keresztmetszeteket a hozzárendelt kezdőcsúcs és a gráf összes többi csúcsa között. A Dijkstra algoritmus szokásos változatával való gyorsítás mögött meghúzódó kulcsötlet az, hogy a szűk keresztmetszetek sorozata az egyes csúcsokig abban a sorrendben, ahogy ezek a csúcsok megjelennek az algoritmusban, egy monoton részsorozat, amelyet az élsorozat súlyai ​​szerint rendeznek. Ezért a Dijkstra-algoritmus prioritási sora megvalósítható konténersorként , egy 1-től m -ig számozott tömbként (a gráf éleinek száma), ahol az i tömbcella olyan csúcsokat tartalmaz, amelyek "szűk keresztmetszete" egyenlő a súllyal. élének i pozíciójával rendezett sorrendben. Ez a módszer a legszélesebb útproblémát a rendezéssel azonos sebességgel oldja meg . Például, ha az élsúlyok egész számok, akkor egy m egész számból álló lista egész számok rendezésének kötött ideje is becslés lesz ehhez a problémához [13] .

Egyetlen forrás és egyetlen cél

Berman és Handler [23] azt javasolta, hogy a segélyautók és a mentők a minimax útvonalat használják, amikor visszatérnek a segélyhívó pontról a bázisra. Ezekben az esetekben a visszatérési idő kevésbé fontos, mint a válaszidő, ha újabb hívás történik, miközben a gép visszatérési folyamatban van. Minimax útvonal használata esetén, amelyben a súly a maximális utazási idő a szélétől a lehetséges hívás legtávolabbi pontjáig, lehetőség van az útvonal tervezésére úgy, hogy a lehető legnagyobb késleltetés legyen a hívás fogadása és az autó érkezése között. minimális [8] . Ulla, Lee és Hassoon [24] maximális útvonalakat használt a metabolikus hálózatok domináns reakcióinak láncolatának modellezésére . Modelljükben egy él súlya a metabolikus reakció szabad energiája, amelyet az él képvisel [6] .

A legszélesebb utak másik alkalmazása a Ford-Fulkerson algoritmusban merül fel a maximális áramlási probléma megoldására . Az áramlás fokozatos növelése egy maximális kapacitású útvonal mentén a maradék áramlási hálózatban a maximális áramlás meghatározásához szükséges lépések számának kis korlátját eredményezi. Itt az élkapacitásokat U -t meg nem haladó egész számoknak tekintjük . Ez az elemzés azonban nem a pontos maximális kapacitás megtalálásán múlik. Bármilyen út alkalmas, amelynek kapacitása állandó tényezővel eltér a maximumtól. Ezeket a közelítési ötleteket az Edmonds-Karp algoritmus legrövidebb útnövelési módszerével kombinálva egy maximális áramlási algoritmust kapunk futási idővel [7] .

Maximális kapacitású és minimax útvonalakat egyetlen forrással és egyetlen céllal nagyon hatékonyan lehet megtalálni még olyan számítási modellekben is, amelyek csak a bemeneti gráfélek súlyainak összehasonlítását teszik lehetővé, aritmetikát nem [13] [25] . Az algoritmus egy S élhalmazon működik, amelyről ismert, hogy az optimális útvonal szűk keresztmetszetének élét tartalmazza. Kezdetben S a gráf mind az m éléből áll. Az algoritmus minden iterációja során S -t megközelítőleg azonos méretű részhalmazok rendezett sorozatára osztják . A részhalmazok száma ebben a partícióban úgy van megválasztva, hogy az alhalmazok közötti összes partíciós pontot megtalálja, ha többszörös mediánt keres O ( m ) idő alatt . Az algoritmus ezután újraszámítja a gráf összes élének súlyát az élt tartalmazó részhalmaz indexével, és a módosított Dijkstra algoritmust használja a gráfon a frissített súlyokkal. Ezen számítások eredményei alapján lineáris időben ki lehet számítani, hogy melyik részhalmaz tartalmazza a szűk keresztmetszet élsúlyát. Az algoritmus ezután lecseréli S -t egy Si részhalmazra , amely tartalmazza a szűk keresztmetszet súlyát, és új iterációt indít ezzel az S halmazzal . Azon részhalmazok száma, amelyekbe S felosztható , minden lépéssel exponenciálisan nőhet, így az iterációk száma arányos a iterált logaritmusával , és a teljes végrehajtási idő [25] lesz . Egy olyan számítási modellben, ahol az egyes élek súlya egy gépi egész szám, az iteratív logaritmusok használata ebben az algoritmusban helyettesíthető a Hahn és Thorup [26] listás particionálási technikával , amely lehetővé teszi S kisebb részekre s S i particionálását . egy lépésben, ami lineáris közös időhatárt eredményez [27] .

Euklideszi pontok halmazai

A minimax útprobléma egy változatát vettük figyelembe az euklideszi síkon lévő pontok halmazára . Az irányítatlan gráfproblémához hasonlóan ez az euklideszi minimax útprobléma is hatékonyan megoldható egy euklideszi minimális feszítőfa megtalálásával  – a fában lévő bármely út egy minimax útvonal. A probléma azonban bonyolultabbá válik, ha azt akarjuk, hogy az út ne csak a felső hosszt minimalizálja, hanem az azonos felső hosszúságú utak között minimalizálja vagy durván minimalizálja az út teljes hosszát. A megoldást a geometriai feszítőfa [28] segítségével közelíthetjük meg .

A számelméletben a megoldatlan Gauss-árok probléma azt kérdezi, hogy a Gauss-prímekben lévő minimax útvonalak minimális hossza korlátos-e . Vagyis van-e olyan B konstans , hogy a Gauss-prímekkel definiált euklideszi pontok végtelen halmazában lévő bármely p és q pár esetén a Gauss-prímekben a p és q közötti minimax út legfeljebb B élhosszúságú legyen ? [29] .

Jegyzetek

  1. ↑ Pollack, 1960 , p. 733–736.
  2. ↑ Shacham, 1992 , p. 1217–1221.
  3. ↑ Wang, Crowcroft, 1995 , p. 2129–2133.
  4. ↑ 1 2 3 Schulze, 2011 , p. 267–303.
  5. ↑ 1 2 Fernandez, Garfinkel, Arbiol, 1998 , p. 293–304.
  6. ↑ 1 2 Ullah, Lee, Hassoun, 2009 , p. 144–150.
  7. ↑ 1 2 Ahuja, Magnanti és Orlin, 1993 , p. 210–212.
  8. ↑ 1 2 Berman, Handler, 1987 , p. 115–122.
  9. ↑ Hu, 1961 , p. 898–900.
  10. ↑ 12 Punnen , 1991 , p. 402–404.
  11. ↑ Malpani, Chen, 2002 , p. 175–180.
  12. ↑ Camerini, 1978 , p. 10–14.
  13. ↑ 1 2 3 Kaibel, Peinhardt, 2006 .
  14. ↑ Fernandez, Garfinkel, Arbiol, 1998 .
  15. ↑ Alt, Godau, 1995 , p. 75–91.
  16. ↑ Leclerc, 1981 , p. 5–37, 127.
  17. ↑ Demaine, Landau, Weimann, 2009 , p. 341–353.
  18. ↑ Pontosabban, az egyetlen lehetőség, ahol a Schulze-féle módszer kudarcot vall, az, ha két jelöltnek azonos szélességű útja van egymáshoz.
  19. ↑ Lásd: Jesse Plamondon-Willard, Testületi választás a preferenciális szavazáshoz , 2008. május; Mark Ryan, 2008. évi Wikimédia-testületi választási eredmények , 2008. június; 2008-as testületi választások , 2008. június; és 2009-es elnökségi választások , 2009. augusztus.
  20. ↑ Duan, Pettie, 2009 , p. 384–391.
  21. ↑ Vassilevska, Williams, Yuster, 2007 , p. 585–589.
  22. ↑ Vasszilevska, 2008 .
  23. ↑ Berman, Handler, 1987 .
  24. ↑ Ullah, Lee, Hassoun, 2009 .
  25. ↑ 1 2 Gabow, Tarjan, 1988 , p. 411–417.
  26. ↑ Han, Thorup, 2002 .
  27. ↑ Han, Thorup, 2002 , p. 135–144.
  28. ↑ Bose, Maheshwari, Narasimhan, Smid, Zeh, 2004 , p. 233–249.
  29. ↑ Gethner, Wagon, Wick, 1998 , p. 327–337.

Irodalom