Legrövidebb út probléma

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. augusztus 20-án felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A legrövidebb út probléma a legrövidebb út (lánc) megtalálása egy gráf két pontja (csúcsa) között , amelyben az utat alkotó élek súlyának összege minimális.

A legrövidebb út probléma a gráfelmélet egyik legfontosabb klasszikus problémája . Ma már számos algoritmus ismert a megoldására .

Ennek a problémának más neve is van: a minimális elérési út probléma, vagy egy elavult verzióban a postakocsi probléma.

Ennek a feladatnak a jelentőségét a különféle gyakorlati alkalmazásai határozzák meg . Például a GPS-navigátorok keresik a legrövidebb utat egy kiindulási pont és egy úti cél között. A kereszteződések csúcsokként működnek, az utak pedig a köztük lévő élek. Ha a kereszteződések közötti utak hosszának összege minimális, akkor a talált út a legrövidebb.

Definíció

A gráf legrövidebb útjának megtalálásának problémája definiálható irányítatlan , irányított vagy vegyes gráf esetén. Ezután a problémafelvetést a legegyszerűbb formában vizsgáljuk meg irányítatlan gráf esetén. Vegyes és irányított gráf esetén az élek irányát is figyelembe kell venni.

A gráf csúcsok és élek (csúcspárok) nem üres halmazának gyűjteménye. A gráf két csúcsa szomszédos, ha közös élük van. Az út az irányítatlan gráfban olyan csúcsok sorozata , amelyek szomszédosak a for -ral . Az ilyen utat a csúcstól a pontig terjedő hosszúságú útnak nevezzük (az út csúcsának számát jelzi, és semmi köze a gráf csúcsainak számozásához). $P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V$ $v_{i}$ $v_{{i+1}}$ $1\leq i<n$ $P$ $n$ $v_{1}$ $v_{n}$ $én$

Legyen két csúcsot összekötő él: és . Adott egy súlyfüggvény , amely leképezi az éleket a súlyukra, amelyek értékei valós számokként vannak kifejezve, és egy irányítatlan gráf . Ekkor a legrövidebb út a csúcstól a csúcsig az az út lesz (ahol és ), amelyen az összeg minimális értéke van . $e_{{i,j}}$ $v_{i}$ $v_{j}$ $f:E\jobbra nyíl {\mathbb {R}}$ $G$ $v$ $v'$ $P=(v_{1},v_{2},\ldots ,v_{n})$ $v_{1}=v$ $v_{n}=v'$ $\sum _{{i=1}}^{{n-1}}f(e_{{i,i+1}}).$

A legrövidebb út problémájának többféle megfogalmazása létezik:

Az adott célhoz vezető legrövidebb út problémája. Meg kell találni a legrövidebb utat egy adott t célcsúcshoz, amely a gráf minden csúcsánál kezdődik (kivéve t). A gráfhoz tartozó egyes élek irányának megváltoztatásával ez a probléma egyetlen kezdeti csúcs problémájára redukálható (amelyben az adott csúcstól az összes többihez vezető legrövidebb út keresése történik).
Egy adott csúcspár közötti legrövidebb út problémája. Meg kell találni a legrövidebb utat egy adott u csúcstól egy adott v csúcsig.
Az összes csúcspár közötti legrövidebb út problémája. Minden u csúcstól minden v csúcsig meg kell találni a legrövidebb utat. Ez a probléma megoldható egy olyan algoritmussal is, amely egy forráscsúcs problémájának megoldására szolgál, de általában gyorsabban megoldódik.

A probléma különböző megfogalmazásában az élhossz szerepét nemcsak maguk a hosszúságok játszhatják, hanem az idő, a költség, a ráfordítások, a ráfordított erőforrások mennyisége (anyag, anyagi, üzemanyag és energia stb.), ill. az egyes élek áthaladásához kapcsolódó egyéb jellemzők. Így a probléma nagyon sok területen talál gyakorlati alkalmazást (számítástechnika, közgazdaságtan, földrajz stb.).

