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

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

Dajkstrin algoritam može biti generalizovan kako bi se pronašlo K-najkraćih puteva.

Definicije: G(V, E): težinski usmereni graf, sa skupom čvorova V i skupom direktnih grana E, w(u,v): cena direktne grane od čvora u ka čvoru v (cene su nenegativne). Veze koje ne zadovoljavaju ograničenja najkraće putanje su uklonjeni iz grafa s: izvorni čvor t: krajnji čvor K- broj najkraćih putanja koje treba naći P_u: putanja od s Do u B gomila strukture podataka koja sadrži putanje P: skup najkraćih putanja od s do t count_u: broj najkraćih putanja do čvor u Algoritam: P =prazno, count_u = 0 za sve u u V ubacite put P_s = {S} u B sa cenom 0 dok B nije prazno i count_t < K: – neka je P_u najmanja cena puta B sa cenom C – B = B − {P_u }, count_u = count_u + 1 – ako je u = t , onda P = P U P_u – akocount_u ≤ K onda za svaki čvor v susedan čvoru u: – ako v nije u P_uonda – neka P_v bude novi put sa cenom C + w(u,v) formiran nadovezivanjem grane (u, v) na put P_u ubacite P_v U B vrati P

Postoje u osnovi dve opcije algoritma za traženje K-najkraćih puteva:

Prva opcija

U prvoj varijanti, putevi ne moraju biti bezciklučni David Eppsteinov algoritam obezbeđuje najbolje vreme.^[2]

Druga opcija

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

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

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 2n² dodataka i n² 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

Primer #1

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

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

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

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

Put mreže: raskrsnice su čvorovi i svaka grana (link) grafa povezuje dva čvora (raskrsnice).

Varijacije

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:

U prvoj varijaciji, ciklusi su dozvoljeni, odnosno dozvoljeno je da put prođe kroz isti čvor više puta. Sledeći dokumenti su saglasni sa ovom varijacijom.^[2]
Druga promena se odnosi na jednostavne puteve. Takođe se zove bezciklično određivanje K-najkraćih putanja i pripisuje se Ju Jenu^[3]

Srodni problemi

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š

Problem najkraćeg puta
Ograničen najkraći put

Reference

^ 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

[1] Michael Günther et al.: “Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA”.

[EppsteinFinding-2] v Eppstein, D. (1998). „Finding the K shortest paths”. SIAM J. Comput. 28 (2): 652—673. doi:10.1137/S0097539795290477.

[Yen-3] v Yen, J. Y (1971), „Finding the K-Shortest Loopless Paths in a Network”, Management Science, 17: 712—716

[4] Xu, W., He, S., Song, R., & Chaudhry, S. (2012).

[1]

[2]

[3]

[4]