Legrövidebb út probléma

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez
A legrövidebb út (A, C, E, D, F) az A és F csúcsok között a súlyozott irányított gráfban

A gráfelméletben a legrövidebb út probléma olyan probléma, hogy egy gráfban két csúcs (vagy csomópont) között olyan utat találjunk, amely minimálisra csökkenti annak alkotó éleinek számát.

A legrövidebb út megtalálásának problémáját az ágrajz két pontja között úgy lehet modellezni, mint a legrövidebb út problémájának különleges esete, ahol a csúcsok kereszteződéseknek, míg az élek útszakaszoknak felelnek meg, mindegyiket a szegmens hosszának függvényében.

Meghatározás[szerkesztés]

Gráfok esetében a legrövidebb út problémát meg lehet határozni irányítatlanként, irányítottként, vagy ezek keverékeként (vegyes gráf). Itt a nem irányított gráfok határozzuk meg; irányított gráfok esetében az elérési út meghatározása megköveteli, hogy az egymást követő csúcsokat megfelelő irányított élek kössék össze.

Két csúcs szomszédos, ha mindkettő közös élhez vezet. A nem irányított gráfban lévő útvonal csúcsok sorozata ahol szomszédos +1-gyel, Ilyen utat hosszúságú útként írunk le, ahol aránylik a -hez. (A változó, számozása itt a sorrendben levő helyzetükre vonatkozik és nem szükséges, hogy kapcsolódjon a csúcsok kanonikus jelöléséhez).

Legyen a szélső eseménye a és -nek. Adott egy valós értékű számfüggvény , és egy irányítatlan (egyszerű) gráfot , a legrövidebb út és között (ahol és ) ahol az összes lehetséges összeget Amikor gráf minden éle a felírható a , függvénnyel, ez egyenértékű azzal, hogy megtaláljuk a legkevesebb élű utat.

A problémát néha az egypáros legrövidebb út problémának is nevezik, hogy megkülönböztessék az alábbi variációktól:

  • Az egy forrásból származó legrövidebb út probléma, amelyben meg kell találnunk a legrövidebb útvonalakat a v forráscsúcstól a grafikon összes többi csúcsáig.
  • Az egycélú legrövidebb út probléma, amelyben a legrövidebb útvonalakat kell keresnünk az irányított gráfban lévő összes csúcsról az egyetlen célpont v csúcsra. Ez redukálható az egy forrásból származó legrövidebb út problémára az ívek megfordításával az irányított gráfban.
  • Az összes pár legrövidebb út problémája', amelyben a gráfok minden v, v csúcsa között meg kell találni a legrövidebb útvonalakat.

Ezeknek az általánosításoknak jelentősen hatékonyabb algoritmusaik vannak, mint az egypáros legrövidebb út algoritmus futtatásának egyszerűsített megközelítésén az összes releváns csúcspáron.

Algoritmusok[szerkesztés]

A probléma megoldásának legfontosabb algoritmusai:

  • Dijkstra algoritmusa az egy forrásból származó legrövidebb út problémát nem negatív él számokkal oldja meg.
  • A Bellman–Ford algoritmus az egy forrásból származó problémát úgy oldja meg, hogy az él számok negatívak is lehetnek,
  • A* keresési algoritmus az egypáros legrövidebb utat oldja meg heurisztikák felhasználásával, hogy megkíséreljék felgyorsítani a keresést.
  • A Floyd–Warshall algoritmus az összes pár legrövidebb út problémát oldja meg.
  • Johnson algoritmusa az összes pár legrövidebb útvonalakat oldja meg, amely gyorsabb lehet, mint a Floyd–Warshall-algoritmus ritka gráfok esetén,
  • A Viterbi algoritmus a legrövidebb sztochasztikus út problémát úgy oldja meg, hogy további valószínűségi számokat is figyelembe vesz mindegyik csomóponton.

Egy forrásból származó legrövidebb utak[szerkesztés]

Irányítatlan grafikonok[szerkesztés]

súlyok Az idő összetettsége Szerző
+ O (V 2) Dijkstra 1959
+ O ((E   +   V)   log   V) Johnson 1977 (bináris halom)
+ O (E   +   V   log   V) Fredman & Tarjan 1984 (Fibonacci-halom)
O (E) Thorup 1999 (állandó idő szorzásra van szükség).

Súlyozatlan gráfok[szerkesztés]

Algoritmus Az idő összetettsége Szerző
Szélességi keresés O (E   +   V)