A legrövidebb útprobléma további megszorítások hatálya alá tartozik

A legrövidebb út problémájával nagyon gyakran találkozunk olyan helyzetben, amikor további megszorításokkal kell számolni. Jelenlétük jelentősen növelheti a feladat összetettségét [1] . Példák ilyen feladatokra:

Egy adott csúcshalmazon áthaladó legrövidebb út. Két megkötést lehet figyelembe venni: a legrövidebb útnak át kell haladnia a kiválasztott csúcshalmazon, és a legrövidebb útnak a lehető legkevesebb ki nem választott csúcsot kell tartalmaznia. Ezek közül az első jól ismert az operációkutatáselméletben [2] .
Egy irányított gráf csúcsainak minimális lefedettsége útvonalakkal. A keresést a gráfot lefedő minimális számú útvonalra, nevezetesen az összes st út egy részhalmazára hajtjuk végre, úgy, hogy egy irányított gráf minden csúcsa legalább egy ilyen útvonalhoz tartozik [3] .
A szükséges utak problémája. Meg kell találni egy olyan halmazt, amely minimális kardinalitású utakból áll , hogy bármelyikhez legyen egy út , amely lefedi. néhány útvonal halmaza egy irányított G gráfban [4] . $P={p_{1},\pontok,p_{m}}$ $t_{i}\in R$ $p_{j}\in P$ $R={t_{1},\pontok ,t_{k}}$
Egy irányított gráf íveinek minimális lefedettsége pályákkal. A probléma az, hogy meg kell találni az összes útvonal minimális részhalmazát az utak száma alapján úgy, hogy minden ív legalább egy ilyen útvonalhoz tartozzon. Ebben az esetben lehetséges egy további követelmény, hogy minden út egy csúcsból származzon [5] .

Algoritmusok

Tekintettel arra, hogy ennek a problémának számos különböző megfogalmazása létezik, vannak a legnépszerűbb algoritmusok a grafikonon a legrövidebb út megtalálásának problémájának megoldására:

Dijkstra algoritmusa megtalálja a legrövidebb utat a gráf egyik csúcsától az összes többi csúcsig. Az algoritmus csak negatív súlyú élek nélküli gráfoknál működik [6] .
A Bellman-Ford algoritmus megkeresi a legrövidebb utat az egyik gráfcsúcstól az összes többiig egy súlyozott gráfban. Az élsúlyok negatívak is lehetnek.
Az A* keresési algoritmus a legolcsóbb útvonalat találja meg az egyik csúcstól (kezdettől) a másikig (cél, végpont) a gráf első legjobb egyezésű keresési algoritmusával.
A Floyd-Warshall algoritmus megtalálja a legrövidebb utat egy súlyozott irányított gráf összes csúcsa között [6] .
A Johnson-algoritmus megtalálja a legrövidebb utat egy súlyozott irányított gráf összes csúcspárja között.
A Lee-algoritmus (hullám-algoritmus) a szélesség-első keresési módszeren alapul. Megkeresi a minimális számú köztes csúcsot (éleket) tartalmazó gráf s és t csúcsai közötti utat (s nem azonos t-vel). A fő alkalmazás az elektromos csatlakozások nyomon követése mikroáramkörök chipeken és nyomtatott áramkörökön . Arra is használják, hogy megtalálják a legrövidebb távolságot a térképen stratégiai játékokban.
A legrövidebb út megkeresése a Kildal-algoritmus alapján [7] .

A munka (Cherkassky et al., 1993) [8] számos további algoritmust mutat be ennek a problémának a megoldására.

Az egyik csúcstól az összes többihez vezető legrövidebb út megtalálásának problémája

A feladatnak ebben a megfogalmazásában meg kell keresni a legrövidebb utat a v csúcstól a gráf összes többi csúcsáig.

Súlyozatlan irányított gráf

Algoritmus	Bonyolultság	Szerző
Szélesség első keresés	O ( V+E )

