Levits algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 december 2015; kontroller kräver 8 redigeringar .

Levits algoritm är en algoritm på grafer som hittar det kortaste avståndet från en av grafens hörn till alla andra. Algoritmen fungerar även för grafer med negativ kantvikt . Algoritmen används flitigt inom programmering och teknik.

Problemformulering

Exempel

Alternativ 1. Med tanke på ett nätverk av vägar som förbinder städerna i Moskva-regionen. Vissa vägar är enkelriktade. Hitta de kortaste vägarna från staden Moskva till varje stad i regionen (om du bara kan röra dig längs vägarna).

Alternativ 2. Det finns ett antal flygningar mellan världens städer, kostnaden är känd för varje. Kostnaden för ett flyg från A till B kanske inte är lika med kostnaden för ett flyg från B till A. Hitta den lägsta kostnadsrutten (eventuellt med transfers) från Köpenhamn till Barnaul .

Formell definition

En viktad riktad [1] graf utan loopar ges . Hitta de kortaste vägarna från någon hörn av grafen till alla andra hörn i denna graf. $G(V,E)$ $a$ $G$

Algoritm

Nedan är en populär och effektiv implementering av den modifierade Levits algoritm på speciella grafer från sajten e-maxx.ru. Dess skillnad från den "kanoniska" versionen är att elementet läggs till i kön i början och inte i slutet. Detta gör det möjligt att uppnå en vinst på vissa grafer, men leder i värsta fall till exponentiell körtid (se avsnittet Komplexitet). $M1$

Notation

$N$ är uppsättningen av grafens hörn
$M$ är uppsättningen av grafkanter
$g[ij]$ - vikt (längd) på revbenet $I j$
$s$ - vertexet, från vilket avstånden söks, det vill säga startpunkten.
$d[i]$ är den aktuella längden på den kortaste vägen från vertex till vertex $s$ $i$
$pi]$ är spetsen som föregår spetsen på den kortaste vägen från spetsen till . $i$ $s$ $i$
$M0$ - hörn, till vilka avståndet redan har beräknats (men kanske inte helt);
$M1$ — hörn, till vilka avståndet beräknas;
$M2$ — hörn, till vilka avståndet ännu inte har beräknats.
$tillstånd[i]$ — lagrar numret på den mängd som vertex i tillhör.

Kod

Det är värt att omedelbart nämna att koden nedan inte är fullt fungerande, eftersom strukturen på grafen inte är inställd (på något sätt). Resultatet (som standard) är en situation där det finns en graf som består av tio (standard) isolerade hörn, och den kortaste vägen söks från vertex med index 1 till vertex med index 3 (standard).

#include <iostream> // för parstrukturen: #inkludera <verktyg> #inkludera <vektor> #inkludera <deque> // för INT_MAX-värde: #inkludera <climits> // för den omvända funktionen: #include <algoritm> använder namnutrymme std ; typedef par < int , int > edge ; typedef vektor < vektor < kant > > graf ; const int INFINITY = INT_MAX ; // Standardvärden för algoritmoperationen (antal grafens hörn, index för sökvägens initiala och sista hörn) int defaultNumber = 10 , defaultStart = 1 , defaultFinish = 3 ; int main () { int numberOfVertices = defaultNumber , startVertex = defaultStart , finishVertex = defaultFinish ; graf g ( antalOfVertices ); // Här läser vi strukturen på grafen (från någonstans, till exempel från en fil). // Förresten, dimensionen och antalet hörn för sökningen måste troligen // hämtas från samma källa. vektor < int > d ( numberOfVertices , INFINITY ); d [ startVertex ] = 0 ; vektor < int > tillstånd ( numberOfVertices , 2 ); state [ startVertex ] = 1 ; deque < int > q ; q . push_back ( startVertex ); vektor < int > p ( antalOfVertices , -1 ); medan ( ! q . tom ()) { int vertex = q . front (); q . pop_front (); state [ vertex ] = 0 ; för ( size_t i = 0 ; i < g [ vertex ]. storlek (); ++ i ) { int till = g [ vertex ][ i ]. först , längd = g [ vertex ][ i ]. andra ; if ( d [ till ] > d [ vertex ] + längd ) { d [ till ] = d [ vertex ] + längd ; if ( ange [ till ] == 2 ) q . push_back ( till ); annat om ( ange [ till ] == 0 ) q . push_front ( till ); p [ till ] = vertex ; ange [ till ] = 1 ; } } } if ( p [ finishVertex ] == -1 ) { cout << "Ingen lösning" << endl ; } annan { vektor < int > sökväg ; för ( int vertex = finishVertex ; vertex != -1 ; vertex = p [ vertex ]) väg . push_back ( vertex ); reverse ( bana .börja (), väg .slut ( ) ); för ( size_t i = 0 ; i < sökväg . storlek (); ++ i ) cout << sökväg [ i ] + 1 << ' ' ; } // för att köra från en icke-kommandorad (så att du kan se resultatet) cin . få (); returnera 0 ; }

Beskrivning

Låt matrisen D[1..N] innehålla de aktuella kortaste väglängderna. Inledningsvis fylls matrisen D med "oändlighets"-värden, förutom D[s] = 0. I slutet av algoritmen kommer denna matris att innehålla de sista kortaste avstånden.

Låt arrayen P[1..N] innehålla de nuvarande förfäderna. Förutom D-matrisen ändras P-matrisen gradvis under algoritmens gång, och i slutet av den antar den de slutliga värdena.

