Back

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




                                     

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

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

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

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

                                     

1. Историја

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

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

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

                                     

2. Алгоритам

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

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

Прва опција

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

                                     

2.1. Алгоритам Прва опција

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

                                     

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

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

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

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

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

                                     

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

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

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

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

                                     

3.1. Неки примери и опис Пример #1

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

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

                                     

3.2. Неки примери и опис Пример #2

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

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

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

                                     

3.3. Неки примери и опис Пример #3

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

                                     

4. Апликације

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

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

5. Варијације

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

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

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

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

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

  • Неколико објеката праћење метод, помоћу к-најкраћи пут алгоритам
  • Разни начини налажења путања
  • Рачунарски вид лабораторије
  • Bibtex по основу: эпштайна расположе/портикле/kpath.биб
  • Схаред Риск Гроуп СРГ и Схаред Линк Риск СРЛГ
  • Имплементација алгоритма јен
  • The K-Shortest Paths Algorithm in C++