Irányított körmentes gráfok (DAG-k)[szerkesztés]

A topológiai sorrend használó algoritmus meg tudja oldani az egy forrásból származó legrövidebb út problémát Θ(E + V) lineáris időben, súlyozott DAG-kban.

Irányított grafikonok nem negatív súlyokkal[szerkesztés]

Az alábbi táblázat Schrijver (2004) kiadványából származik, néhány javítással és kiegészítéssel. Egy zöld háttér az aszimptotikusan legjobban megkötött táblát jelzi; L az összes él közötti maximális hosszúság (vagy tömeg), egész éleket figyelembe véve.

Algoritmus Az idő összetettsége Szerző
O (V 2 EL) Ford 1956
Bellman–Ford-algoritmus O (VE) Shimbel 1955, Bellman 1958, Moore 1959
O (V 2   log   V) Dantzig 1960
Dijkstra algoritmusa listával O (V 2) Leyzorek et al. 1957, Dijkstra 1959, Minty (lásd Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dijkstra algoritmusa bináris halommal O ((E   +   V)   log   V) Johnson 1977
. . . . . . . . .
Dijkstra-algoritmus Fibonacci-halommal O (E   +   V   log   V) Fredman & Tarjan 1984, Fredman & Tarjan 1987
O (E   log   log   L) Johnson 1981, Karlsson & Poblete 1983
Gabow algoritmusa O (E   napló E / V   L) Gabow 1983, Gabow 1985
O (E   +   V log L) Ahuja et al. 1990
Thorup O (E   +   V   log   log   V) Thorup 2004

Irányított grafikonok tetszőleges súlyokkal, negatív ciklusok nélkül[szerkesztés]

Algoritmus Az idő összetettsége Szerző
O (V 2 EL) Ford 1956
Bellman–Ford-algoritmus O (VE) Shimbel 1955, Bellman 1958, Moore 1959

Sík irányított grafikonok tetszőleges súlyokkal[szerkesztés]

Összes pár legrövidebb utak[szerkesztés]

Az összes pár legrövidebb útja a grafikon v, v ' csúcsainak párja között találja meg a legrövidebb utat. Shimbel vezette be az összes pár legrövidebb út problémát a súlyozatlan irányított gráfok esetében, aki megfigyelte, hogy mindez megoldható a mátrixszorzók lineáris számával, amely összesen O időt vesz igénybe (V 4).

Irányítatlan grafikon[szerkesztés]

súlyok Az idő összetettsége Algoritmus
+ O(V3) Floyd – Warshall algoritmus
Seidel algoritmusa (várható futási idő).
Williams 2014
+ O(EV log α(E,V)) Pettie & Ramachandran 2002
O(EV) Thorup 1999 minden csúcsra alkalmazva (állandó idő szorzást igényel).

Irányított grafikon[szerkesztés]

súlyok Az idő összetettsége Algoritmus
ℝ (nincs negatív ciklus) O(V3) Floyd – Warshall algoritmus
Williams 2014
ℝ (nincs negatív ciklus) O(EV + V2 log V) Johnson-Dijkstra
ℝ (nincs negatív ciklus) O(EV + V2 log log V) Pettie 2004
O(EV + V2 log log V) Hagerup 2000

Alkalmazások[szerkesztés]

A legrövidebb algoritmusokat az irányok automatikus keresésére alkalmazzák két fizikailag meghatározható pont között, például vezetési útmutatások olyan webes térképezési webhelyeken, mint a MapQuest vagy a Google Maps. Ennek alkalmazásához gyors speciális algoritmusok állnak rendelkezésre.[1]

Ha egy nem meghatározott elvonatkoztatott gépet gráfként ábrázolunk, ahol a csúcsok az állapotokat, és az élek a lehetséges átmeneteket jelölik, akkor a legrövidebb út algoritmust lehet felhasználni az optimális választási szekvencia megtalálásához, hogy elérjünk egy bizonyos eléréséhez, vagy alacsonyabb határok meghatározásához a szükséges idő alatt elérjünk egy adott állapotot. Például, ha a csúcsok egy puzzle állapotát reprezentálják, mint például a Rubik-kocka, és minden irányított él egyetlen mozdulatnak vagy fordulásnak felel meg, akkor a legrövidebb út algoritmusok használhatók olyan megoldás megtalálására, amely a lehető legkevesebb mozdulatok számát használja.

A hálózati vagy távközlési gondolkodásmód esetén, a legrövidebb út problémát néha a min-delay útvonal problémának nevezzük, és általában szélesebb út problémájához kötődik. Például az algoritmus a legrövidebb (min-delay) legszélesebb utat, vagy a legszélesebb legrövidebb (min-delay) utat keresheti.

Egy könnyebb alkalmazása a „hat fokos elválasztás” játéka, amely egy gráfon belüli legrövidebb utat úgy próbálja megtalálni, mint ahogy a filmsztárok megjelennek ugyanazon filmben.

Gyakran az operatív kutatások során is alkalmazzák a fentieket, amely magukban foglalják az üzem és a létesítmény elrendezését, a robotikát, a szállítást és a VLSI tervezését.[2]

Utcatérképek[szerkesztés]

Az utcatérképek pozitív súlyú gráfoknak tekinthetők. A csomópontok az útkereszteződéseket ábrázolják, és a gráfok minden széle a két kereszteződés közötti útszakaszhoz van társítva. Az élek súlya megfelelhet a hozzá tartozó útszakasz hosszának, a szegmens áthaladásához szükséges időnek vagy a szakasz áthaladásának költségeinek. Irányított élekkel egyirányú utcák is modellezhetőek. Az ilyen grafikonok abban az értelemben különlegesek, hogy egyes élek fontosabbak, mint mások a távolsági utazások során (pl. autópályák). Ez a tulajdonság az autópálya-dimenzió fogalmával lett formalizálva.[3] Nagyon sok algoritmus használja ki ezt a tulajdonságot, ezért sokkal gyorsabban képes kiszámítani a legrövidebb utat, mint az általános gráfokon lehetséges lenne.

Ezek az algoritmusok két fázisban működnek. Az első szakaszban a gráfot előzetesen feldolgozzák a forrás vagy a célcsomópont ismerete nélkül. A második fázis a lekérdezés fázisa. Ebben a fázisban a forrás és a célcsomópont ismert. Az ötlet az, hogy az ágrajz statikus, tehát az előzetes feldolgozási szakasz egyszer elvégezhető, és ugyanazon ágrajz nagyszámú lekérdezéséhez felhasználható.

A leggyorsabban ismert lekérdezési idővel rendelkező algoritmust hub-címkézésnek nevezzük, és képes mikrosekundum töredéke alatt kiszámítani a legrövidebb utat Európa vagy az Egyesült Államok közúthálózatán.[4] Egyéb alkalmazott technikák a következők:

  • ALT (A* keresés, tereptárgyak és háromszög-egyenlőtlenség)
  •  Ívzászlók
  • Összehúzódási hierarchiák
  • Tranzitcsomópont útválasztása
  • Reach-alapú metszés
  • Címkézés
  • Hub-címkék

Kapcsolódó problémák[szerkesztés]

A számítógépes geometriában található legrövidebb út problémájához, lásd euklideszi legrövidebb utat.

Az utazó eladó probléma az a probléma, hogy megtalálják a legrövidebb utat, amely pontosan egyszer halad át minden csúcson, és visszatér az elejére. A legrövidebb út problémájával ellentétben, amelyet polinomális időben grafikonokban lehet megoldani negatív ciklusok nélkül, az utazó eladó probléma NP-teljes, és mint ilyen, úgy gondolják, hogy a nagy adatsorok esetében nem oldható meg hatékonyan (lásd P = NP probléma)). Az a probléma is, hogy a leghosszabb utat találjuk meg egy gráfban, az NP-teljes.

