Levitin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. joulukuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Levitin algoritmi on graafien algoritmi , joka löytää lyhimmän etäisyyden graafin yhdestä kärjestä kaikkiin muihin. Algoritmi toimii myös graafisille negatiivisille reunapainoille . Algoritmia käytetään laajasti ohjelmoinnissa ja tekniikassa.

Ongelman kuvaus

Esimerkkejä

Vaihtoehto 1. Moskovan alueen kaupungit yhdistävä tieverkosto. Jotkut tiet ovat yksisuuntaisia. Etsi lyhyimmät polut Moskovan kaupungista jokaiseen alueen kaupunkiin (jos voit liikkua vain teitä pitkin).

Vaihtoehto 2. Maailman kaupunkien välillä on useita lentoja, joiden hinta on tiedossa. Lennon hinta paikasta A paikkaan B ei välttämättä ole sama kuin paikasta B paikkaan A kulkevan lennon hinta. Etsi minimikustannusreitti (mahdollisesti siirroilla ) Kööpenhaminasta Barnauliin .

Muodollinen määritelmä

Painotettu suunnattu [1] graafi ilman silmukoita on annettu . Etsi lyhyimmät polut jostakin graafin kärjestä kaikkiin muihin tämän graafin kärkikohtiin. $G(V,E)$ $a$ $G$

Algoritmi

Alla on suosittu ja tehokas muunnetun Levitin algoritmin toteutus erityisillä kaavioilla sivustolta e-maxx.ru. Sen ero "kanoniseen" versioon on se, että elementti lisätään jonoon alussa, ei lopussa. Tämä mahdollistaa vahvistuksen saavuttamisen joissakin kaavioissa, mutta johtaa pahimmassa tapauksessa eksponentiaaliseen käyntiaikaan (katso Monimutkaisuus-osio). $M1$

Merkintä

$N$ on graafin kärkipisteiden joukko
$M$ on graafin reunojen joukko
$g[ij]$ - kylkiluun paino (pituus). $ij$
$s$ - kärki, josta etäisyyksiä etsitään, eli aloituspiste.
$d[i]$ on lyhimmän polun nykyinen pituus kärjestä kärkeen $s$ $i$
$p[i]$ on kärkipiste, joka edeltää kärkeä lyhimmällä polulla kärjestä pisteeseen . $i$ $s$ $i$
$M0$ - kärjet, joiden etäisyys on jo laskettu (mutta ehkä ei kokonaan);
$M1$ — kärjet, joiden etäisyys lasketaan;
$M2$ — kärjet, joiden etäisyyttä ei ole vielä laskettu.
$osavaltio[i]$ — tallentaa sen joukon numeron, johon kärki i kuuluu.

Koodi

On syytä mainita heti, että alla oleva koodi ei ole täysin toimiva, koska kaavion rakennetta ei ole asetettu (millään tavalla). Tuloksena (oletusarvoisesti) on tilanne, jossa on graafi , joka koostuu kymmenestä (oletus) eristetystä pisteestä ja etsitään lyhintä polkua indeksin 1 kärjestä indeksin 3 kärkeen (oletus).

#include <iostream> // parirakenteelle: #include <apuohjelma> #sisällytä <vektori> #sisällytä < deque > // INT_MAX-arvolle: #include <climits> // käänteiselle funktiolle: #include <algoritm> käyttäen nimiavaruutta std ; typedef pari < int , int > reuna ; typedef vektori < vektori < reuna > > graafi ; const int INFINITY = INT_MAX ; // Algoritmin toiminnan oletusarvot (graafin kärkipisteiden määrä, polun alku- ja loppupisteiden indeksit) int oletusNumber = 10 , oletusAloitus = 1 , oletusFinish = 3 ; int main () { int numberOfVertices = oletusNumber , startVertex = oletusAloitus , finishVertex = oletusLopetus ; graafi g ( vertikkojen lukumäärä ); // Täällä luetaan graafin rakenne (jostain esim. tiedostosta). // Muuten, haun ulottuvuus ja kärkien lukumäärät todennäköisimmin // täytyy saada samasta lähteestä. vektori < int > d ( vertikkojen lukumäärä , INFINITY ); d [ alkuVertex ] = 0 ; vektorin < int > tila ( numberOfVertices , 2 ); tila [ alkuVertex ] = 1 ; deque < int > q ; q . push_back ( aloitusVertex ); vektori < int > p ( Vertisien lukumäärä , -1 ); kun ( ! q . tyhjä ()) { int vertex = q . edessä (); q . pop_front (); tila [ vertex ] = 0 ; for ( koko_t i = 0 ; i < g [ vertex ]. size (); ++ i ) { int to = g [ vertex ][ i ]. ensin pituus = g [ vertex ] [ i ]. toinen ; jos ( d [ to ] > d [ kärki ] + pituus ) { d [ to ] = d [ vertex ] + pituus ; jos ( tila [ to ] == 2 ) q . push_back ( to ); muuten jos ( tila [ to ] == 0 ) q . push_front ( to ); p [ to ] = kärki ; tila [ to ] = 1 ; } } } if ( p [ viimeistelyVertex ] == -1 ) { cout << "Ei ratkaisua" << endl ; } muu { vektori < int > polku ; for ( int vertex = viimeistelyVertex ; vertex != -1 ; vertex = p [ vertex ]) polku . push_back ( vertex ); käänteinen ( polku .alku (), polku .loppu ( ) ); for ( koko_t i = 0 ; i < polku . koko (); ++ i ) cout << polku [ i ] + 1 << ' ' ; } // suorittaaksesi ei-komentoriviltä (jotta näet tuloksen) cin . saada (); paluu 0 ; }

