Kortaste vägen Problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 augusti 2021; kontroller kräver 4 redigeringar .

Det kortaste vägproblemet är problemet med att hitta den kortaste vägen (kedjan) mellan två punkter (hörn) på en graf där summan av vikterna av kanterna som utgör vägen minimeras.

Kortaste vägproblemet är ett av de viktigaste klassiska problemen inom grafteorin . Idag är många algoritmer kända för att lösa det .

Det här problemet har andra namn: det minsta sökvägsproblemet eller, i en föråldrad version, diligensproblemet.

Betydelsen av denna uppgift bestäms av dess olika praktiska tillämpningar . GPS-navigatorer söker till exempel efter den kortaste vägen mellan en startpunkt och en destination. Korsningar fungerar som hörn, och vägar är kanter som ligger mellan dem. Om summan av väglängderna mellan korsningar är minimal, så är den hittade vägen den kortaste.

Definition

Problemet med att hitta den kortaste vägen på en graf kan definieras för en oriktad , riktad eller blandad graf. Därefter kommer vi att överväga problemformuleringen i den enklaste formen för en oriktad graf. För en blandad och riktad graf måste även kanternas riktningar beaktas.

En graf är en samling av en icke-tom uppsättning av hörn och kanter (uppsättningar av par av hörn). Två hörn i en graf ligger intill varandra om de delar en gemensam kant. En bana i en oriktad graf är en sekvens av hörn som ligger intill för . En sådan bana kallas en längdväg från vertex till ( indikerar numret på banans hörn och har inget att göra med numreringen av hörn på grafen). $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}$ $i$

Låta vara en kant som förbinder två hörn: och . Givet en viktfunktion som mappar kanter till deras vikter vars värden uttrycks som reella tal, och en oriktad graf . Då blir den kortaste vägen från vertex till vertex den väg (där och ) som har minimivärdet av summan . $e_{{i,j}}$ $v_{i}$ $v_{j}$ $f:E\rightarrow {\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}}).$

Det finns olika formuleringar av problemet med kortaste vägen:

Problemet med den kortaste vägen till en given destination. Det krävs att hitta den kortaste vägen till en given målpunkt t som börjar vid var och en av grafens hörn (utom t). Genom att ändra riktningen för varje kant som hör till grafen kan detta problem reduceras till problemet med en enda initial vertex (där sökningen efter den kortaste vägen från en given vertex till alla andra utförs).
Problemet med den kortaste vägen mellan ett givet par av hörn. Det krävs för att hitta den kortaste vägen från en given vertex u till en given vertex v.
Problemet med den kortaste vägen mellan alla par av hörn. Det krävs att man hittar den kortaste vägen från varje vertex u till varje vertex v. Detta problem kan också lösas med hjälp av en algoritm utformad för att lösa problemet med en källpunkt, men vanligtvis löses det snabbare.

I olika formuleringar av problemet kan kantens längds roll spelas inte bara av själva längderna utan också av tid, kostnad, utgifter, mängden resurser som förbrukas (material, finansiellt, bränsle och energi, etc.) eller andra egenskaper associerade med passagen av varje kant. Således finner problemet praktisk tillämpning inom ett stort antal områden (datavetenskap, ekonomi, geografi, etc.).

Problemet med kortaste vägen är föremål för ytterligare begränsningar

Problemet med den kortaste vägen uppstår mycket ofta i en situation där ytterligare begränsningar måste beaktas. Deras närvaro kan avsevärt öka komplexiteten i uppgiften [1] . Exempel på sådana uppgifter:

Den kortaste vägen som går genom en given uppsättning hörn. Två begränsningar kan övervägas: den kortaste vägen måste passera genom den valda uppsättningen av hörn, och den kortaste vägen måste innehålla så få ovalda hörn som möjligt. Den första av dessa är välkänd inom operationsforskningsteori [2] .
Minsta täckning av hörnen i en riktad graf med banor. Sökningen utförs efter det minsta antalet banor som täcker grafen, nämligen en delmängd av alla st banor, så att varje vertex i en riktad graf tillhör minst en sådan väg [3] .
Problemet med nödvändiga vägar. Det krävs att hitta en uppsättning st med banor med minimal kardinalitet så att det för alla finns en väg som täcker den. är en uppsättning av några banor i en riktad graf G [4] . $P={p_{1},\dots ,p_{m}}$ $t_{i}\i R$ $p_{j}\i P$ $R={t_{1},\dots ,t_{k}}$
Minimal täckning av bågar av en riktad graf av banor. Problemet är att hitta den minsta delmängden av alla vägar i termer av antalet vägar, så att varje båge tillhör åtminstone en sådan väg. I detta fall är ett ytterligare krav möjligt att alla vägar kommer från en vertex [5] .

