Korteste vej problem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. august 2021; checks kræver 4 redigeringer .

Problemet med den korteste vej er problemet med at finde den korteste vej (kæde) mellem to punkter (hjørnepunkter) på en graf , hvor summen af vægten af de kanter , der udgør stien, er minimeret.

Problemet med den korteste vej er et af de vigtigste klassiske problemer i grafteori . I dag er mange algoritmer kendt for at løse det .

Dette problem har andre navne: minimumsstiproblemet eller, i en forældet version, diligensproblemet.

Betydningen af denne opgave bestemmes af dens forskellige praktiske anvendelser . For eksempel søger GPS-navigatorer efter den korteste vej mellem et startpunkt og en destination. Korsveje fungerer som knudepunkter, og veje er kanter, der ligger mellem dem. Hvis summen af vejlængderne mellem kryds er minimal, så er den fundne vej den korteste.

Definition

Problemet med at finde den korteste vej på en graf kan defineres for en urettet , rettet eller blandet graf. Dernæst vil vi overveje problemformuleringen i den enkleste form for en urettet graf. For en blandet og rettet graf skal kanternes retninger desuden tages i betragtning.

En graf er en samling af et ikke-tomt sæt af hjørner og kanter (sæt af par af hjørner). To hjørner i en graf er tilstødende, hvis de deler en fælles kant. En sti i en urettet graf er en sekvens af knudepunkter , som støder op til for . En sådan sti kaldes en sti af længde fra toppunkt til ( angiver nummeret på kurvens toppunkt og har intet at gøre med nummereringen af toppunkter på grafen). $P=(v_{1},v_{2},\ldots ,v_{n})\in V\ gange V\ gange \ldots \ gange V$ $v_{i}$ $v_{{i+1}}$ $1\leq i<n$ $P$ $n$ $v_{1}$ $v_{n}$ $jeg$

Lade være en kant, der forbinder to hjørner: og . Givet en vægtfunktion, der kortlægger kanter til deres vægte, hvis værdier er udtrykt som reelle tal, og en urettet graf . Så vil den korteste vej fra toppunkt til toppunkt være stien (hvor og ), der har summens minimumværdi . $e_{{i,j}}$ $v_{i}$ $v_{j}$ $f:E\højrepil {\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}}).$

Der er forskellige formuleringer af problemet med den korteste vej:

Problemet med den korteste vej til en given destination. Det er påkrævet at finde den korteste vej til et givet destinationspunkt t, der starter ved hver af grafens toppunkter (undtagen t). Ved at ændre retningen af hver kant, der hører til grafen, kan dette problem reduceres til problemet med et enkelt indledende toppunkt (hvor søgningen efter den korteste vej fra et givet toppunkt til alle de andre udføres).
Problemet med den korteste vej mellem et givet par knudepunkter. Det er nødvendigt at finde den korteste vej fra et givet toppunkt u til et givet toppunkt v.
Problemet med den korteste vej mellem alle par af hjørner. Det er nødvendigt at finde den korteste vej fra hvert toppunkt u til hvert toppunkt v. Dette problem kan også løses ved hjælp af en algoritme designet til at løse problemet med et kildepunkt, men normalt løses det hurtigere.

I forskellige formuleringer af problemet kan kantens længde ikke kun spilles af længderne selv, men også af tid, omkostninger, udgifter, mængden af brugte ressourcer (materiale, finansiel, brændstof og energi osv.) eller andre egenskaber forbundet med passagen af hver kant. Problemet finder således praktisk anvendelse på en lang række områder (datalogi, økonomi, geografi osv.).

Problemet med den korteste vej er underlagt yderligere begrænsninger

Problemet med den korteste vej opstår meget ofte i en situation, hvor der skal tages højde for yderligere begrænsninger. Deres tilstedeværelse kan øge kompleksiteten af opgaven markant [1] . Eksempler på sådanne opgaver:

Den korteste vej, der går gennem et givet sæt af hjørner. Der kan tages hensyn til to begrænsninger: den korteste vej skal passere gennem det valgte sæt af toppunkter, og den korteste vej skal indeholde så få uvalgte toppunkter som muligt. Den første af disse er velkendt inden for operationsforskningsteori [2] .
Minimumsdækningen af hjørnerne af en rettet graf med stier. Søgningen udføres efter det mindste antal stier, der dækker grafen, nemlig en delmængde af alle st stier, således at hvert hjørne af en rettet graf tilhører mindst én sådan vej [3] .
Problemet med nødvendige stier. Det er nødvendigt at finde et sæt stier med minimal kardinalitet , således at der for enhver er en sti, der dækker den. er et sæt af nogle stier i en rettet graf G [4] . $P={p_{1},\dots ,p_{m}}$ $t_{i}\i R$ $p_{j}\i P$ $R={t_{1},\dots ,t_{k}}$
Minimal dækning af buer af en rettet graf med stier. Problemet er at finde den minimale delmængde af alle stier i form af antallet af stier, således at hver bue tilhører mindst én sådan sti. I dette tilfælde er et yderligere krav muligt, at alle stier kommer fra et toppunkt [5] .

Algoritmer

På grund af det faktum, at der er mange forskellige formuleringer af dette problem, er der de mest populære algoritmer til at løse problemet med at finde den korteste vej på en graf:

Dijkstras algoritme finder den korteste vej fra en af grafens hjørner til alle de andre. Algoritmen virker kun for grafer uden kanter med negativ vægt [6] .
Bellman-Ford-algoritmen finder de korteste veje fra et graftoppunkt til alle andre i en vægtet graf. Kantvægte kan være negative.
A*-søgealgoritmen finder den billigste rute fra et toppunkt (start) til et andet (mål, slutning) ved at bruge den første bedste søgealgoritme i grafen.
Floyd-Warshall-algoritmen finder de korteste veje mellem alle hjørner af en vægtet rettet graf [6] .
Johnsons algoritme finder de korteste veje mellem alle par af hjørner i en vægtet rettet graf.
Lee-algoritmen (bølgealgoritmen) er baseret på bredde-først søgemetoden. Finder en sti mellem knudepunkter s og t i en graf (s er ikke det samme som t), der indeholder det mindste antal mellemliggende knudepunkter (kanter). Hovedapplikationen er sporing af elektriske forbindelser på mikrokredsløbschips og på printkort . Bruges også til at finde den korteste afstand på et kort i strategispil.
At finde den korteste vej baseret på Kildal-algoritmen [7] .

Værket (Cherkassky et al., 1993) [8] præsenterer flere flere algoritmer til at løse dette problem.

Problemet med at finde den korteste vej fra et toppunkt til alle andre

I denne problemformulering udføres søgningen efter den korteste vej fra toppunktet v til alle andre toppunkter på grafen.

Uvægtet rettet graf

Algoritme	Kompleksitet	Forfatter
Bredde først søgning	O ( V+E )

Dette er en ufuldstændig liste og vil muligvis aldrig opfylde visse standarder for fuldstændighed. Du kan supplere det fra velrenommerede kilder .

Styret graf med ikke-negative vægte

