Lyhimmän polun ongelma

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 20. elokuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Lyhyin polkuongelma  on ongelma löytää lyhin polku (ketju) kahden pisteen (pisteen) välillä graafista , jossa reitin muodostavien reunojen painojen summa on minimoitu.

Lyhimmän polun ongelma on yksi tärkeimmistä graafiteorian klassisista ongelmista . Nykyään sen ratkaisemiseen tunnetaan monia algoritmeja .

Tällä ongelmalla on muita nimiä: minimipolkuongelma tai vanhentuneessa versiossa kulkuväyläongelma.

Tämän tehtävän merkityksen määräävät sen erilaiset käytännön sovellukset . Esimerkiksi GPS-navigaattorit etsivät lyhimmän polun aloituspisteen ja määränpään välillä. Risteykset toimivat pisteinä, ja tiet ovat niiden välissä olevia reunoja. Jos risteysten välisten teiden pituuksien summa on minimaalinen, niin löydetty polku on lyhin.

Määritelmä

Kuvaajan lyhimmän polun löytämisen ongelma voidaan määrittää suuntaamattomalle , suunnatulle tai sekagraafille . Seuraavaksi tarkastellaan ongelman lausetta ohjaamattoman graafin yksinkertaisimmassa muodossa. Sekoitettua ja suunnattua graafia varten on lisäksi otettava huomioon reunojen suunnat.

Graafi on kokoelma ei-tyhjiä kärki- ja reunajoukkoja (pisteparien joukkoja). Graafin kaksi kärkeä ovat vierekkäisiä, jos niillä on yhteinen reuna. Polku ohjaamattomassa graafissa on sarja pisteitä , jotka ovat lähellä for . Tällaista polkua kutsutaan poluksi, jonka pituus on pisteestä pisteeseen ( ilmaisee polun kärjen numeron , eikä sillä ole mitään tekemistä graafin kärkien numeroinnin kanssa).

Antaa olla  reuna yhdistää kaksi kärkeä: ja . Annettu painofunktio , joka kartoittaa reunat niiden painoihin, joiden arvot ilmaistaan ​​reaalilukuina, ja suuntaamaton graafi . Tällöin lyhin polku kärjestä kärkeen on polku (jossa ja ), jolla on summan pienin arvo .

Lyhimmän polun ongelmasta on olemassa useita muotoja:

• Ongelma lyhyimmästä tiestä tiettyyn määränpäähän. On löydettävä lyhin polku tiettyyn kohdepisteeseen t, joka alkaa kustakin graafin kärjestä (paitsi t). Muuttamalla kunkin graafiin kuuluvan reunan suuntaa tämä ongelma voidaan pelkistää yhden alkupisteen ongelmaksi (jossa suoritetaan lyhimmän polun haku tietystä kärjestä kaikkiin muihin).
• Tehtävä lyhyimmästä polusta tietyn kärkiparin välillä. On löydettävä lyhin polku tietystä kärjestä u tiettyyn pisteeseen v.
• Kaikkien kärkiparien välisen lyhimmän polun ongelma. Jokaisesta kärjestä u on löydettävä lyhin polku jokaiseen kärkeen v. Tämä ongelma voidaan ratkaista myös käyttämällä algoritmia, joka on suunniteltu ratkaisemaan yhden lähdepisteen ongelma, mutta yleensä se ratkaistaan ​​nopeammin.

Erilaisissa ongelman muotoiluissa reunan pituuden roolia voivat olla paitsi itse pituudet, myös aika, kustannukset, kustannukset, käytettyjen resurssien määrä (materiaali, rahoitus, polttoaine ja energia jne.) tai muut kunkin reunan läpikulkuun liittyvät ominaisuudet. Siten ongelma löytää käytännön sovellutuksia useilla aloilla (tietotekniikan, taloustieteen, maantieteen jne.).

Lyhyin polkuongelma, johon liittyy lisärajoituksia

Lyhimmän polun ongelma kohtaa hyvin usein tilanteessa, jossa on otettava huomioon lisärajoitukset. Niiden läsnäolo voi merkittävästi lisätä tehtävän monimutkaisuutta [1] . Esimerkkejä tällaisista tehtävistä:

