Određivanje k-najkraćih puteva

S Vikipedije, slobodne enciklopedije

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 | uredi izvor]

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 | uredi izvor]

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
  • Pu: putanja od s Do u
  • B gomila strukture podataka koja sadrži putanje
  • P: skup najkraćih putanja od s do t
  • countu: broj najkraćih putanja do čvor u

Algoritam:

*P =prazno,
*countu = 0 za sve u u V
ubacite put Ps = {S} u B sa cenom 0
dok B nije prazno i countt < K:
– neka je Pu najmanja cena puta B sa cenom C
– B = B − {Pu }, countu = countu + 1
– ako je u = t , onda  P = P U Pu
– akocountu ≤ K onda
  • za svaki čvor v susedan čvoru u:
– ako v nije u  Pu onda
– neka Pv  bude novi put sa cenom C + w(u,v) formiran nadovezivanjem grane (u, v) na put Pu
ubacite Pv U B
vrati P

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

Prva opcija[uredi | uredi izvor]

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

Druga opcija[uredi | uredi izvor]

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 | uredi izvor]

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 | uredi izvor]

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 | uredi izvor]

Primer #1[uredi | uredi izvor]

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.

15-čvorna mreža, koja sadrži kombinaciju dvosmernih i jednosmernih grana

Primer #2[uredi | uredi izvor]

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 | uredi izvor]

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 | uredi izvor]

Određivanje K-najkraćih putanja je dobra alternativa za:

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

Varijacije[uredi | uredi izvor]

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[uredi | uredi izvor]

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ Michael Günther et al.: “Symbolic calculation of K-shortest paths and related measures with the stochastic process algebra tool CASPA”.
  2. ^ a b v Eppstein, D. (1998). „Finding the K shortest paths”. SIAM J. Comput. 28 (2): 652—673. doi:10.1137/S0097539795290477. 
  3. ^ a b 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).

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Одређивање_к-најкраћих_путева&oldid=27755654”