Одређивање к-најкраћих путева

С Википедије, слободне енциклопедије

Одређивање K-најкраћих путева је проширени алгоритам алгоритма најкраћег пута у датој мрежи.

Понекад је од кључног значаја да имате више од једног пута између два чвора у мрежи. У случају додатних ограничења, други путеви који се разликују од најкраће путање се могу израчунати. За проналажење најкраћих путања се могу користити  проблеми најкраћег пута , као што је Дајкстрин алгоритам или Беллман-Фордов алгоритам, а онда да их проширимо на проналажење више од једног пута. Одређивање к-најкраћих путева је генерализација проблема најкраћег пута . Алгоритам не само да проналази најкраћи пут, већ проналази и К-1 осталих путева у неопадајућем поретку њихових цена.

Проблем може бити ограничен на проналазак К најкраћих путева без петље (loopless) или са петљом.

Историја[уреди | уреди извор]

Од 1957. године било је доста чланака објављених на тему одређивање к-најкраћих путева. Већина радова, није била заснована на проблему налажења једног најкраћег пута између пара чворова, већ на налажење низа од К најкраћих путева, и ти радови су објављени од 1960. год до 2001. год. Од тада, већина новијих истраживања је у вези примене алгоритма и његових варијација. У 2010. години Мајкл Гинтер са сар. објавио је књигу о симболичком тражењу К-најкраћих путева .[1]

Важне радови о проблему одређивања к-најкраћих путева:

Година издања Аутор Име
1971 Јин  Јен Проналажење К К-најкраћих путева у мрежи
1972 М. т. Ардон и сар. Рекурзивни алгоритам за креирање шеме и повезани подграфови
1973 П. М. Камерини и др. К-најкраћих путева у стаблу графа
1975 К. Аихара Приступ проучавању основних путева
1976 Т. Д Ам ет сар. Алгоритам за генерисање свих путева између два чвора у диграфу и његова примена
1988 Равиндра К. Ахуджа сар. Брзи алгоритми за проблем најкражег пута
1989 С. Anily сар. Ранг листи најбољих бинарних стабала[мртва веза]
1990 Равиндра К. Бржи алгоритми за одређивање најкраћег пута
1993 Ел-Амин и сарадници Експертски систем за проналажење лиеарног пута
1997 Дејвид Еппстеин Проналажење К-најкраћих путева
1997 Инго Алтхофер  К-најбољи режим у компјутерском шаху
1999 Инго Алтхофер „Системи За Подршку Одлучивању Са Неколико Структуре Избор”. 
2011 Хусаин, Алјаззар, Стефан Леуе „К*: алгоритам за претрагу К-најкраћих путева”. doi:10.1016/j.artint.2011.07.003. 

BibTeX база садржи више чланака.

Алгоритам[уреди | уреди извор]

Дајкстрин алгоритам може бити генерализован како би се пронашло К-најкраћих путева.

Дефиниције:
  • G(V, E): тежински усмерени граф, са скупом чворова V и скупом директних грана Е,
  • w(u,v): цена директне гране од чвора у ка чвору в (цене су ненегативне).
Везе које не задовољавају ограничења најкраће путање су уклоњени из графа
  • s: изворни чвор
  • t: крајњи чвор
  • K- број најкраћих путања које треба наћи
  • Pu: путања од s До u
  • B гомила структуре података која садржи путање
  • P: скуп најкраћих путања од s до t
  • countu: број најкраћих путања до чвор u

Алгоритам:

*P =празно,
*countu = 0 за све u у V
убаците пут Ps = {S} у B са ценом 0
док B није празно и countt < K:
– нека је Pu најмања цена пута B са ценом C
– B = B − {Pu }, countu = countu + 1
– ако је u = t , онда  P = P U Pu
– акоcountu ≤ K онда
  • за сваки чвор v суседан чвору u:
– ако v није у  Pu онда
– нека Pv  буде нови пут са ценом C + w(u,v) формиран надовезивањем гране (u, v) на пут Pu
убаците Pv У B
врати P

Постоје у основи две опције алгоритма за тражење К-најкраћих путева:

Прва опција[уреди | уреди извор]

У првој варијанти, путеви не морају бити безциклучни Давид Еппстеинов алгоритам обезбеђује најбоље време.[2]

Друга опција[уреди | уреди извор]

Друга опција приписује се Јин Ју Јену, путеви морају бити безциклучни.[3] (Ово ограничење уводи додатни ниво тежине.) Јенов алгоритам се користи када се у питању просте путање, док се Еппстеинов алгоритам користи за непросте путев (пример када је дозвољено путу да прође кроз исти чвор више пута).

Путеви не морају да буду безциклични[уреди | уреди извор]

За све што треба, м - грана, н - број чворова.

Еппстеинов алгоритам даје најбоље резултате.[2] Еппстеинов модел налази К најкраћих дужина (дозвољавајући циклусе), повезујући два чвора у диграфу, за време o(m+ nlogn + к).

Еппстеинов  алгоритам користи  технику трансформације графа.

Овај модел такође може наћи К најкраћих путева из почетног чвора s до сваког чвора у графу, за време o(m + nlogn + kn).

Безциклични алгоритам за проналажење К-најкраћих путева [уреди | уреди извор]

Најбоље време за овај модел се приписује Јин. Ј. Јену.[3] Јенов алгоритам проналази дужине свих најкраћих путева из фиксног чвора до свих осталих чворова у ненегативној н-чворовној мрежи.

Овај метод захтева само 2n2 додатака и n2 поређења- што је мање од других доступних алгоритама.

Тренутно време је сложености o(Kn(m + nlogn)). m представља број грана, n - број чворова.

Неки примери и опис[уреди | уреди извор]

Пример #1[уреди | уреди извор]

У следећем примеру се користи Јенов модел да се пронађе прве К најкраћих путања између чворава који су повезани. То јест, он проналази први, други, трећи, итд све до К.-ог  најкраћег пута. Више информација можете наћи овде.

Код дат у овом примеру покушава да нађе К-најкраће путање мреже која има 15-чворова, који су повезани једносмерним и двосмерним гранама.

15-чворна мрежа, која садржи комбинацију двосмерних и једносмерних грана

Пример #2[уреди | уреди извор]

Други пример је употреба алгоритма према ком пратите неколико објеката.

Техника имплементира неколико објеката за праћење заснованих на алгоритму за К-најкраћих путања.

Све информације се могу наћи у "компјутерског вида лабораторији – CVLAB" .

Пример #3[уреди | уреди извор]

Још једна примена алгоритама за најкраће путање је пројектовање транзитне мреже, што повећава удобност корисника у транспортном превозу. Такав пример транзитне мреже може бити конструисан, стављајући на разматрање време путовања.  Поред времена путовања, могу се узети други услови у зависности од економских и географских ограничења. Без обзира на разлике у параметрима, алгоритам за одређивање К-најкраћих путовања проналази највише оптимална решења, задовољавајући готово све потребе корисника. Такве апликације за најкраћи пут алгоритми постају све чешће, у последње време Xu, He, Song and Chaudry (2012) проучавали су  проблеме К-најкраћих путева у транзитној мрежи. [4]

Апликације[уреди | уреди извор]

Одређивање К-најкраћих путања је добра алтернатива за:

  • Пут мреже: раскрснице су чворови и свака грана (линк) графа повезује два чвора (раскрснице).

Варијације[уреди | уреди извор]

Постоје две основне варијације на алгоритам за одређивање К-најкраћих путања као што смо горе поменули. Све остале варијације, спадају под ове две:

  • У првој варијацији, циклуси су дозвољени, односно дозвољено је да пут прође кроз исти чвор више пута. Следећи документи су сагласни са овом варијацијом.[2]
  • Друга промена се односи на једноставне путеве. Такође се зове безциклично одређивање К-најкраћих путања и приписује се Ју Јену [3]

Сродни проблеми[уреди | уреди извор]

Види још[уреди | уреди извор]

Референце[уреди | уреди извор]

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

Спољашње везе[уреди | уреди извор]

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