1. Lyhin tie, joka kulkee tietyn kärkijoukon läpi. Kaksi rajoitusta voidaan ottaa huomioon: lyhimmän polun tulee kulkea valitun pistejoukon läpi ja lyhimmän polun tulee sisältää mahdollisimman vähän valitsemattomia pisteitä. Näistä ensimmäinen tunnetaan hyvin operaatiotutkimuksen teoriassa [2] .
2. Suunnatun graafin kärkien minimipeitto poluilla . Haku suoritetaan minimimäärälle graafia peittäviä polkuja, nimittäin kaikkien st polkujen osajoukkoa siten, että suunnatun graafin jokainen kärki kuuluu ainakin yhteen tällaiseen polkuun [3] .
3. Vaadittujen polkujen ongelma. On löydettävä joukko st polkuja, joiden kardinaalisuus on minimaalinen siten, että jokaiselle on polku , joka peittää sen.  on joukko polkuja suunnatussa graafissa G [4] .
4. Suunnatun graafin kaarien minimaalinen peitto poluilla. Ongelmana on löytää kaikkien polkujen vähimmäisosajoukko polkujen lukumäärän perusteella siten, että jokainen kaari kuuluu vähintään yhteen tällaiseen polkuun. Tässä tapauksessa lisävaatimus on mahdollista, että kaikki polut tulevat yhdestä kärjestä [5] .

Algoritmit

Koska tästä ongelmasta on monia erilaisia ​​​​formulaatioita, on olemassa suosituimmat algoritmit kaavion lyhimmän polun löytämisen ongelman ratkaisemiseksi:

• Dijkstran algoritmi löytää lyhimmän polun yhdestä graafin kärjestä kaikkiin muihin. Algoritmi toimii vain graafeille, joissa ei ole negatiivisia reunoja [6] .
• Bellman-Ford-algoritmi löytää lyhyimmät polut yhdestä graafin kärjestä kaikkiin muihin painotetussa graafissa. Reunapainot voivat olla negatiivisia.
• A*-hakualgoritmi löytää edullisimman reitin kärjestä (alku) toiseen (kohde, loppu) käyttämällä kaavion ensimmäistä parhaan haun hakualgoritmia.
• Floyd-Warshall-algoritmi löytää lyhimmät polut painotetun suunnatun graafin kaikkien kärkien välillä [6] .
• Johnsonin algoritmi löytää lyhyimmät polut kaikkien painotetun suunnatun graafin kärkiparien välillä.
• Lee-algoritmi (aaltoalgoritmi) perustuu leveys-ensin hakumenetelmään. Etsii polun graafin pisteiden s ja t välillä (s ei ole sama kuin t), joka sisältää vähimmäismäärän välipisteitä (reunoja). Pääsovellus on sähkökytkentöjen jäljitys mikropiirisiruille ja piirilevyille . Käytetään myös lyhimmän matkan löytämiseen kartalta strategiapeleissä.
• Lyhimmän polun löytäminen Kildal-algoritmin [7] perusteella .

Työ (Cherkassky et al., 1993) [8] esittää useita muita algoritmeja tämän ongelman ratkaisemiseksi.

Ongelma lyhimmän polun löytämisessä yhdestä huippupisteestä kaikkiin muihin

Tässä tehtävän muotoilussa suoritetaan lyhimmän polun haku kärjestä v kaikkiin muihin graafin pisteisiin.

Painottamaton suunnattu graafi

Algoritmi	Monimutkaisuus	Tekijä
Leveys ensimmäinen haku	O ( V+E )

Tämä on epätäydellinen luettelo, eikä se välttämättä koskaan täytä tiettyjä täydellisyysvaatimuksia. Voit täydentää sitä hyvämaineisista lähteistä .

Suunnattu kuvaaja ei-negatiivisilla painoilla

Algoritmi	Monimutkaisuus	Tekijä
-	O ( V 2 EL )	Ford 1956
Bellman-Ford-algoritmi	O ( VE )	Bellman 1958 [9] , Moore 1957 [10]
-	O ( V 2 log V )	Danzig 1958, Danzig 1960, Minty (vrt. Pollack & Wiebenson 1960), Whiting & Hillier 1960
Dijkstran lista - algoritmi .	O ( V2 ) _	Leyzorek et ai. 1957 [11] , Dijkstra 1959 [12]
Dijkstran algoritmi modifioidulla binäärikeolla	O ( ( E + V ) log V )	-
. . .	. . .	. . .
Dijkstran algoritmi Fibonacci-keon avulla	O ( E + V log V )	Fridman & Tarjan 1984 [13] , Fridman & Tarjan 1987 [14]
-	O ( E log log L )	Johnson 1982, Karlsson & Poblete 1983
Gabovin algoritmi	O ( E log E / V L )	Gabow 1983, Gabow 1985
-	O ( E + V √ log L )	Ahuja et ai. 1990

Tämä on epätäydellinen luettelo, eikä se välttämättä koskaan täytä tiettyjä täydellisyysvaatimuksia. Voit täydentää sitä hyvämaineisista lähteistä .