Ez egy hiányos lista , és előfordulhat, hogy soha nem felel meg a teljesség bizonyos követelményeinek. Jó hírű forrásokból kiegészítheti .

Irányított gráf nem negatív súlyokkal

Algoritmus	Bonyolultság	Szerző
-	O ( V 2 EL )	Ford 1956
Bellman-Ford algoritmus	O ( VE )	Bellman 1958 [9] , Moore 1957 [10]
-	O ( V 2 log V )	Danzig 1958, Danzig 1960, Minty (vö. Pollack & Wiebenson 1960), Whiting és Hillier 1960
Dijkstra lista algoritmusa .	O ( V2 ) _	Leyzorek et al. 1957 [11] , Dijkstra 1959 [12]
Dijkstra algoritmusa módosított bináris kupacokkal	O ( ( E + V ) log V )	-
. . .	. . .	. . .
Dijkstra algoritmusa Fibonacci Heap használatával	O ( E + V log V )	Fridman és Tarjan 1984 [13] , Fridman és Tarjan 1987 [14]
-	O ( E log log L )	Johnson 1982, Karlsson & Poblete 1983
Gabov algoritmusa	O ( E log E / V L )	Gabow 1983, Gabow 1985
-	O ( E + V √ log L )	Ahuja et al. 1990

Ez egy hiányos lista , és előfordulhat, hogy soha nem felel meg a teljesség bizonyos követelményeinek. Jó hírű forrásokból kiegészítheti .

Irányított gráf tetszőleges súllyal

Algoritmus	Bonyolultság	Szerző
Bellman-Ford algoritmus	O ( VE )	Bellman [9] , Moore [10]

Ez egy hiányos lista , és előfordulhat, hogy soha nem felel meg a teljesség bizonyos követelményeinek. Jó hírű forrásokból kiegészítheti .

Az összes csúcspár közötti legrövidebb út problémája

A súlyozatlan irányított gráf összes csúcspárja közötti legrövidebb útproblémát Simbel vetette fel 1953-ban [15] , aki úgy találta, hogy ez lineáris számú mátrixmanipulációval (szorzással) megoldható. Egy ilyen algoritmus bonyolultsága O ( V 4 ).

Vannak más gyorsabb algoritmusok is a probléma megoldására, mint például a Floyd-Warshall algoritmus O komplexitású ( V 3 ) és a Johnson algoritmus (amely a Bellman-Ford és a Dijkstra algoritmusok kombinációja) O komplexitású ( VE + V 2 log V ) .

Alkalmazás

A gráfon a legrövidebb út megtalálásának problémája többféleképpen értelmezhető és különböző területeken alkalmazható. A következő példák a probléma különféle alkalmazási területeire mutatnak be. Az operációkutatással foglalkozó tudományágban további alkalmazásokat is vizsgálnak [16] .

Térképszolgáltatások

A grafikon legrövidebb útvonalának algoritmusait arra használják, hogy megtalálják a fizikai objektumok közötti utakat olyan térképszolgáltatásokon, mint a Google Térkép vagy az OpenStreetMap . A Google oktatóvideójában különféle hatékony algoritmusokat ismerhet meg, amelyeket ezen a területen használnak [17] .

Nem determinisztikus gép

Ha egy nem-determinisztikus absztrakt gépet gráfként képzelünk el, ahol a csúcsok állapotokat írnak le, az élek pedig a lehetséges átmeneteket határozzák meg, akkor a legrövidebb út algoritmusai segítségével megtalálhatjuk az optimális megoldási sorozatot a fő cél eléréséhez. Például, ha a csúcsok egy Rubik-kocka állapotai , és az él egyetlen műveletet jelent a kockán, akkor az algoritmus alkalmazható minimális mozdulatszámú megoldás megtalálására.

Úthálózatok

A legrövidebb út grafikonon való megtalálásának problémáját széles körben használják az úthálózat legrövidebb távolságának meghatározására.

