Određivanje k-najkraćih puteva
Određivanje K-najkraćih puteva je prošireni algoritam algoritma najkraćeg puta u datoj mreži.
Ponekad je od ključnog značaja da imate više od jednog puta između dva čvora u mreži. U slučaju dodatnih ograničenja, drugi putevi koji se razlikuju od najkraće putanje se mogu izračunati. Za pronalaženje najkraćih putanja se mogu koristiti problemi najkraćeg puta , kao što je Dajkstrin algoritam ili Bellman-Fordov algoritam, a onda da ih proširimo na pronalaženje više od jednog puta. Određivanje k-najkraćih puteva je generalizacija problema najkraćeg puta . Algoritam ne samo da pronalazi najkraći put, već pronalazi i K-1 ostalih puteva u neopadajućem poretku njihovih cena.
Problem može biti ograničen na pronalazak K najkraćih puteva bez petlje (loopless) ili sa petljom.
Istorija uredi
Od 1957. godine bilo je dosta članaka objavljenih na temu određivanje k-najkraćih puteva. Većina radova, nije bila zasnovana na problemu nalaženja jednog najkraćeg puta između para čvorova, već na nalaženje niza od K najkraćih puteva, i ti radovi su objavljeni od 1960. god do 2001. god. Od tada, većina novijih istraživanja je u vezi primene algoritma i njegovih varijacija. U 2010. godini Majkl Ginter sa sar. objavio je knjigu o simboličkom traženju K-najkraćih puteva .[1]
Važne radovi o problemu određivanja k-najkraćih puteva:
Godina izdanja | Autor | Ime |
---|---|---|
1971 | Jin Jen | Pronalaženje K K-najkraćih puteva u mreži |
1972 | M. t. Ardon i sar. | Rekurzivni algoritam za kreiranje šeme i povezani podgrafovi |
1973 | P. M. Kamerini i dr. | K-najkraćih puteva u stablu grafa |
1975 | K. Aihara | Pristup proučavanju osnovnih puteva |
1976 | T. D Am et sar. | Algoritam za generisanje svih puteva između dva čvora u digrafu i njegova primena |
1988 | Ravindra K. Ahudža sar. | Brzi algoritmi za problem najkražeg puta |
1989 | S. Anily sar. | Rang listi najboljih binarnih stabala[mrtva veza] |
1990 | Ravindra K. | Brži algoritmi za određivanje najkraćeg puta |
1993 | El-Amin i saradnici | Ekspertski sistem za pronalaženje liearnog puta |
1997 | Dejvid Eppstein | Pronalaženje K-najkraćih puteva |
1997 | Ingo Althofer | K-najbolji režim u kompjuterskom šahu |
1999 | Ingo Althofer | „Sistemi Za Podršku Odlučivanju Sa Nekoliko Strukture Izbor”. |
2011 | Husain, Aljazzar, Stefan Leue | „K*: algoritam za pretragu K-najkraćih puteva”. doi:10.1016/j.artint.2011.07.003. |
BibTeX baza sadrži više članaka.
Algoritam uredi
Dajkstrin algoritam može biti generalizovan kako bi se pronašlo K-najkraćih puteva.
Definicije:
Algoritam:
|
Postoje u osnovi dve opcije algoritma za traženje K-najkraćih puteva:
Prva opcija uredi
U prvoj varijanti, putevi ne moraju biti bezciklučni David Eppsteinov algoritam obezbeđuje najbolje vreme.[2]
Druga opcija uredi
Druga opcija pripisuje se Jin Ju Jenu, putevi moraju biti bezciklučni.[3] (Ovo ograničenje uvodi dodatni nivo težine.) Jenov algoritam se koristi kada se u pitanju proste putanje, dok se Eppsteinov algoritam koristi za neproste putev (primer kada je dozvoljeno putu da prođe kroz isti čvor više puta).
Putevi ne moraju da budu bezciklični uredi
Za sve što treba, m - grana, n - broj čvorova.
Eppsteinov algoritam daje najbolje rezultate.[2] Eppsteinov model nalazi K najkraćih dužina (dozvoljavajući cikluse), povezujući dva čvora u digrafu, za vreme o(m+ nlogn + k).
Eppsteinov algoritam koristi tehniku transformacije grafa.
Ovaj model takođe može naći K najkraćih puteva iz početnog čvora s do svakog čvora u grafu, za vreme o(m + nlogn + kn).
Bezciklični algoritam za pronalaženje K-najkraćih puteva uredi
Najbolje vreme za ovaj model se pripisuje Jin. J. Jenu.[3] Jenov algoritam pronalazi dužine svih najkraćih puteva iz fiksnog čvora do svih ostalih čvorova u nenegativnoj n-čvorovnoj mreži.
Ovaj metod zahteva samo 2n2 dodataka i n2 poređenja- što je manje od drugih dostupnih algoritama.
Trenutno vreme je složenosti o(Kn(m + nlogn)). m predstavlja broj grana, n - broj čvorova.
Neki primeri i opis uredi
Primer #1 uredi
U sledećem primeru se koristi Jenov model da se pronađe prve K najkraćih putanja između čvorava koji su povezani. To jest, on pronalazi prvi, drugi, treći, itd sve do K.-og najkraćeg puta. Više informacija možete naći ovde.
Kod dat u ovom primeru pokušava da nađe K-najkraće putanje mreže koja ima 15-čvorova, koji su povezani jednosmernim i dvosmernim granama.
Primer #2 uredi
Drugi primer je upotreba algoritma prema kom pratite nekoliko objekata.
Tehnika implementira nekoliko objekata za praćenje zasnovanih na algoritmu za K-najkraćih putanja.
Sve informacije se mogu naći u "kompjuterskog vida laboratoriji – CVLAB" .
Primer #3 uredi
Još jedna primena algoritama za najkraće putanje je projektovanje tranzitne mreže, što povećava udobnost korisnika u transportnom prevozu. Takav primer tranzitne mreže može biti konstruisan, stavljajući na razmatranje vreme putovanja. Pored vremena putovanja, mogu se uzeti drugi uslovi u zavisnosti od ekonomskih i geografskih ograničenja. Bez obzira na razlike u parametrima, algoritam za određivanje K-najkraćih putovanja pronalazi najviše optimalna rešenja, zadovoljavajući gotovo sve potrebe korisnika. Takve aplikacije za najkraći put algoritmi postaju sve češće, u poslednje vreme Xu, He, Song and Chaudry (2012) proučavali su probleme K-najkraćih puteva u tranzitnoj mreži.[4]
Aplikacije uredi
Određivanje K-najkraćih putanja je dobra alternativa za:
- Planiranje geografskog puta
- Mrežno rutiranje, posebno za optičke mreže , gde postoje i dodatna ograničenja, koji ne mogu biti rešena uz pomoć običnog algoritma za najkraće putanje.
- Formiranje hipoteza u oblasti računarske lingvistike
- Redosled poređenja i traženje metaboličkih putanji u bioinformatici
- Praćenje nekoliko objekata
- Planiranje geografskog puta
- Put mreže: raskrsnice su čvorovi i svaka grana (link) grafa povezuje dva čvora (raskrsnice).
Varijacije uredi
Postoje dve osnovne varijacije na algoritam za određivanje K-najkraćih putanja kao što smo gore pomenuli. Sve ostale varijacije, spadaju pod ove dve:
Srodni problemi uredi
- Algoritam deйkstrы rešava problem nalaženja jednog najkraćeg puta
- Bellman–Fordov algoritam rešava problem i kada su grane negativni brojevi.
- U pretragu u širinu algoritam se koristi za pretraživanje ograničeno sa dve operacije.
- Floid–Varshallov algoritam rešava najkraće puteve svih parova.
- Džonsonov algoritam rešava sve parove najkraćih puteva, i možda je brži nego Floid–Varshallov kada se primeni na razvijene grafove
- Teorija poremećaja pronalazi (u najgorem slučaju) lokalno najkraći put.
Vidi još uredi
- Problem najkraćeg puta
- Ograničen najkraći put
Reference uredi
- ^ Michael Günther et al.: “Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA”.
- ^ a b v Eppstein, D. (1998). „Finding the K shortest paths”. SIAM J. Comput. 28 (2): 652—673. doi:10.1137/S0097539795290477.
- ^ a b v Yen, J. Y (1971), „Finding the K-Shortest Loopless Paths in a Network”, Management Science, 17: 712—716
- ^ Xu, W., He, S., Song, R., & Chaudhry, S. (2012).
Spoljašnje veze uredi
- Implementacija algoritma jen
- The K-Shortest Paths Algorithm in C++
- Nekoliko objekata praćenje metod, pomoću k-najkraći put algoritam
- Bibtex po osnovu: http://www.ics.uci.edu/~эпштайна расположе/портикле/kpath.биб
- Računarski vid laboratorije
- Razni načini nalaženja putanja
- Shared Risk Group (SRG) i Shared Link Risk (SRLG)