Suunnattu kuvaaja mielivaltaisilla painoilla

Algoritmi	Monimutkaisuus	Tekijä
Bellman-Ford-algoritmi	O ( VE )	Bellman [9] , Moore [10]

Tämä on epätäydellinen luettelo, eikä se välttämättä koskaan täytä tiettyjä täydellisyysvaatimuksia. Voit täydentää sitä hyvämaineisista lähteistä .

Kaikkien kärkiparien välisen lyhimmän polun ongelma

Lyhimmän polun ongelman painottamattoman suunnatun graafin kaikkien kärkiparien välillä esitti Simbel vuonna 1953 [15] , joka havaitsi, että se voidaan ratkaista lineaarisella määrällä matriisimanipulaatioita (kertoja). Tällaisen algoritmin monimutkaisuus on O ( V 4 ).

Tämän ongelman ratkaisemiseen on myös muita nopeampia algoritmeja, kuten Floyd-Warshall-algoritmi , jonka monimutkaisuus on O ( V 3 ), ja Johnson-algoritmi (joka on Bellman-Ford- ja Dijkstra-algoritmien yhdistelmä), jonka kompleksisuus on O ( VE + V 2 log V ) .

Sovellus

Kuvaajan lyhimmän polun löytämisen ongelma voidaan tulkita eri tavoin ja soveltaa eri alueilla. Seuraavassa on esimerkkejä ongelman erilaisista sovelluksista. Muita sovelluksia tutkitaan operaatiotutkimusta käsittelevällä tieteenalalla [16] .

Karttapalvelut

Kuvaajan lyhimmän polun algoritmeja käytetään etsimään polkuja fyysisten kohteiden välillä karttapalveluista, kuten Google Maps tai OpenStreetMap . Googlen harjoitusvideossa voit oppia erilaisia ​​tehokkaita algoritmeja, joita käytetään tällä alueella [17] .

Ei-deterministinen kone

Jos kuvittelemme epädeterministisen abstraktin koneen graafina, jossa kärjet kuvaavat tiloja ja reunat määrittelevät mahdolliset siirtymät, niin lyhimmän polun algoritmeja voidaan soveltaa löytämään optimaalinen ratkaisusarja päätavoitteen saavuttamiseksi. Esimerkiksi, jos kärjet ovat Rubikin kuution tiloja ja reuna edustaa yhtä kuution toimintoa, algoritmia voidaan soveltaa ratkaisun löytämiseen mahdollisimman pienellä määrällä liikkeitä.

Tieverkot

Lyhyimmän polun löytäminen kaaviosta on laajalti käytössä tieverkon lyhimmän etäisyyden määrittämisessä.

Tieverkosto voidaan esittää graafisesti positiivisilla painoilla. Huippupisteet ovat tienristeyksiä ja reunat ovat teitä, jotka yhdistävät ne. Reunapainot voivat vastata tietyn osan pituutta, sen ylittämiseen tarvittavaa aikaa tai matkakustannuksia. Orientoituja reunoja voidaan käyttää edustamaan yksisuuntaisia ​​katuja. Tällaiseen sarakkeeseen voit syöttää ominaisuuden, joka osoittaa, että jotkin tiet ovat tärkeämpiä kuin toiset pitkillä matkoilla (esimerkiksi moottoritiet). Se virallistettiin moottoriteiden käsitteeseen (ideaan) [18] .

Lähestymistavan toteuttamiseksi, jossa jotkut tiet ovat tärkeämpiä kuin toiset, on olemassa monia algoritmeja. Ne ratkaisevat lyhimmän polun löytämisen ongelman paljon nopeammin kuin vastaavat tavalliset kaaviot. Tällaiset algoritmit koostuvat kahdesta vaiheesta:

1. esikäsittelyvaiheessa. Graafi esikäsitellään ottamatta huomioon alku- ja loppupisteitä (se voi kestää useita päiviä, jos työskentelet todellisen datan kanssa). Se suoritetaan yleensä kerran ja sitten käytetään vastaanotettua dataa.
2. pyyntövaihe. Pyyntö ja lyhimmän polun haku suoritetaan, kun alku- ja loppupisteet tunnetaan.

Nopein algoritmi voi ratkaista tämän ongelman Euroopan tai Amerikan teillä mikrosekunnin murto-osassa [19] .

Muita tällä alueella käytettyjä lähestymistapoja (tekniikoita):

• ALT
• Kaaren liput
• Supistushierarkiat
• Julkisen liikenteen solmureititys
• Tavoitteeseen perustuva karsiminen
• Merkinnät