Az úthálózat pozitív súlyokkal ábrázolható grafikonként. A csúcsok útkereszteződések , a szélek pedig az őket összekötő utak. Az élsúlyok megfelelhetnek egy adott szakasz hosszának, a leküzdéséhez szükséges időnek vagy a végighaladási költségnek. Az orientált élek használhatók az egyirányú utcák ábrázolására. Egy ilyen oszlopban megadhat egy olyan jellemzőt, amely azt jelzi, hogy egyes utak fontosabbak, mint mások a hosszú utakhoz (például autópályák). Az autópályák koncepciójában (eszmében) formalizálódott [18] .

A megközelítés megvalósításához, ahol egyes utak fontosabbak, mint mások, számos algoritmus létezik. Sokkal gyorsabban oldják meg a legrövidebb út megtalálásának problémáját, mint a hasonlók a szokásos grafikonokon. Az ilyen algoritmusok két szakaszból állnak:

előfeldolgozási szakasz. A gráf előfeldolgozása a kezdeti és a végső csúcsok figyelembevétele nélkül történik (ez akár több napig is eltarthat, ha valós adatokkal dolgozik). Általában egyszer hajtják végre, majd a kapott adatokat használják fel.
kérés szakaszában. A legrövidebb út kérése és keresése történik, miközben a kezdeti és a végső csúcs ismert.

A leggyorsabb algoritmus a mikroszekundum töredéke alatt képes megoldani ezt a problémát Európa vagy Amerika útjain [19] .

Egyéb megközelítések (technikák), amelyeket ezen a területen alkalmaznak:

ALT
Íves zászlók
Összehúzódási hierarchiák
Tömegközlekedési csomópont útvonaltervezés
Elérés alapú metszés
Címkézés

Hasonló problémák

Vannak olyan problémák, amelyek hasonlóak a gráf legrövidebb útjának megtalálásához.

A legrövidebb út megtalálása a számítási geometriában (lásd Euklideszi legrövidebb út ).
Az utazó eladó probléma . Legalább egyszer meg kell találni a legrövidebb útvonalat, amely áthalad a megadott városokon (csúcsokon), majd visszatér az eredeti városba. Ez a probléma az NP-nehéz feladatok osztályába tartozik, ellentétben a legrövidebb út megtalálásának problémájával, amely ciklus nélküli gráfokban polinomiális időben megoldható. Az utazó eladó probléma megoldása nem hatékony nagy adathalmazok esetén.
A kanadai utazó probléma és a sztochasztikus legrövidebb út probléma a vizsgált probléma általánosítása, amelyben a bejárandó gráf előre teljesen ismeretlen és időben változik, vagy a következő áthaladást a gráfon valószínűségek alapján számítják ki.
A legrövidebb út megtalálása, amikor a gráfban transzformációk történnek. Például egy él súlyának megváltoztatása vagy egy csúcs törlése [20] .

Állítás a lineáris programozás problémájáról

Legyen adott egy irányított gráf ( V , A ), ahol V csúcsok halmaza, A pedig élek halmaza, s kezdőcsúccsal, t végponttal és w ij súlyokkal az A minden élére ( i , j ) . Az egyes élek súlya az x ij programváltozónak felel meg .

Ekkor a következőképpen tesszük fel a problémát: keressük meg a függvény minimumát , ahol , feltéve, hogy a következő egyenlőtlenség minden i -re és j -re teljesül: $F=\sum _{{ij\in A}}w_{{ij}}x_{{ij}}$ $x_{{ij}}\geq 0$ $\sum _{j}x_{{ij}}-\sum _{j}x_{{ji}}={\begin{cases}1,&{\text{if }}i=s;\\-1 ,&{\text{if }}i=t;\\0,&{\text{ egyébként.}}\end{cases}}$

Lásd még

Jegyzetek