Kuvaus

Olkoon taulukko D[1..N] nykyisen lyhimmän polun pituudet. Aluksi taulukko D täytetään "äärettömyyden" arvoilla, paitsi D[s] = 0. Algoritmin lopussa tämä matriisi sisältää lopulliset lyhyimmät etäisyydet.

Olkoon taulukon P[1..N] nykyiset esivanhemmat. Kuten D-taulukko, myös P-taulukko muuttuu vähitellen algoritmin aikana ja saa lopulliset arvot sen lopussa.

Aluksi kaikki kärjet sijoitetaan joukkoon M2, paitsi kärki V0, joka sijoitetaan joukkoon M1.

Algoritmin jokaisessa vaiheessa otamme kärjen joukosta M1 (otamme ylimmän elementin jonosta). Olkoon V valittu kärki. Käännämme tämän kärjen joukoksi M0. Sitten katsomme kaikkien tästä kärjestä tulevien reunojen läpi. Olkoon T nykyisen reunan toinen pää (eli ei yhtä suuri kuin V) ja L nykyisen reunan pituus.

Jos T kuuluu M2:een, siirrämme T jonon lopussa olevaan joukkoon M1. Asetamme DT:ksi yhtä suureksi kuin DV + L.
Jos T kuuluu M1:een, yritämme parantaa DT:n arvoa: DT = min(DT, DV + L). Itse kärki T ei liiku jonossa millään tavalla.
Jos T kuuluu M0:aan ja jos DT:tä voidaan parantaa (DT > DV + L), parannetaan DT:tä ja palautetaan kärkipiste T joukkoon M1 asettamalla se jonon kärkeen.

Tietysti joka kerta kun taulukkoa D päivitetään, myös taulukon P arvo tulee päivittää.

Algoritmin monimutkaisuus

Jos algoritmi on toteutettu väärin, käyttämällä deque-merkkiä jonojen M1' ja M1'' sijasta ja lisäämällä pisteitä M0:sta dequen alkuun, algoritmi toimii pahimmassa tapauksessa eksponentiaalisesti [2] , tätä ei suositella. Todellisilla kaavioilla algoritmi on osoittautunut varsin hyvin: sen ajoaika [3] . $O(MN)$

Dijkstran ja Levitin algoritmien vertailu

Verrattuna Dijkstran menetelmään Levitin menetelmä häviää siinä, että joitain pisteitä täytyy käsitellä toistuvasti, mutta voittaa yksinkertaisemmissa algoritmeissa, joissa M1-joukkoa otetaan ja jätetään pois. Kokeet osoittavat, että "geometrisen" alkuperän eli liikenneverkkojen ja todellisten etäisyyksien perusteella rakennetuille kuvaajille Levitin menetelmä osoittautuu nopeimmaksi. Hän voittaa myös ohjelman koon suhteen.

Levittin menetelmällä on myös se etu Dijkstran menetelmään verrattuna, että se soveltuu negatiivisiin kaaren pituuksiin (kunhan "kaaren pituus" on vain nimi, joka antaa meille hyödyllisiä assosiaatioita todellisuuteen). Jos oletetaan, että l(u):n arvot eivät välttämättä ole positiivisia, lyhimmän polun ongelman ratkaisusta tulee paljon monimutkaisempi.

Ensimmäinen vaikeus on, että Dijkstran menetelmän yksinkertainen sääntö tiettyyn kaareen lasketun etäisyyden lopullisuuden määrittämiseksi menetetään. Tämä vaikeus, kuten tulemme myöhemmin näkemään, ohitetaan, vaikka menetelmän tehokkuus heikkenee (joudumme tarkistamaan kaikki annettuun kärkeen johtavat kaaret).