A kanadai utazó probléma és a sztochasztikus legrövidebb út probléma általánosítás, ahol vagy a gráf nem teljesen ismert a mozgó/utazó számára, az idő múlásával változik, vagy ha a műveletek (áthaladások) valószínűek.

A legrövidebb, többször leválasztott útvonal [5] a primitív úthálózat reprezentációja a Reptation elmélet keretein belül.

A legszélesebb út problémája olyan utat keres, amelyben az élek minimális címkéje a lehető legnagyobb legyen.

Stratégiai legrövidebb utak[szerkesztés]

A gráfok élei néha személyiségekkel rendelkeznek: mindegyik élnek megvan a maga saját önző érdeke. Példa erre a kommunikációs hálózat, amelyben minden él egy számítógép, amely valószínűleg egy másik személyhez tartozik. A különböző számítógépek átviteli sebessége eltérő, tehát a hálózat minden élének numerikus súlya megegyezik az üzenet továbbításához szükséges milliszekundumok számával. Célunk az, hogy a lehető legrövidebb időn belül üzenetet küldjünk a hálózat két pontja között. Ha tudjuk az egyes számítógépek átviteli idejét (az egyes élek súlyát), akkor használhatunk egy szabványos legrövidebb út algoritmust. Ha nem tudjuk az átviteli időket, akkor minden számítógépet fel kell kérnünk, hogy mondja meg az átviteli időt. Azonban a számítógépek önzőek lehetnek: egy számítógép megmondhatja nekünk, hogy az átviteli ideje nagyon hosszú, így nem zavarhatjuk üzeneteinkkel. A probléma egyik lehetséges megoldása a VCG-mechanizmus egy változatának használata, amely ösztönzi a számítógépeket valódi súlyuk feltárására.