Inledningsvis placeras alla hörn i mängden M2, förutom vertexen V0, som är placerad i mängden M1.

Vid varje steg i algoritmen tar vi en vertex från uppsättningen M1 (vi tar det översta elementet från kön). Låt V vara det valda hörnet. Vi översätter denna vertex till mängden M0. Sedan tittar vi igenom alla kanter som kommer ut från denna vertex. Låt T vara den andra änden av den aktuella kanten (det vill säga inte lika med V), och L vara längden på den aktuella kanten.

Om T tillhör M2, överför vi T till uppsättningen M1 i slutet av kön. Vi sätter DT lika med DV + L.
Om T tillhör M1, så försöker vi förbättra värdet på DT: DT = min(DT, DV + L). Själva vertex T rör sig inte på något sätt i kön.
Om T tillhör M0, och om DT kan förbättras (DT > DV + L), så förbättrar vi DT, och returnerar vertex T till uppsättningen M1, och placerar den i spetsen av kön.

Naturligtvis, varje gång array D uppdateras, bör värdet i array P också uppdateras.

Algoritmens komplexitet

Om algoritmen är felaktigt implementerad, genom att använda en deque istället för köerna M1' och M1'' och lägga till hörn från M0 till början av deque, kommer algoritmen att köras exponentiellt i värsta fall [2] , detta rekommenderas inte. På riktiga grafer har algoritmen visat sig ganska väl: dess körtid [3] . $O(MN)$

Jämförelse av Dijkstras och Levits algoritmer

I jämförelse med Dijkstras metod förlorar Levits metod i det faktum att vissa hörn måste bearbetas upprepade gånger, men vinner i enklare algoritmer för att inkludera och exkludera hörn från M1-uppsättningen. Experiment visar att för grafer med ett "geometriskt" ursprung, det vill säga för grafer byggda på basis av transportnätverk och verkliga avstånd, visar sig Levits metod vara den snabbaste. Han vinner även när det gäller storleken på programmet.

Levitts metod har också den fördelen framför Dijkstras att den gäller negativa båglängder (”båglängd” är trots allt bara ett namn som ger oss användbara associationer till verkligheten). Om vi antar att värdena för l(u) inte nödvändigtvis är positiva, blir lösningen av problemet med den kortaste vägen mycket mer komplicerad.

Den första svårigheten är att en enkel regel i Dijkstras metod för att bestämma slutgiltigheten av det beräknade avståndet till en viss båge går förlorad. Denna svårighet, som vi kommer att se senare, förbigås, men med viss förlust av metodens effektivitet (vi måste kontrollera alla bågar som leder till den givna vertexen).

Den andra svårigheten är allvarligare: för negativa längder kan grafen innehålla konturer med en negativ summa av båglängder (låt oss kalla sådana konturer "negativa"). Att lägga till en negativ kontur till banan minskar värdet på objektivfunktionen, och ju fler rundor av den negativa konturen vi lägger till, desto "bättre". Det är helt enkelt omöjligt att bli av med den oändliga minskningen av minimum, men det finns två vägar ut ur en svår situation (naturligtvis beror valet av utväg inte på oss, utan på att det praktiska problemet löses).

Förbjud införande av konturer i banan, det vill säga överväg bara enkla vägar, men ett sådant förbud gör uppgiften mycket svår.

Vid negativa konturer, tänk på att problemet inte har någon lösning, och begränsa dig till att lösa problemet i de fall det inte finns några negativa konturer. I det här fallet kommer Levits metod att ge den nödvändiga optimala lösningen, och med viss modifiering kommer den att tillåta att "fånga" negativa konturer.

Se även

Bellman-Ford-algoritmen är en lösning på samma problem om grafen även kan innehålla kanter med negativ vikt
Floyd-Warshall algoritm - hitta det kortaste avståndet mellan alla par av hörn
Johnsons algoritm
Dijkstras algoritm är en lösning på samma problem, men på ett annat sätt.

Anteckningar

↑ Här är oriktade och blandade ("delvis riktade") grafer ett specialfall av en riktad graf.
↑ Levit (modifierad Ford-Bellman) från e-maxx.ru arbetar för utställaren. — Codeforces . Hämtad 22 juni 2013. Arkiverad från originalet 6 juni 2012. (obestämd)
↑ Levitts algoritm - Wikisummary . neerc.ifmo.ru. Hämtad 13 december 2018. Arkiverad från originalet 24 november 2018. (obestämd)

Länkar

Litteratur

B. Yu. Levit. Algoritmer för att hitta de kortaste vägarna på en graf. Förfaranden från Institutet för hydrodynamik i den sibiriska grenen av USSR Academy of Sciences. lö. "Modellering av ledningsprocesser". Problem. 4. Novosibirsk. 1971. sid. 1117-148
B. Yu. Levit, V. N. Livshits. Icke-linjära nätverkstransportproblem, M. Transport. 1972. s. 43-61
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
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Romanovsky I.V. Diskret analys: Lärobok för elever med inriktning mot tillämpad matematik och datavetenskap. . - 3:e uppl. - St Petersburg. : Nevsky Dialect , 2003. - S. 221-222.
Ananiy V. Levitin. Algoritmer: Introduktion till design och analys av aigoritmer. - M . : "Williams" , 2006. - S. 189-195. — ISBN 0-201-74395-7 .

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