Samanlaisia ​​ongelmia

On ongelmia, jotka ovat samanlaisia ​​kuin kaavion lyhimmän polun löytäminen.

• Lyhimmän polun löytäminen laskennallisessa geometriassa (katso Euklidinen lyhin polku ).
• Matkamyyjän ongelma . On löydettävä lyhin reitti, joka kulkee määritettyjen kaupunkien (pisteiden) läpi vähintään kerran ja palaa sitten alkuperäiseen kaupunkiin. Tämä ongelma kuuluu NP-kovien tehtävien luokkaan, toisin kuin lyhimmän polun löytämisen ongelma, joka voidaan ratkaista polynomiajassa kaavioissa ilman jaksoja. Matkamyyjä-ongelma ratkaistaan ​​tehottomasti suurilla tietojoukoilla.
• Kanadan matkustajaongelma ja stokastinen lyhimmän polun ongelma ovat yleistys tarkasteltavasta ongelmasta, jossa läpikäytävä graafi on täysin tuntematon etukäteen ja muuttuu ajassa tai seuraava graafin läpikulku lasketaan todennäköisyyksien perusteella.
• Tehtävä löytää lyhin polku, kun kaaviossa tapahtuu muunnoksia. Esimerkiksi reunan painon muuttaminen tai kärjen poistaminen [20] .

Lausunto lineaarisen ohjelmoinnin ongelmasta

Olkoon suunnattu graafi ( V , A ), jossa V  on joukko pisteitä ja A  on joukko reunoja, jonka alkupiste s , loppu t ja painot w ij jokaiselle A :n reunalle ( i , j ) . Kunkin reunan paino vastaa ohjelman muuttujaa x ij .

Sitten ongelma esitetään seuraavasti: etsi funktion minimi , jossa , edellyttäen, että seuraava epäyhtälö pätee kaikille i :lle ja j :lle:

Katso myös

• IEEE 802.1aq
• liikenneverkko
• Kaksisuuntainen haku

Muistiinpanot

1. ↑ Graafiteorian soveltaminen ohjelmointiin, 1985 .
2. ↑ Graafiteorian soveltaminen ohjelmointiin, 1985 , s. 138-139.
3. ↑ Graafiteorian soveltaminen ohjelmointiin, 1985 , s. 139-142.
4. ↑ Graafiteorian soveltaminen ohjelmointiin, 1985 , s. 144-145.
5. ↑ Graafiteorian soveltaminen ohjelmointiin, 1985 , s. 145-148.
6. ↑ 1 2 Diskreetti matematiikka. Combinatorial Optimization on Graphs, 2003 .
7. ↑ Graafiteorian soveltaminen ohjelmointiin, 1985 , s. 130-131.
8. ↑ Cherkassky, Goldberg, Radzik, 1996 .
9. ↑ 1 2 Bellman Richard, 1958 .
10. ↑ 12 Moore , 1957 .
11. ↑ M. Leyzorek, 1957 .
12. ↑ Dijkstra, 1959 .
13. ↑ Michael Fredman Lawrence, 1984 .
14. ↑ Fredman Michael, 1987 .
15. ↑ Shimbel, 1953 .
16. ↑ Algoritmien ja ohjelmistojen kehittäminen geometristen polkujen suunnitteluongelmiin, 1996 .
17. ↑ Nopea reittisuunnittelu .
18. ↑ Highway Dimension, 2010 .
19. ↑ Keskitinpohjainen merkintäalgoritmi, 2011 .
20. ↑ Ladyzhensky Y., Popoff Y. Algorithm, 2006 .

Kirjallisuus