↑ Gráfelmélet alkalmazása programozásra, 1985 .
↑ A gráfelmélet alkalmazása a programozásban, 1985 , p. 138-139.
↑ A gráfelmélet alkalmazása a programozásban, 1985 , p. 139-142.
↑ A gráfelmélet alkalmazása a programozásban, 1985 , p. 144-145.
↑ A gráfelmélet alkalmazása a programozásban, 1985 , p. 145-148.
↑ 1 2 Diszkrét matematika. Combinatorial Optimization on Graphs, 2003 .
↑ A gráfelmélet alkalmazása a programozásban, 1985 , p. 130-131.
↑ Cherkassky, Goldberg, Radzik, 1996 .
↑ 1 2 Bellman Richard, 1958 .
↑ 12 Moore , 1957 .
↑ M. Leyzorek, 1957 .
↑ Dijkstra, 1959 .
↑ Michael Fredman Lawrence, 1984 .
↑ Fredman Michael, 1987 .
↑ Shimbel, 1953 .
↑ Algoritmusok és szoftverek fejlesztése geometriai úttervezési problémákhoz, 1996 .
↑ Gyors útvonaltervezés .
↑ Autópálya Dimenzió, 2010 .
↑ Hub-Based Labeling Algorithm, 2011 .
↑ Ladyzhensky Y., Popoff Y. Algorithm, 2006 .

Irodalom

