Kontrakcija hijerarhija

U primenjenoj matematici, metod kontrakcija hijerarhija je tehnika efikasnog rešavanja problema najkraćeg puta u grafu prvo kreiranjem kontrahovane verzije povezanog grafa. Može se smatrati posebnim slučajem „autoput-čvor putanja“ pristupa.

Kontrakcija hijerarhija može se koristiti za generisanje najkraćeg puta u grafu mnogo efikasnije nego Dijkstrin algoritam ili prethodni pristup autoput-čvor putanja, i koristi se u mnogim naprednim tehnikama za usmeravanje.To je javno dostupan softver za izračunavanje putanje od jednog do drugog mesta.

Algoritam

Ovaj algoritam ima dve faze: pretprocesiranje početnog grafa (što može potrajati više od sat vremena) i ispitivanje (manje od sekunde). Kontrakcija hijerarhija je specijalan slučaj hijerarhije pristupa, koja generiše hijerarhiju višeslojnog čvora u fazi pretprocesiranja. U KH svaki čvor grafa je predstavljen kao da je i sam nivo hijerarhije. Ovo se može postići na različite načine: jedan jednostavan način je da se označi svaki čvor numerisanjem od 1 do |N|. Sofisticiraniji pristup je proceniti vrstu puta (autoput protiv manjeg puta itd.).

Pretprocesiranje

Poredak čvorova u KH može biti proizvoljan. Suština je da se grane prečice uvode kada je potrebno. Da bi se razumelo kad su prečice potrebne, mora se razumeti algoritam pretrage. Algoritam pretrage (dvosmerni Dijkstrin algoritam) u ovom slučaju je ograničen tako da samo uklanja grane koje su povezane za čvorove koji su viši u KH od trenutnog čvora u jednom pravcu, i obrnuto. Sa ovim ograničenjem, algoritam neće naći određene najkraće puteve u neobrađenoj mreži, i zbog toga moramo uvesti nove grane u grafu koje predstavljaju postojeće najkraće puteve koje algoritam ne uzima u obzir. Nema potrebe da svi najkraći putevi budu obnovljeni kao grane prečice: dovoljno je da se uzmu u obzir susedni čvorovi nekih čvorova koji su viši u KH (dok je deo nekog najkraćeg puta i sam najkraći put). Algoritmički:

• Dodaj nivo na čvorove grafa

• Za svaki čvor, poštujući naredbe, uzmi njegove susedne čvorove višeg reda i ispitaj da li najkraći put između svakog para od njih prolazi kroz trenutni čvor i ako prolazi, dodaj granu prečicu.

Recimo da uzmemo u obzir samo dva susedna čvora (od njih n):

Sa ove slike, ako najkraći put od v do w prolazi kroz čvor u koji je manji u KH, nova grana mora biti dodata u KH graf tako da najkraći putevi koje algoritam pretrage uzima u obzir budu sačuvani.

Težina nove grane jednaka je rastojanju puta od v do w.

Kada je pretprocesiranje početnog grafa završeno, imamo KH graf koji se sastoji od početnog grafa sa čvorovima dodatim naredbama i sa uključenim granama prečicama.

Ispitivanje

Za traženi algoritam, koristi se dvosmerni Dijkstrin algoritam. To je klasičan Dijkstrin algoritam sa nekim modifikacijama. Algoritam pretrage od početnog čvora u jednom pravcu i od krajnjeg čvora u drugom pravcu (ovo je klasičan dvosmerni Dijkstrin algoritam), ali on uklanja grane koje su usmerene ka hijerarhijski višim čvorovima u jednom pravcu (u suštini širi se ka hijerarhijski višim čvorovima) i grane koje su usmerene ka hijerarhijski nižim čvorovima u drugom pravcu. Ako najkraći put postoji, ove dve pretrage će se sresti na istom čvoru v. Najkraći put od s do t sastoji se od puteva od s do v i od v do t.

Najkraći putevi pronađeni ovim algoritmom imaju određen oblik:

$<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$

Put pronađen ispitivanjem je najkraći put zbog faze pretprocesiranja. U fazi pretprocesiranja mi transformišemo graf uključivanjem grana prečica, koje predstavljaju najkraći put koji algoritam ne uzima u obzir.

Da bi se dobio krajnji rezultat, grane prečice treba da prođu kroz pretprocesiranje da bi se dobili stvarni putevi koje predstavljaju u početnom grafu.

Da bi pokazali da ovaj algoritam pronalazi najkraće puteve, razmotrimo to kontradikcijom: pretpostavimo da postoji put koji je kraći od onog koji smo našli ovim algoritmom:

Recimo da u nekom momentu postoji put koji je kraći od onog koji smo pronašli algoritmom. Pošto se algoritam širi ka čvorovima višeg reda, poredak $u_{k}$ čvora mora biti manji od reda $u_{k-1}$ i $u_{k+1}$ čvorova. Zbog te činjenice, u fazi pretprocesiranja taj put će biti predstavljen kao grana prečica sa jednakom dužinom, i samim tim ne postoji put koji je kraći od onog pronađenog algoritmom.