Lineáris programozási megfogalmazás[szerkesztés]

Létezik egy természetes lineáris programozási formula a legrövidebb út problémájához, az alábbiak szerint. Nagyon egyszerű, összehasonlítva a lineáris programok diszkrét optimalizálásban alkalmazott legtöbb egyéb felhasználásával, azonban szemlélteti más fogalmakhoz való kapcsolódást is.

Ha egy irányított gráfot (V, A) adunk az s forráscsomóponttal, t célcsomóponttal és w ij költséggel minden egyes él (i, j) számára A-ban, akkor vegyük figyelembe a programot az x ij változókkal, akkor

minimalizálása feltéve és minden i,

Az intuíció emögött, hogy a változó indikátora az élnek (i, j) : 1, amikor van, és 0, ha nem. Szeretnénk a lehető legkisebb súlyú élek halmazát kiválasztani, azzal a megkötéssel, hogy ez a halmaz útvonalat képez s- től t-ig (egyenlőségi kényszer képviseli: minden csúcs esetében s és t kivételével a bejövő és kimenő élek száma, amelyek ugyanannak az útvonalnaka részei. (azaz hogy legyen egy út s-től t-ig).

Ennek az LP-nek az a különleges tulajdonsága, hogy szerves; Pontosabban, minden alapvető optimális megoldásnak (ha létezik ilyen) az összes változó értéke 0 vagy 1, és az élek halmaza, amelynek változói egyenlőek 1 formában egy s - t dipath. Továbbiakért lásd Ahuja et al.[6] bizonyítékra, bár e megközelítés eredete a 20. század közepére nyúlik vissza.

A lineáris program kettős értéke:

maximalizálja y t - y s alá az összes ij, y J - y iw ij

és a megvalósítható párok megfelelnek az A* algoritmus következetes heurisztikájának a legrövidebb utakon történő fogalmának. Bármely megvalósítható pár esetén a csökkentett költségek nem negatívak, és az A * alapvetően Dijkstra-algoritmusát használja ezekre a csökkentett költségekre.

Általános algebrai keretek a félbeszakításokhoz: az algebrai út probléma[szerkesztés]

Számos probléma a lehető legrövidebb út formáját öltheti néhány, az adott út mentén történő, helyettesített, és a minimumot figyelembe vevő, megfelelően helyettesített fogalom számára. Ezek általános megközelítése a két művelet félbeszakításnak tekintése. Az összetett szorzás az út mentén, míg az összeadás az utak között történik. Ezt az általános keretet algebrai út problémának nevezik. [7]

A klasszikus legrövidebb utat alkalmazó algoritmusok (és az újak) nagy része lineáris rendszerek megoldására alakítható az algebrai struktúrák felett.[8]


Az utóbbi időben ezek megoldására még általánosabb keretet dolgoztak ki az értékelési algebrák cím alatt.[9]

Rövidebb út a sztochasztikus időfüggő hálózatokban[szerkesztés]

A valós helyzetekben a szállítási hálózat általában sztochasztikus és időfüggő. Valójában a napi összeköttetéssel utazó eltérő utazási időt tapasztalhat ezen a linken, nemcsak az utazási igény ingadozása miatt (a kiindulási és a rendeltetési hely mátrixa), hanem az olyan események miatt, mint például a munkakörzetek, a rossz időjárási körülmények, a balesetek és a jármű meghibásodása. Ennek eredményeként egy sztochasztikus időfüggő (STD) hálózat a valós ágrajz reálisabb ábrázolása, mint a determinisztikus. [10] [11]

Az elmúlt évtized folyamán bekövetkezett jelentős előrelépések ellenére továbbra is ellentmondásos kérdés, hogyan kell meghatározni és azonosítani az optimális utat a sztochasztikus ágrajzokban. Más szavakkal, nincs egyértelmű meghatározás az optimális út számára a bizonytalanság miatt. Erre a kérdésre az egyik lehetséges és általános válasz az, hogy keresni kell egy utat a minimálisan várható utazási idővel. Ennek a megközelítésnek az a legnagyobb előnye, hogy a determinisztikus hálózatokhoz bevezetett hatékony legrövidebb út algoritmusok könnyen felhasználhatók az elérési út azonosításához a sztochasztikus ágrajzban várható minimális utazási idővel. Az e megközelítés által azonosított eredményes optimális út azonban nem biztos, hogy megbízható, mivel ez a megközelítés nem foglalkozik az utazási idő változásával. Ennek a kérdésnek a kezelése érdekében egyes kutatók a várható érték helyett az utazási idő eloszlását használják, így különféle optimalizálási módszerekkel - például a dinamikus programozás és a Dijkstra algoritmusa[12] alapján - megtalálják a teljes utazási idő valószínűségi eloszlását. Ezek a módszerek sztochasztikus optimalizálást, különösen sztochasztikus dinamikus programozást alkalmaznak, hogy megtalálják a valószínűsíthető ívhosszúságú hálózatokban a legrövidebb utat.[13] Az utazási idő megbízhatóságának fogalmát felváltva használják az utazási idő változtathatóságával a szállítási kutatási irodalomban, tehát általánosságban elmondható, hogy minél nagyobb az utazási idő variabilitása, annál alacsonyabb a megbízhatósága és fordítva.

Az utazási idő megbízhatóságának pontosabb elszámolása érdekében két általános alternatív meghatározást javasoltak az optimális úthoz bizonytalanság mellett. Néhányan bevezették a legmegbízhatóbb út fogalmát, azzal a céllal, hogy maximalizálják annak valószínűségét, hogy időben megérkezzenek, vagy egy adott utazási időkorlátnál korábban érkezzenek. Mások alternatívaként egy α-megbízható út fogalmát terjesztették elő, mellyel a lehető legkisebbre akarták csökkenti az előre megadott időben történő érkezés valószínűségének biztosításához szükséges utazási idő költségvetését.

Jegyzetek[szerkesztés]

  1. Sanders (2009. március 23.). „Fast route planning”, Kiadó: Google Tech Talk.  
  2. Chen (1996. december 1.). „Developing algorithms and software for geometric path planning problems”. ACM Computing Surveys 28 (4es). DOI:10.1145/242224.242246.  
  3. Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms". ACM-SIAM Symposium on Discrete Algorithms, pages 782–793, 2010.
  4. Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. research.microsoft.com/pubs/142356/HL-TR.pdf "A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks". Symposium on Experimental Algorithms, pages 230–241, 2011.
  5. Kroger, Martin (2005). „Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems”. Computer Physics Communications 168 (3), 209–232. o. DOI:10.1016/j.cpc.2005.01.020.  
  6. Ahuja, Ravindra K.. Network Flows: Theory, Algorithms and Applications. Prentice Hall (1993). ISBN 978-0-13-617549-0 
  7. Baras, John. Path Problems in Networks. Morgan & Claypool Publishers, 9–. o. (2010. április 4.). ISBN 978-1-59829-924-3 
  8. Graphs, Dioids and Semirings: New Models and Algorithms. Springer Science & Business Media (2008). ISBN 978-0-387-75450-5 
  9. Gondran, Michel. Graphs, Dioids and Semirings: New Models and Algorithms. Springer Science & Business Media (2008). ISBN 978-0-387-75450-5 
  10. Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.
  11. Rajabi-Bahaabadi (2015. november 1.). „Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm”. Expert Systems with Applications 42 (12), 5056–5064. o. DOI:10.1016/j.eswa.2015.02.046.  
  12. (2014. november 1.) „Finding shortest path in a combined exponential – gamma probability distribution arc length”. International Journal of Operational Research 21 (1), 25–37. o. DOI:10.1504/IJOR.2014.064020.  
  13. (2014. november 1.) „Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length”. International Journal of Operational Research 21 (2), 143–154. o. DOI:10.1504/IJOR.2014.064541.  

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a Shortest path problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.

Kapcsolódó szócikkek[szerkesztés]

További irodalom[szerkesztés]

  • (1998) „Fully dynamic output bounded single source shortest path problem”.. 
  • Dreyfus, S. E. (October 1967). An Appraisal of Some Shortest Path Algorithms (PDF) (Report). Project Rand. United States Air Force. RM-5433-PR. DTIC AD-661265.