Evstigneev VA 3. fejezet. Iteratív algoritmusok globális gráfelemzéshez. Utak és burkolatok // Gráfelmélet alkalmazása a programozásban / Szerk. A. P. Ershova. - Moszkva: Tudomány . Fizikai és matematikai irodalom főkiadása, 1985. - S. 138-150. — 352 p.
Alekseev V.E., Talanov V.A. fejezet 3.4. A legrövidebb utak megkeresése gráfban // Grafikonok. Számítási modellek. Adatstruktúrák . - Nyizsnyij Novgorod: Nyizsnyij Novgorod állam kiadója. Egyetem, 2005. - S. 236-237. — 307 p. — ISBN 5–85747–810–8. Archivált: 2013. december 13. aWayback Machine
Galkina V.A. 4. fejezet Legrövidebb utak szerkesztése irányított gráfban // Discrete Mathematics. Kombinatorikus optimalizálás gráfokon. - Moszkva: "Helios ARV" kiadó, 2003. - S. 75-94. — 232 p. - ISBN 5-85438-069-2.
Berge K. 7. fejezet. Legrövidebb út probléma // Gráfelmélet és alkalmazásai = Theorie des graphes et ses applications / Szerk. I. A. Vainshtein. - Moszkva: Külföldi Irodalmi Kiadó , 1962. - S. 75-81. — 320 s.
Austin Ore. Gráfelmélet / Szerk. I. M. Ovchinnikova. - Tudományos Kiadó , 1980. - 336 p. Archiválva: 2013. december 15. aWayback Machine
Vitalij Osipov, A legrövidebb utak megtalálása az úthálózatokban: az elmélettől a megvalósításig a YouTube -on .
Harari F. 2. fejezet. Grafikonok // Gráfelmélet / szerk. G. P. Gavrilov - M .: Mir , 1973. - S. 27. - 301 p.
Cherkassky B. V. , Goldberg A. V. , Radzik T. Shortest paths algorithms: Theory and experimental assessment // Math . Prog. - Springer Science + Business Media , 1996. - Vol. 73, Iss. 2. - P. 129-174. — ISSN 0025-5610 ; 1436-4646 - doi:10.1007/BF02592101
Richard Bellman. Egy útválasztási problémáról // Quarterly of Applied Mathematics. - 1958. - T. 16 . - S. 87-90 .
Dijkstra E. W. Megjegyzés két problémához gráfokkal kapcsolatban // Szám . Math / F. Brezzi - Springer Science + Business Media , 1959. - Vol. 1, Iss. 1. - P. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Moore E. F. A legrövidebb út egy labirintuson keresztül // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 1957. április 2-5.) - Harvard University Press , 1959. - 20. évf. 2. - P. 285-292. — 345 p. - ( Annals of the Computation Laboratory of Harvard University ; Vol. 30) - ISSN 0073-0750
M. Leyzorek, RS Gray, AA Gray, WC Ladew, SR Meaker, RM Petry, RN Seitz. Modelltechnikák vizsgálata – Első éves jelentés – 1956. június 6. – 1957. július 1. – A kommunikációs rendszerek modelltechnikáinak tanulmánya . – Cleveland, Ohio: Case Institute of Technology, 1957.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci kupacok és felhasználásuk továbbfejlesztett hálózatoptimalizáló algoritmusokban (angolul) : napló. - Villamos- és Elektronikai Mérnöki Intézet , 1984. - P. 338-346 . — ISBN 0-8186-0591-X . - doi : 10.1109/SFCS.1984.715934 . Az eredetiből archiválva : 2012. október 11.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci kupacok és felhasználásuk továbbfejlesztett hálózatoptimalizáló algoritmusokban // Journal of the Association for Computing Machinery : Journal. - 1987. - 1. évf. 34 , sz. 3 . - P. 596-615 . doi : 10.1145 / 28869.28874 .
Shimbel, Alfonso. Kommunikációs hálózatok szerkezeti paraméterei // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , 4. sz . - S. 501-507 . - doi : 10.1007/BF02476438 .
Sanders, Péter. Gyors útvonaltervezés . - Google Tech Talk, 2009. - március 23. . - "Sablon: Inkonzisztens idézetek".
Chen, Danny Z. Algoritmusok és szoftverek fejlesztése geometriai úttervezési problémákhoz // ACM Computing Surveys : folyóirat. - 1996. - December ( 28. évf. , 4es. sz. ). — 18. o . - doi : 10.1145/242224.242246 .
Ábrahám, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Highway Dimension, Shortest Paths, and Provably Efficient Algorithms // ACM-SIAM Symposium on Discrete Algorithms : Journal. - 2010. - P. 782-793 .
Ábrahám, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. Egy csomópont-alapú címkézési algoritmus a legrövidebb úthálózatokhoz . Symposium on Experimental Algorithms] (eng.) : folyóirat. - 2011. - P. 230-241 .
Kroger, Martin. A legrövidebb többszörösen leválasztott út a két- és háromdimenziós polimer rendszerek összefonódásainak elemzéséhez // Computer Physics Communications : folyóirat. - 2005. - 20. évf. 168. sz . 168 . - P. 209-232 . - doi : 10.1016/j.cpc.2005.01.020 .
Ladyzhensky Y., Popoff Y. Algoritmus a gráf összes csomópontja közötti legrövidebb utak meghatározására két csomópont tömörítése után. Proceedings of Donyeck National Technical University, Számítástechnika és automatizálás. Vol.107. Donyeck (angol) : folyóirat. - 2006. - P. 68-75 . .

Szótárak és enciklopédiák	Britannica (online)
Bibliográfiai katalógusokban	GND : 4138403-9

Grafikon keresési algoritmusok
Tájékozatlan módszerek	Kétirányú keresés Sugárkeresés Lexikográfiai szélesség első keresés Szélesség első keresés Keresés költségkritérium szerint Mélységi első keresés Keresés visszafelé Keresés a csúcsra való mászás alapján Mélységben korlátozott keresés Mélység-első keresés iteratív elmélyítéssel
Tájékozott módszerek	Alfa béta vágás Elágazás és kötött módszer Keresés az első legjobb találat alapján A* B* D* Átmeneti pont keresése IDA* Rekurzív keresés az első legjobb találaton SMA*
Parancsikonok	Hullám algoritmus Bellman-Ford algoritmus Dijkstra algoritmusa Johnson algoritmus Levit algoritmusa Floyd-Warshall algoritmus Edge keresés
Minimálisan átívelő fa	Boruvka algoritmusa Prim algoritmusa Kruskal algoritmusa
Egyéb	British Museum algoritmus Edmonds algoritmus Fa bejárás Legközelebbi szomszéd algoritmus az utazó eladó problémájában