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

Одређивање 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- број најкраћих путања које треба наћи P_u: путања од s До u B гомила структуре података која садржи путање P: скуп најкраћих путања од s до t count_u: број најкраћих путања до чвор u Алгоритам: P =празно, count_u = 0 за све u у V убаците пут P_s = {S} у B са ценом 0 док B није празно и count_t < K: – нека је P_u најмања цена пута B са ценом C – B = B − {P_u }, count_u = count_u + 1 – ако је u = t , онда P = P U P_u – акоcount_u ≤ K онда за сваки чвор v суседан чвору u: – ако v није у P_uонда – нека P_v буде нови пут са ценом C + w(u,v) формиран надовезивањем гране (u, v) на пут P_u убаците P_v У B врати P

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

Прва опција

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

Друга опција

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

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

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

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

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

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

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

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

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

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

Неки примери и опис

Пример #1

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

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

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

Пример #2

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

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

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

Пример #3

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

Апликације

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

Планирање географског пута
Мрежно рутирање, посебно за оптичке мреже , где постоје и додатна ограничења, који не могу бити решена уз помоћ обичног алгоритма за најкраће путање.
Формирање хипотеза у области рачунарске лингвистике
Редослед поређења и тражење метаболичких путањи у биоинформатици
Праћење неколико објеката

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

Варијације

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

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

Сродни проблеми

Алгоритам дейкстры решава проблем налажења једног најкраћег пута

Беллман–Фордов алгоритам решава проблем и када су гране негативни бројеви.
У претрагу у ширину алгоритам се користи за претраживање ограничено са две операције.
Флоид–Варсхаллов алгоритам решава најкраће путеве свих парова.

Џонсонов алгоритам решава све парове најкраћих путева, и можда је бржи него Флоид–Варсхаллов када се примени на развијене графове

Теорија поремећаја проналази (у најгорем случају) локално најкраћи пут.

Види још

Проблем најкраћег пута
Ограничен најкраћи пут

Референце

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

Спољашње везе

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

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

[Yen-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).

[1]

[2]

[3]

[4]