Algoritmer

På grund av det faktum att det finns många olika formuleringar av detta problem, finns det de mest populära algoritmerna för att lösa problemet med att hitta den kortaste vägen på en graf:

Dijkstras algoritm hittar den kortaste vägen från en av grafens hörn till alla andra. Algoritmen fungerar endast för grafer utan kanter med negativ vikt [6] .
Bellman-Ford-algoritmen hittar de kortaste vägarna från en grafvertex till alla andra i en viktad graf. Kantvikter kan vara negativa.
A*-sökalgoritmen hittar den billigaste vägen från en vertex (start) till en annan (mål, slut) med den första bästa matchande sökalgoritmen i grafen.
Floyd-Warshall-algoritmen hittar de kortaste vägarna mellan alla hörn av en vägd riktad graf [6] .
Johnsons algoritm hittar de kortaste vägarna mellan alla par av hörn i en vägd riktad graf.
Lee-algoritmen (vågalgoritmen) är baserad på sökmetoden bredd-först. Hittar en väg mellan hörn s och t i en graf (s är inte samma som t) som innehåller det minsta antalet mellanliggande hörn (kanter). Huvudapplikationen är spårning av elektriska anslutningar på mikrokretschip och på kretskort . Används även för att hitta det kortaste avståndet på en karta i strategispel.
Att hitta den kortaste vägen baserat på Kildal-algoritmen [7] .

Arbetet (Cherkassky et al., 1993) [8] presenterar flera fler algoritmer för att lösa detta problem.

Problemet med att hitta den kortaste vägen från en vertex till alla andra

I denna problemformulering utförs sökningen efter den kortaste vägen från vertex v till alla andra hörn på grafen.

Oviktad riktad graf

Algoritm	Komplexitet	Författare
Utöka första sökningen	O ( V+E )

Detta är en ofullständig lista och kanske aldrig uppfyller vissa standarder för fullständighet. Du kan komplettera det från välrenommerade källor .

Riktad graf med icke-negativa vikter