Algoritme	Kompleksitet	Forfatter
-	O ( V 2 EL )	Ford 1956
Bellman-Ford algoritme	O ( VE )	Bellman 1958 [9] , Moore 1957 [10]
-	O ( V 2 log V )	Danzig 1958, Danzig 1960, Minty (jf. Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dijkstras listealgoritme . _	O ( V2 ) _	Leyzorek et al. 1957 [11] , Dijkstra 1959 [12]
Dijkstras algoritme med modificeret binær bunke	O (( E + V ) log V )	-
. . .	. . .	. . .
Dijkstras algoritme ved hjælp af Fibonacci Heap	O ( E + V log V )	Fridman & Tarjan 1984 [13] , Fridman & Tarjan 1987 [14]
-	O ( E log log L )	Johnson 1982, Karlsson & Poblete 1983
Gabovs algoritme	O ( E log E / V L )	Gabow 1983, Gabow 1985
-	O ( E + V √ log L )	Ahuja et al. 1990

Dette er en ufuldstændig liste og vil muligvis aldrig opfylde visse standarder for fuldstændighed. Du kan supplere det fra velrenommerede kilder .

Styret graf med vilkårlige vægte

Algoritme	Kompleksitet	Forfatter
Bellman-Ford algoritme	O ( VE )	Bellman [9] , Moore [10]

Dette er en ufuldstændig liste og vil muligvis aldrig opfylde visse standarder for fuldstændighed. Du kan supplere det fra velrenommerede kilder .

Problemet med den korteste vej mellem alle par af hjørner

Det korteste vejproblem mellem alle par af hjørner for en uvægtet rettet graf blev stillet af Simbel i 1953 [15] , som fandt ud af, at det kunne løses i et lineært antal matrixmanipulationer (multiplikationer). Kompleksiteten af en sådan algoritme er O ( V 4 ).

Der er også andre hurtigere algoritmer til at løse dette problem, såsom Floyd-Warshall-algoritmen med kompleksitet O ( V 3 ), og Johnson-algoritmen (som er en kombination af Bellman-Ford og Dijkstra-algoritmerne) med kompleksitet O ( VE + V2 log V ) .

Ansøgning

Problemet med at finde den korteste vej på en graf kan fortolkes på forskellige måder og anvendes i forskellige områder. Det følgende er eksempler på forskellige anvendelser af problemet. Andre anvendelser er ved at blive udforsket inden for disciplinen, der beskæftiger sig med operationsforskning [16] .

Korttjenester

Grafiske korteste sti-algoritmer bruges til at finde stier mellem fysiske objekter på korttjenester såsom Google Maps eller OpenStreetMap . I træningsvideoen fra Google kan du lære forskellige effektive algoritmer, der bruges på dette område [17] .

Ikke-deterministisk maskine

Hvis vi forestiller os en ikke-deterministisk abstrakt maskine som en graf, hvor toppunkter beskriver tilstande og kanter definerer mulige overgange, så kan korteste vejalgoritmer anvendes til at finde den optimale rækkefølge af løsninger for at nå hovedmålet. For eksempel, hvis hjørnerne er tilstanden af en Rubiks terning , og kanten repræsenterer en enkelt handling på terningen, så kan algoritmen anvendes til at finde en løsning med et minimum antal træk.

Vejnet

Problemet med at finde den korteste vej på en graf er meget brugt til at bestemme den korteste afstand i et vejnet.

Vejnettet kan repræsenteres som en graf med positive vægte . Punkterne er vejkryds , og kanterne er de veje, der forbinder dem. Kantvægte kan svare til længden af en given sektion, den tid, det tager at overvinde den, eller omkostningerne ved at rejse langs den. Orienterede kanter kan bruges til at repræsentere ensrettede gader. I en sådan kolonne kan du indtaste en karakteristik, der angiver, at nogle veje er vigtigere end andre til lange rejser (f.eks. motorveje). Det blev formaliseret i konceptet (ideen) om motorveje [18] .

For at implementere tilgangen, hvor nogle veje er vigtigere end andre, er der mange algoritmer. De løser problemet med at finde den korteste vej meget hurtigere end tilsvarende på almindelige grafer. Sådanne algoritmer består af to faser:

forbehandlingsstadiet. Grafen er forbehandlet uden at tage højde for de indledende og endelige hjørner (det kan tage op til flere dage, hvis du arbejder med rigtige data). Det udføres normalt én gang, og derefter bruges de modtagne data.
anmodningsstadiet. En anmodning og søgning efter den korteste vej udføres, mens de indledende og endelige toppunkter er kendt.

Den hurtigste algoritme kan løse dette problem på vejene i Europa eller Amerika på en brøkdel af et mikrosekund [19] .

Andre tilgange (teknikker), der bruges på dette område:

ALT
Arc Flag
Sammentrækningshierarkier
Transit Node Routing
Reach baseret beskæring
Mærkning

Lignende problemer

Der er problemer, der ligner problemet med at finde den korteste vej på en graf.

At finde den korteste vej i beregningsgeometri (se Euklidisk korteste vej ).
Problemet med den rejsende sælger . Det er påkrævet at finde den korteste rute, der passerer gennem de angivne byer (hjørner) mindst én gang og derefter vende tilbage til den oprindelige by. Dette problem hører til klassen af NP-hårde problemer, i modsætning til problemet med at finde den korteste vej, som kan løses i polynomiel tid i grafer uden cyklusser. Problemet med den rejsende sælger løses ineffektivt for store datasæt.
Det canadiske rejseproblem og det stokastiske korteste vejproblem er en generalisering af det undersøgte problem, hvor grafen, der skal gennemløbes, er fuldstændig ukendt på forhånd og ændrer sig i tid, eller den næste passage gennem grafen beregnes ud fra sandsynligheder.
Opgaven med at finde den korteste vej, når der sker transformationer i grafen. For eksempel ændring af vægten af en kant eller sletning af et toppunkt [20] .

Udtalelse af problemet med lineær programmering

Lad en rettet graf ( V , A ) være givet, hvor V er et sæt af hjørner, og A er et sæt af kanter, med et startpunkt s , ende t og vægte w ij for hver kant ( i , j ) i A. Vægten af hver kant svarer til programvariablen x ij .

Så er problemet stillet som følger: find minimum af funktionen , hvor , forudsat at følgende ulighed gælder for alle i og j : $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{ ellers.}}\end{cases}}$