• Evstigneev VA Luku 3. Iteratiiviset algoritmit globaaliin graafianalyysiin. Polut ja peitteet // Graafiteorian soveltaminen ohjelmointiin / Toim. A.P. Ershova. - Moskova: Tiede . Fysikaalisen ja matemaattisen kirjallisuuden pääpainos, 1985. - S. 138-150. — 352 s.
• Alekseev V.E., Talanov V.A. Luku 3.4. Lyhimpien polkujen löytäminen kaaviosta // Kuvaajat. Laskentamallit. Tietorakenteet . - Nižni Novgorod: Nižni Novgorodin osavaltion kustantamo. Yliopisto, 2005. - S. 236-237. — 307 s. — ISBN 5–85747–810–8. Arkistoitu13. joulukuuta 2013Wayback Machineen
• Galkina V.A. Luku 4. Lyhimpien polkujen rakentaminen suunnatussa graafissa // Diskreetti matematiikka. Kuvaajien kombinatorinen optimointi. - Moskova: Kustantaja "Helios ARV", 2003. - S. 75-94. — 232 s. - ISBN 5-85438-069-2.
• Berge K. Luku 7. Lyhimmän polun ongelma // Graafiteoria ja sen sovellukset = Theorie des graphes et ses applications / Toim. I. A. Vainshtein. - Moskova: Publishing House of Foreign Literature , 1962. - S. 75-81. – 320 s.
• Austin Ore. Graafiteoria / Toim. I. M. Ovchinnikova. - Science Publishing House , 1980. - 336 s. Arkistoitu15. joulukuuta 2013Wayback Machinessa
• Vitaly Osipov, Lyhimpien polkujen löytäminen tieverkoissa: teoriasta toteutukseen YouTubessa .
• Harari F. Luku 2. Graafit // Graafiteoria / toim. G. P. Gavrilov - M .: Mir , 1973. - S. 27. - 301 s.
• Cherkassky B. V. , Goldberg A. V. , Radzik T. Lyhyimpien polkujen algoritmit: teoria ja kokeellinen arviointi  // Math . Prog. - Springer Science + Business Media , 1996. - Voi. 73, Iss. 2. - s. 129-174. — ISSN 0025-5610 ; 1436-4646 - doi:10.1007/BF02592101
• Richard Bellman. Reititysongelmasta  // Quarterly of Applied Mathematics. - 1958. - T. 16 . - S. 87-90 .
• 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
• Moore E. F. Lyhin polku sokkelon läpi  // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2.-5. huhtikuuta 1957) - Harvard University Press , 1959. - Voi. 2. - s. 285-292. — 345 s. - ( 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. Mallitekniikoiden tutkimus - Ensimmäinen vuosikertomus - 6. kesäkuuta 1956 - 1. heinäkuuta 1957 - Tutkimus viestintäjärjestelmien  mallitekniikoista . - Cleveland, Ohio: Case Institute of Technology, 1957.
• Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci-kasat ja niiden käyttö parannetuissa verkon optimointialgoritmeissa  (englanniksi)  : päiväkirja. - Institute of Electrical and Electronics Engineers , 1984. - P. 338-346 . — ISBN 0-8186-0591-X . - doi : 10.1109/SFCS.1984.715934 . Arkistoitu alkuperäisestä 11. lokakuuta 2012.
• Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacci-kasat ja niiden käyttö parannetuissa verkon optimointialgoritmeissa  //  Journal of the Association for Computing Machinery  : Journal. - 1987. - Voi. 34 , nro. 3 . - s. 596-615 . doi : 10.1145 / 28869.28874 .
• Shimbel, Alfonso. Viestintäverkkojen rakenneparametrit // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , nro 4 . - S. 501-507 . - doi : 10.1007/BF02476438 .
• Sanders, Peter. Nopea reittisuunnittelu . - Google Tech Talk, 2009. - 23. maaliskuuta. . - "Malli: Epäjohdonmukaiset lainaukset".
• Chen, Danny Z. Algoritmien ja ohjelmistojen kehittäminen geometristen polkujen suunnitteluongelmiin  //  ACM Computing Surveys : päiväkirja. - 1996. - joulukuu ( osa 28 , nro 4es ). - s. 18 . - doi : 10.1145/242224.242246 .
• Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Valtatien ulottuvuus, lyhyimmat polut ja todistetusti tehokkaat algoritmit  //  ACM-SIAM Symposium on Discrete Algorithms : Journal. - 2010. - S. 782-793 .
• Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. Keskuspohjainen merkintäalgoritmi lyhimmille poluille tieverkostoissa . Symposium on Experimental Algorithms]  (eng.)  : Journal. - 2011. - s. 230-241 .
• Kroger, Martin. Lyhin moninkertainen irrotettu polku sotkeutumisten analysointiin kaksi- ja kolmiulotteisissa polymeerijärjestelmissä  //  Computer Physics Communications : päiväkirja. - 2005. - Voi. 168 , nro. 168 . - s. 209-232 . - doi : 10.1016/j.cpc.2005.01.020 .
• Ladyzhensky Y., Popoff Y. Algoritmi määrittää lyhimmät polut kaikkien graafin solmujen välillä kahden solmun pakkaamisen jälkeen. Proceedings of Donetsk National Technical University, Computing and Automation. Vol. 107. Donetsk  (englanniksi)  : päiväkirja. - 2006. - s. 68-75 . .

Sanakirjat ja tietosanakirjat	Britannica (verkossa)
Bibliografisissa luetteloissa	GND : 4138403-9

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