Контракција хијерархија

У примењеној математици, метод контракција хијерархија је техника ефикасног решавања проблема најкраћег пута у графу прво креирањем контраховане верзије повезаног графа. Може се сматрати посебним случајем „аутопут-чвор путања“ приступа.

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

Алгоритам

Овај алгоритам има две фазе: претпроцесирање почетног графа (што може потрајати више од сат времена) и испитивање (мање од секунде). Контракција хијерархија је специјалан случај хијерархије приступа, која генерише хијерархију вишеслојног чвора у фази претпроцесирања. У КХ сваки чвор графа је представљен као да је и сам ниво хијерархије. Ово се може постићи на различите начине: један једноставан начин је да се означи сваки чвор нумерисањем од 1 до |Н|. Софистициранији приступ је проценити врсту пута (аутопут против мањег пута итд.).

Претпроцесирање

Поредак чворова у КХ може бити произвољан. Суштина је да се гране пречице уводе када је потребно. Да би се разумело кад су пречице потребне, мора се разумети алгоритам претраге. Алгоритам претраге (двосмерни Дијкстрин алгоритам) у овом случају је ограничен тако да само уклања гране које су повезане за чворове који су виши у КХ од тренутног чвора у једном правцу, и обрнуто. Са овим ограничењем, алгоритам неће наћи одређене најкраће путеве у необрађеној мрежи, и због тога морамо увести нове гране у графу које представљају постојеће најкраће путеве које алгоритам не узима у обзир. Нема потребе да сви најкраћи путеви буду обновљени као гране пречице: довољно је да се узму у обзир суседни чворови неких чворова који су виши у КХ (док је део неког најкраћег пута и сам најкраћи пут). Алгоритмички:

• Додај ниво на чворове графа

• За сваки чвор, поштујући наредбе, узми његове суседне чворове вишег реда и испитај да ли најкраћи пут између сваког пара од њих пролази кроз тренутни чвор и ако пролази, додај грану пречицу.

Рецимо да узмемо у обзир само два суседна чвора (од њих н):

Са ове слике, ако најкраћи пут од в до w пролази кроз чвор у који је мањи у КХ, нова грана мора бити додата у КХ граф тако да најкраћи путеви које алгоритам претраге узима у обзир буду сачувани.

Тежина нове гране једнака је растојању пута од в до w.

Када је претпроцесирање почетног графа завршено, имамо КХ граф који се састоји од почетног графа са чворовима додатим наредбама и са укљученим гранама пречицама.

Испитивање

За тражени алгоритам, користи се двосмерни Дијкстрин алгоритам. То је класичан Дијкстрин алгоритам са неким модификацијама. Алгоритам претраге од почетног чвора у једном правцу и од крајњег чвора у другом правцу (ово је класичан двосмерни Дијкстрин алгоритам), али он уклања гране које су усмерене ка хијерархијски вишим чворовима у једном правцу (у суштини шири се ка хијерархијски вишим чворовима) и гране које су усмерене ка хијерархијски нижим чворовима у другом правцу. Ако најкраћи пут постоји, ове две претраге ће се срести на истом чвору в. Најкраћи пут од с до т састоји се од путева од с до в и од в до т.

Најкраћи путеви пронађени овим алгоритмом имају одређен облик:

$<s=u_{0},u_{1},...,u_{p}=v,...,v_{q}=t>,p,q\in \mathbb {N}$

$u_{i}<u_{i+1},i\in \mathbb {N} ,i<p$

$u_{j}>u_{j+1},j\in \mathbb {N} ,p\leq j<q$

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

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

Да би показали да овај алгоритам проналази најкраће путеве, размотримо то контрадикцијом: претпоставимо да постоји пут који је краћи од оног који смо нашли овим алгоритмом:

Рецимо да у неком моменту постоји пут који је краћи од оног који смо пронашли алгоритмом. Пошто се алгоритам шири ка чворовима вишег реда, поредак $u_{k}$ чвора мора бити мањи од реда $u_{k-1}$ и $u_{k+1}$ чворова. Због те чињенице, у фази претпроцесирања тај пут ће бити представљен као грана пречица са једнаком дужином, и самим тим не постоји пут који је краћи од оног пронађеног алгоритмом.