Se også

Noter

↑ Anvendelse af grafteori til programmering, 1985 .
↑ Anvendelse af grafteori i programmering, 1985 , s. 138-139.
↑ Anvendelse af grafteori i programmering, 1985 , s. 139-142.
↑ Anvendelse af grafteori i programmering, 1985 , s. 144-145.
↑ Anvendelse af grafteori i programmering, 1985 , s. 145-148.
↑ 1 2 Diskret matematik. Kombinatorisk optimering på grafer, 2003 .
↑ Anvendelse af grafteori i programmering, 1985 , s. 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 .
↑ Udvikling af algoritmer og software til geometriske stiplanlægningsproblemer, 1996 .
↑ Hurtig ruteplanlægning .
↑ Motorvejsdimension, 2010 .
↑ En Hub-Based Labeling Algorithm, 2011 .
↑ Ladyzhensky Y., Popoff Y. Algorithm, 2006 .

Litteratur

Evstigneev VA Kapitel 3. Iterative algoritmer til global grafanalyse. Stier og belægninger // Anvendelse af grafteori i programmering / Red. A. P. Ershova. - Moskva: Videnskab . Hovedudgave af fysisk og matematisk litteratur, 1985. - S. 138-150. — 352 s.
Alekseev V.E., Talanov V.A. Kapitel 3.4. Find de korteste veje i en graf // Grafer. Beregningsmodeller. Datastrukturer . - Nizhny Novgorod: Forlag i Nizhny Novgorod-staten. Universitet, 2005. - S. 236-237. — 307 s. — ISBN 5–85747–810–8. Arkiveret13. december 2013 påWayback Machine
Galkina V.A. Kapitel 4. Konstruktion af korteste veje i en rettet graf // Diskret matematik. Kombinatorisk optimering på grafer. - Moskva: Forlaget "Helios ARV", 2003. - S. 75-94. — 232 s. - ISBN 5-85438-069-2.
Berge K. Kapitel 7. Shortest Path Problem // Grafteori og dens anvendelser = Theorie des graphes et ses applications / Red. I. A. Vainshtein. - Moscow: Publishing House of Foreign Literature , 1962. - S. 75-81. - 320 sek.
Austin Ore. Grafteori / Red. I. M. Ovchinnikova. - Science Publishing House , 1980. - 336 s. Arkiveret15. december 2013 påWayback Machine
Vitaly Osipov, Finding Shortest Paths in Road Networks: From Theory to Implementation on YouTube .
Harari F. Kapitel 2. Grafer // Grafteori / udg. G. P. Gavrilov - M . : Mir , 1973. - S. 27. - 301 s.
Cherkassky B. V. , Goldberg A. V. , Radzik T. Shortest paths-algoritmer: Teori og eksperimentel evaluering // Math . Prog. - Springer Science + Business Media , 1996. - Vol. 73, Iss. 2. - S. 129-174. — ISSN 0025-5610 ; 1436-4646 - doi:10.1007/BF02592101
Richard Bellman. Om et routingproblem // Quarterly of Applied Mathematics. - 1958. - T. 16 . - S. 87-90 .
Dijkstra E. W. En note om to problemer i forbindelse med grafer // Tal . Math / F. Brezzi - Springer Science + Business Media , 1959. - Vol. 1, Iss. 1. - S. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Moore E. F. Den korteste vej gennem en labyrint // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2.-5. april 1957) - Harvard University Press , 1959. - Vol. 2. - S. 285-292. — 345 s. - ( Annals of the Computation Laboratory of Harvard University ; bind 30) - ISSN 0073-0750
M. Leyzorek, RS Grey, AA Grey, WC Ladew, SR Meaker, RM Petry, RN Seitz. Undersøgelse af modelteknikker - Første årsberetning - 6. juni 1956 - 1. juli 1957 - En undersøgelse af modelteknikker for kommunikationssystemer . — Cleveland, Ohio: Case Institute of Technology, 1957.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci-dynger og deres anvendelser i forbedrede netværksoptimeringsalgoritmer (engelsk) : journal. - Institut for elektriske og elektroniske ingeniører , 1984. - S. 338-346 . — ISBN 0-8186-0591-X . - doi : 10.1109/SFCS.1984.715934 . Arkiveret fra originalen den 11. oktober 2012.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci-dynger og deres anvendelser i forbedrede netværksoptimeringsalgoritmer // Journal of the Association for Computing Machinery : journal. - 1987. - Bd. 34 , nr. 3 . - S. 596-615 . doi : 10.1145 / 28869.28874 .
Shimbel, Alfonso. Strukturelle parametre for kommunikationsnetværk // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , nr. 4 . - S. 501-507 . - doi : 10.1007/BF02476438 .
Sanders, Peter. Hurtig ruteplanlægning . - Google Tech Talk, 2009. - 23. marts. . - "Skabelon:Inkonsistente citater".
Chen, Danny Z. Udvikling af algoritmer og software til geometriske stiplanlægningsproblemer // ACM Computing Surveys : journal. - 1996. - December ( bind 28 , nr. 4es ). — S. 18 . - doi : 10.1145/242224.242246 .
Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Motorvejsdimension, korteste veje og beviseligt effektive algoritmer // ACM-SIAM Symposium om diskrete algoritmer: tidsskrift. - 2010. - S. 782-793 .
Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. En hub-baseret mærkningsalgoritme for korteste veje på vejnet . Symposium on Experimental Algorithms] (eng.) : journal. - 2011. - S. 230-241 .
Kroger, Martin. Korteste multiple afbrudte vej til analyse af sammenfiltringer i to- og tredimensionelle polymere systemer // Computer Physics Communications : journal. - 2005. - Bd. 168 , nr. 168 . - S. 209-232 . - doi : 10.1016/j.cpc.2005.01.020 .
Ladyzhensky Y., Popoff Y. Algoritme til at definere de korteste veje mellem alle noder i en graf efter komprimering af to noder. Proceedings of Donetsk National Technical University, Computing and automation. bind 107. Donetsk (engelsk) : tidsskrift. - 2006. - S. 68-75 . .

Ordbøger og encyklopædier	Britannica (online)
I bibliografiske kataloger	GND : 4138403-9

Algoritmer til grafsøgning
Uoplyste metoder	Tovejssøgning Strålesøgning Leksikografisk bredde første søgning Bredde først søgning Søg efter omkostningskriterium Dybde første søgning Backtracking søgning Søg ved at klatre til toppen Dybdebegrænset søgning Dybde-første søgning med iterativ uddybning
Informerede metoder	Alfa beta klipning Gren og bundet metode Søg efter første bedste match EN* B* D* At finde et overgangspunkt IDA* Rekursiv søgning på det første bedste match SMA*
Genveje	Bølgealgoritme Bellman-Ford algoritme Dijkstras algoritme Johnsons algoritme Levits algoritme Floyd-Warshall algoritme Kantsøgning
Minimumspændende træ	Boruvkas algoritme Prims algoritme Kruskals algoritme
Andet	British Museum Algoritme Edmonds algoritme Trækøring Nærmeste nabo-algoritme i problemet med rejsende sælger