Toinen vaikeus on vakavampi: negatiivisilla pituuksilla kaavio voi sisältää ääriviivoja negatiivisella kaaren pituuksien summalla (kutsutaanko tällaisia ääriviivoja "negatiivisiksi"). Negatiivisen ääriviivan lisääminen polkuun pienentää tavoitefunktion arvoa, ja mitä enemmän negatiivisen ääriviivan kierroksia lisäämme, sitä "parempi". On yksinkertaisesti mahdotonta päästä eroon minimin loputtomasta laskusta, mutta vaikeasta tilanteesta on kaksi tietä (tietenkin ulospääsyn valinta ei riipu meistä, vaan ratkaistavasta käytännön ongelmasta).

Estä ääriviivojen sisällyttäminen polkuun, eli harkitse vain yksinkertaisia polkuja, mutta tällainen kielto tekee tehtävästä erittäin vaikean.

Jos ääriviivat ovat negatiivisia, ota huomioon, että ongelmalla ei ole ratkaisua, ja rajoita ongelman ratkaisemiseen tapauksissa, joissa negatiivisia ääriviivoja ei ole. Tässä tapauksessa Levitin menetelmä antaa vaaditun optimaalisen ratkaisun, ja jollain modifioinnilla se mahdollistaa negatiivisten ääriviivojen "talpaamisen".

Katso myös

Bellman-Ford-algoritmi on ratkaisu samaan ongelmaan, jos graafi voi sisältää myös negatiivisia reunoja
Floyd-Warshall-algoritmi - lyhimmän etäisyyden löytäminen kaikkien kärkiparien välillä
Johnsonin algoritmi
Dijkstran algoritmi on ratkaisu samaan ongelmaan, mutta eri tavalla.

Muistiinpanot

↑ Tässä suuntaamattomat ja sekoitetut ("osittain suunnatut") graafit ovat suunnatun graafin erikoistapaus.
↑ Levit (muokattu Ford-Bellman) e-maxx.ru:sta työskentelee näytteilleasettajan palveluksessa. — Koodivoimat . Haettu 22. kesäkuuta 2013. Arkistoitu alkuperäisestä 6. kesäkuuta 2012. (määrätön)
↑ Levittin algoritmi - Wikiyhteenveto . neerc.ifmo.ru. Haettu 13. joulukuuta 2018. Arkistoitu alkuperäisestä 24. marraskuuta 2018. (määrätön)

Linkit

Kirjallisuus

B. Yu. Levit. Algoritmit kaavion lyhimpien reittien löytämiseksi. Neuvostoliiton tiedeakatemian Siperian osaston hydrodynamiikan instituutin julkaisut. la "Johtamisprosessien mallintaminen". Ongelma. 4. Novosibirsk. 1971. s. 1117-148
B. Yu. Levit, V. N. Livshits. Epälineaarisen verkon kuljetusongelmat, M. Transport. 1972. s. 43-61
Dijkstra E. W. Huomautus kahdesta ongelmasta graafien yhteydessä // Numero . Math / F. Brezzi - Springer Science + Business Media , 1959. - Voi. 1, Iss. 1. - s. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Romanovsky I.V. Diskreetti analyysi: Oppikirja soveltavan matematiikan ja tietojenkäsittelytieteen opiskelijoille. . - 3. painos - Pietari. : Nevskin murre , 2003. - S. 221-222.
Ananiy V. Levitin. Algoritmit: Johdatus Aigoritmien suunnitteluun ja analyysiin. - M . : "Williams" , 2006. - S. 189-195. — ISBN 0-201-74395-7 .

Kaavion hakualgoritmit
Tietämättömät menetelmät	Kaksisuuntainen haku Säteen haku Leksikografinen leveys ensimmäinen haku Leveys ensimmäinen haku Hae kustannuskriteerin mukaan Ensimmäinen syvyyshaku Peruutushaku Hae kiipeämällä huipulle Syvyysrajoitettu haku Syvyys-ensin haku iteratiivisella syventämisellä
Tietoon perustuvat menetelmät	Alfa beta leikkaus Haara- ja sidontamenetelmä Hae ensimmäisen parhaan osuman perusteella A* B* D* Siirtymäkohdan löytäminen IDA* Rekursiivinen haku ensimmäisen parhaan osuman perusteella SMA*
Pikanäppäimet	Aalto-algoritmi Bellman-Ford-algoritmi Dijkstran algoritmi Johnsonin algoritmi Levitin algoritmi Floyd-Warshall-algoritmi Reunahaku
Vähintään ulottuva puu	Boruvkan algoritmi Primin algoritmi Kruskalin algoritmi
Muut	British Museum Algorithm Edmondsin algoritmi Puun läpikulku Lähin naapuri -algoritmi matkustavan myyjän ongelmassa