Algoritm	Komplexitet	Författare
-	O ( V 2 EL )	Ford 1956
Bellman-Ford algoritm	O ( VE )	Bellman 1958 [9] , Moore 1957 [10]
-	O ( V 2 log V )	Danzig 1958, Danzig 1960, Minty (jfr Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dijkstras listalgoritm . _	O ( V2 ) _	Leyzorek et al. 1957 [11] , Dijkstra 1959 [12]
Dijkstras algoritm med modifierad binär hög	O (( E + V ) log V )	-
. . .	. . .	. . .
Dijkstras algoritm med 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 algoritm	O ( E log E / V L )	Gabow 1983, Gabow 1985
-	O ( E + V √ log L )	Ahuja et al. 1990

Detta är en ofullständig lista och kanske aldrig uppfyller vissa standarder för fullständighet. Du kan komplettera det från välrenommerade källor .

Riktad graf med godtyckliga vikter

Algoritm	Komplexitet	Författare
Bellman-Ford algoritm	O ( VE )	Bellman [9] , Moore [10]

Detta är en ofullständig lista och kanske aldrig uppfyller vissa standarder för fullständighet. Du kan komplettera det från välrenommerade källor .

Problemet med den kortaste vägen mellan alla par av hörn

Det kortaste vägproblemet mellan alla hörnpar för en oviktad riktad graf ställdes av Simbel 1953 [15] , som fann att det kunde lösas i ett linjärt antal matrismanipulationer (multiplikationer). Komplexiteten hos en sådan algoritm är O ( V4 ) .

Det finns även andra snabbare algoritmer för att lösa detta problem, såsom Floyd-Warshall-algoritmen med komplexitet O ( V 3 ), och Johnson-algoritmen (som är en kombination av Bellman-Ford- och Dijkstra-algoritmerna) med komplexitet O ( VE + V2 log V ) .

Applikation

Problemet med att hitta den kortaste vägen på en graf kan tolkas på olika sätt och tillämpas på olika områden. Följande är exempel på olika tillämpningar av problemet. Andra tillämpningar undersöks inom disciplinen som handlar om operationsforskning [16] .

Karttjänster

Algoritmer för diagram med kortaste väg används för att hitta vägar mellan fysiska objekt på karttjänster som Google Maps eller OpenStreetMap . I utbildningsvideon från Google kan du lära dig olika effektiva algoritmer som används inom detta område [17] .

Icke-deterministisk maskin

Om vi föreställer oss en icke-deterministisk abstrakt maskin som en graf där hörn beskriver tillstånd och kanter definierar möjliga övergångar, så kan kortaste vägalgoritmer användas för att hitta den optimala sekvensen av lösningar för att uppnå huvudmålet. Till exempel, om hörnen är tillstånden för en Rubiks kub och kanten representerar en enda åtgärd på kuben, kan algoritmen tillämpas för att hitta en lösning med ett minimum antal drag.

Vägnät

Problemet med att hitta den kortaste vägen på en graf används ofta för att bestämma det kortaste avståndet i ett vägnät.

Vägnätet kan representeras som en graf med positiva vikter . Topparna är vägkorsningar , och kanterna är vägarna som förbinder dem. Kantvikter kan motsvara längden på en given sektion, tiden som krävs för att övervinna den eller kostnaden för att resa längs den. Orienterade kanter kan användas för att representera enkelriktade gator. I en sådan kolumn kan du ange en egenskap som indikerar att vissa vägar är viktigare än andra för långa resor (till exempel motorvägar). Det formaliserades i konceptet (idén) av motorvägar [18] .

För att implementera tillvägagångssättet, där vissa vägar är viktigare än andra, finns det många algoritmer. De löser problemet med att hitta den kortaste vägen mycket snabbare än liknande på vanliga grafer. Sådana algoritmer består av två steg:

förbehandlingsstadiet. Grafen är förbehandlad utan att ta hänsyn till de initiala och slutliga hörnen (det kan ta upp till flera dagar om du arbetar med riktiga data). Det utförs vanligtvis en gång och sedan används den mottagna datan.
begäran stadiet. En begäran och sökning efter den kortaste vägen utförs, medan de initiala och slutliga hörnen är kända.

Den snabbaste algoritmen kan lösa detta problem på Europas eller Amerikas vägar på en bråkdel av en mikrosekund [19] .

Andra tillvägagångssätt (tekniker) som används inom detta område:

ALT
Arc Flaggor
Sammandragningshierarkier
Transit Nod Routing
Räckviddsbaserad beskärning
Märkning

Liknande problem

Det finns problem som liknar problemet med att hitta den kortaste vägen på en graf.

Att hitta den kortaste vägen i beräkningsgeometri (se Euklidisk kortaste väg ).
Problemet med resande säljare . Det är nödvändigt att hitta den kortaste vägen som passerar genom de angivna städerna (hörn) minst en gång och sedan återvända till den ursprungliga staden. Detta problem tillhör klassen av NP-hårda problem, i motsats till problemet med att hitta den kortaste vägen, som kan lösas i polynomtid i grafer utan cykler. Problemet med resande säljare löses ineffektivt för stora datamängder.
Det kanadensiska resenärsproblemet och det stokastiska kortaste vägproblemet är en generalisering av det aktuella problemet, där grafen som ska passeras är helt okänd i förväg och ändras i tid, eller nästa passage genom grafen beräknas utifrån sannolikheter.
Uppgiften att hitta den kortaste vägen när transformationer sker i grafen. Till exempel att ändra vikten på en kant eller ta bort en vertex [20] .

Uttalande av problemet med linjär programmering

Låt en riktad graf ( V , A ) ges, där V är en uppsättning av hörn och A är en uppsättning kanter, med ett startpunkt s , slut t och vikter w ij för varje kant ( i , j ) i A . Vikten av varje kant motsvarar programvariabeln x ij .

Sedan ställs problemet på följande sätt: hitta minimum av funktionen , där , förutsatt att följande olikhet gäller för alla i och j : $F=\summa _{{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{ annars.}}\end{cases}}$

Se även

Anteckningar

↑ Tillämpning av grafteori på programmering, 1985 .
↑ Tillämpning av grafteori i programmering, 1985 , sid. 138-139.
↑ Tillämpning av grafteori i programmering, 1985 , sid. 139-142.
↑ Tillämpning av grafteori i programmering, 1985 , sid. 144-145.
↑ Tillämpning av grafteori i programmering, 1985 , sid. 145-148.
↑ 1 2 Diskret matematik. Combinatorial Optimization on Graphs, 2003 .
↑ Tillämpning av grafteori i programmering, 1985 , sid. 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 .
↑ Utveckling av algoritmer och programvara för geometriska vägplaneringsproblem, 1996 .
↑ Snabb ruttplanering .
↑ Motorvägsdimension, 2010 .
↑ En navbaserad märkningsalgoritm, 2011 .
↑ Ladyzhensky Y., Popoff Y. Algorithm, 2006 .

Litteratur

Evstigneev VA Kapitel 3. Iterativa algoritmer för global grafanalys. Banor och beläggningar // Tillämpning av grafteori i programmering / Ed. A. P. Ershova. - Moskva: Vetenskap . Huvudupplagan av fysisk och matematisk litteratur, 1985. - S. 138-150. — 352 sid.
Alekseev V.E., Talanov V.A. Kapitel 3.4. Hitta de kortaste vägarna i en graf // Grafer. Beräkningsmodeller. Datastrukturer . - Nizhny Novgorod: Förlag i delstaten Nizhny Novgorod. Universitet, 2005. - S. 236-237. — 307 sid. — ISBN 5–85747–810–8. Arkiverad13 december 2013 påWayback Machine
Galkina V.A. Kapitel 4. Konstruktion av kortaste vägar i en riktad graf // Diskret matematik. Kombinatorisk optimering på grafer. - Moskva: Förlaget "Helios ARV", 2003. - S. 75-94. — 232 sid. - ISBN 5-85438-069-2.
Berge K. Kapitel 7. Kortaste vägen Problem // Grafteori och dess tillämpningar = Theorie des graphes et ses applications / Ed. I. A. Vainshtein. - Moscow: Publishing House of Foreign Literature , 1962. - S. 75-81. — 320 s.
Austin Ore. Grafteori / Ed. I. M. Ovchinnikova. - Science Publishing House , 1980. - 336 sid. Arkiverad15 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 / ed. G. P. Gavrilov - M . : Mir , 1973. - S. 27. - 301 sid.
Cherkassky B. V. , Goldberg A. V. , Radzik T. Shortest paths-algoritmer: Teori och experimentell utvärdering // 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 ett routingproblem // Quarterly of Applied Mathematics. - 1958. - T. 16 . - S. 87-90 .
Dijkstra E. W. En anteckning om två problem i samband med grafer // Numer . 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. Den kortaste vägen genom 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 sid. - ( Annals of the Computation Laboratory of Harvard University ; Vol. 30) - ISSN 0073-0750
M. Leyzorek, RS Grey, AA Grey, WC Ladew, SR Meaker, RM Petry, RN Seitz. Undersökning av modelltekniker - Första årsrapporten - 6 juni 1956 - 1 juli 1957 - En studie av modelltekniker för kommunikationssystem . — Cleveland, Ohio: Case Institute of Technology, 1957.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci-högar och deras användning i förbättrade nätverksoptimeringsalgoritmer (engelska) : journal. - Institute of Electrical and Electronics Engineers , 1984. - P. 338-346 . — ISBN 0-8186-0591-X . - doi : 10.1109/SFCS.1984.715934 . Arkiverad från originalet den 11 oktober 2012.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci-högar och deras användning i förbättrade nätverksoptimeringsalgoritmer // Journal of the Association for Computing Machinery : journal. - 1987. - Vol. 34 , nr. 3 . - s. 596-615 . doi : 10.1145 / 28869.28874 .
Shimbel, Alfonso. Strukturella parametrar för kommunikationsnätverk // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , nr 4 . - S. 501-507 . - doi : 10.1007/BF02476438 .
Sanders, Peter. Snabb ruttplanering . - Google Tech Talk, 2009. - 23 mars. . - "Mall:Inkonsekventa citat".
Chen, Danny Z. Utvecklar algoritmer och programvara för geometriska vägplaneringsproblem // ACM Computing Surveys : journal. - 1996. - December ( vol. 28 , nr 4es ). — S. 18 . - doi : 10.1145/242224.242246 .
Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Motorvägsdimension, kortaste vägar och bevisligen effektiva algoritmer // ACM-SIAM Symposium on Discrete Algorithms: journal. - 2010. - S. 782-793 .
Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. En navbaserad märkningsalgoritm för kortaste vägar på vägnät . Symposium on Experimental Algorithms] (eng.) : journal. - 2011. - S. 230-241 .
Kroger, Martin. Kortaste multipel frånkopplade väg för analys av intrasslingar i två- och tredimensionella polymersystem // Computer Physics Communications : journal. - 2005. - Vol. 168 , nr. 168 . - S. 209-232 . - doi : 10.1016/j.cpc.2005.01.020 .
Ladyzhensky Y., Popoff Y. Algoritm för att definiera de kortaste vägarna mellan alla noder i en graf efter komprimering av två noder. Proceedings of Donetsk National Technical University, Computing and automation. Vol. 107. Donetsk (engelska) : tidskrift. - 2006. - S. 68-75 . .

Ordböcker och uppslagsverk	Britannica (online)
I bibliografiska kataloger	GND : 4138403-9

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare