N ej kratší cesty □ Nejkratší cesty ■ Algoritmus Bellmana a Forda ■ Acyklické grafy ■ Dijkstrův algoritmus ■ Lineární nerovnice o 9. května 2016 1/42 N ej kratší cesty Formulace problému nej kratších cest Cesta v grafu cesta v grafu G — (V, E) je posloupnost vrcholů p = (vq, v\, ..., Vk) taková, že (vi-i, Vi) G E pro i = 1,..., k jednoduchá cesta je cesta, která neobsahuje dva stejné vrcholy terminologie cesta jednoduchá cesta path simple path walk path sled cesta p — (vo, vi,..., Vk) je cestou z vrcholu u do vrcholu v právě když vo = u a Vk = v v je dosažitelný z u, u v BM 9. května 2016 2 / 42 Formulace problému nej kratších cest Délka cesty graf G — (V, E), váhová funkce (ohodnocení, délka hran) w : E —)► M délka cesty p — (vq, vi, ..., Vk) je součet délek hran cesty k i=l délka nejkratší cesty z vrcholu u do vrcholu v je definovaná předpisem nejkratší cesta z vrcholu u do vrcholu v je libovolná cesta p z ^ do i; pro kte w(p) — S(u, v) pro neohodnocené grafy se délka cesty definuje jako počet hran cesty 9. května 2016 N ej kratší cesty Formulace problému nej kratších cest Varianty problému nejkratší cesty nejkratší cesty z daného vrcholu do všech vrcholů single source shortest path, SSSP tato přednáška nejkratší cesty ze všech vrcholů do daného vrcholu pro neorientované grafy totožné s SSSP pro orientované grafy redukce na SSSP změnou orientace hran nejkratší cesta mezi danou dvojicí vrcholů speciální případ SSSP, nejsou známy asymptoticky rychlejší algoritmy než pro SSSP tato přednáška nejkratší cesty mezi všemi dvojicemi vrcholů řešení opakovanou aplikací algoritmu pro SSSP existují efektivnější algoritmy ADS II nejdelší, nejširší, nejspolehlivější ... cesty viz literatura o 9. května 2016 4 / 42 N ej kratší cesty Formulace problému nej kratších cest Algoritmy pro SSSP orientované grafy neohodnocený graf průzkum do šírky, BFS acyklický graf průzkum do hloubky tato přednáška graf s nezáporným ohodnocením hran Dijkstrův algoritmus a jiné tato přednáška obecný graf algoritmus Bellmana Forda a jiné tato přednáška o 9. května 2016 5 / 42 N ej kratší cesty Formulace problému nej kratších cest Algoritmy pro SSSP neorientované grafy neohodnocený graf ■ průzkum do šírky, BFS graf s nezáporným ohodnocením hran ■ hranu nahradíme dvojici orientovaný hran a převedeme na úlohu v orientovaném grafu obecný graf ■ nahrazením hrany se záporným ohodnocením dvojicí orientovaných hran vznikne cyklus záporné délky ■ pokud původní graf obsahuje hrany záporné délky, ale žádný cyklus záporné délky, lze takovou úlohu převést na hledání nej levnějšího perfektního párování ■ když obsahuje cyklus záporné délky, problém je NP-těžký a umíme ho řešit pouze algoritmy exponenciální složitosti ■ viz literatura BM 9. května 2016 6 / 42 N ej kratší cesty Formulace problému nej kratších cest Nejkratší cesta vs nejkratší jednoduchá cesta graf neobsahuje hrany záporné délky mezi každou dvojicí vrcholů existuje nejkratší cesta, která je jednoduchá nechť p je nejkratší cesta, která není jednoduchá, tj. obsahuje cyklus ■ cyklus nemůže mít zápornou délku (spor s předpokladem neexistence hran záporné délky ■ cyklus nemůže mít kladnou délku (spor s předpokladem, že cesta je nejkratší ■ cyklus má nulovou délku - cyklus můžeme z cesty vypustit a dostaneme jednoduchou nejkratší cestu o 9. května 2016 7 / 42 N ej kratší cesty Formulace problému nej kratších cest Nejkratší cesta vs nejkratší jednoduchá cesta graf obsahuje hrany záporné délky ■ cyklus (b, c, d, b) má délku -2 ■ jestliže nějaká cesta z x do y obsahuje cyklus záporné délky, tak žádná cesta z x do y nemůže být nejkratší cestou, ô(x,y) — —oo v případě, že graf obsahuje hrany se zápornou délkou, problém nejkratší cesty je formulovaný jako 1. rozhodni, zda graf obsahuje cyklus záporné délky 2. když ne, tak najdi nejkratší (jednoduché) cesty 9. května 2016 8 / N ej kratší cesty Formulace problému nej kratších cest Struktura nejkratších cest Lemma 1 Každá podcesta nej kratší cesty je nej kratší cestou. ■ nechť p je nej kratší cesta z u do v w(P) w(PUX) + w(pxy) + w(Pyy) ■ předpokládejme, že existuje kratší cesta z x do y, w{p'xy) < w(p i , . / Pux Pxy Pyv m zkonstruujeme novou cestu p —u^x^y^v W{pr) w(PUX) + w(pxy) + w(pyv) < w(Pux) + ™(Pxy) + ™(Pyv) — w(p) což je spor s předpokladem, že p je nejkratší cesta z u do v N ej kratší cesty Generický SSSP algoritmus Reprezentace nejkratších cest strom nejkratších cest pozor na rozdíl mezi stromem nejkratších cest a nej levnější kostrou grafu o 9. května 2016 10 / 42 N ej kratší cesty Generický SSSP algoritmus Reprezentace stromu nejkratších cest z vrcholu s atribut vzdálenost distance, v.d • iniciální nastavení v.d = oo • hodnota v.d se v průběhu výpočtu snižuje • hodnota v.d je horním odhadem délky nej kratší cesty, v.d > S(s,v) • na konci výpočtu je v.d — v) atribut předchůdce parent, v.tt • iniciální nastavení v.tv = Nil • vrchol v.tv je předchůdcem vrcholu v na cestě z s do v délky v.d • na konci výpočtu je v.tt předchůdce vrcholu v na nejkratší cestě z s do v, resp. v.tt — Nil když neexistuje cesta z s do i; graf předchůdců Gp = (VpiEp) je definovaný hodnotami .tt Vp = {v G V | i;.7r 7^ Nil} U {5} = {(v.tt, v) \v eVp\ {s}} strom nejkratších cest na konci výpočtu je Gp stromem nejkratších cest • s je kořen stromu, Vp je množina vrcholů dosažitelných z vrcholu s • pro každý vrchol v G Vp, (jediná) cesta z s do v v Gp je nejkratší cestou z s do v v G 9. května 2016 11 / N ej kratší cesty Generický SSSP algoritmus Relaxace ■ technika, kterou využívají algoritmy pro hledání nejkratších cest ■ relaxací hrany (u, v) rozumíme test, zda je možné zkonstruovat kratší cestu do v tak, že projedeme přes vrchol u ■ když aktuálně známá cesta do vrcholu u prodloužená o hranu (u,v) je kratší než aktuálně známá cesta do v (u.d + w(u,v) < v.d), tak jsme našli novou -kratší cestu do v a podle toho aktualizujeme hodnoty v.d a v.tt {y.d u.d + w(u, v) a v.tt <(— u ) u v Relax Relax ■ hranu (u, v) nazýváme napjatou právě když u.d + w(u,v) < v.d o 9. května 2016 12 / N ej kratší cesty Generický SSSP algoritmus Generický SSSP algoritmus lnit_SSSP(G,s) 1 foreach v E V do v.d oo; v.tt Nil od 2 s.d u.d + w(u, v) 7 then Relax(í/, v, w) 8 S * • • • —>* v.7t.7t —>* v.7t —>* v ■ když žádná hrana grafu není napjatá, tak cesta s —)►••• v.tt.tt —>► v.tt —>► v je nejkratší cestou z s do v důkaz indukcí na počet relaxací důsledek: když výpočet generického algoritmu skončí, tak Gp je strom nej kratších cest o 9. května 2016 14 / 42 N ej kratší cesty Generický SSSP algoritmus Složitost generického SSSP algoritmu závisí od toho ■ jakou datovou strukturu použijeme pro reprezentaci množiny S obsahující vrcholy určené k prozkoumání (tj. vrcholy, u kterých byla změněna hodnota .ď) ■ v jakém pořadí budeme prozkoumávat vrcholy z množiny S o 9. května 2016 15 / 42 N ej kratší cesty Algoritmus Bellmana a Forda Bellmanův - Fordů v algoritmus ■ pro reprezentaci množiny vrcholů určených k prozkoumání využíva frontu (FIFO) ■ pro přehlednější analýzu složitosti a důkaz korektnosti rozdělujeme výpočet do iterací; v jedné iteraci se relaxují všechny hrany grafu Bellman-Ford(G, w, s) 1 Init_SSSP(G,s) 2 for i = 1 to \V\ — 1 do s foreach (u, v) £ E do 4 if v.d > u.d + w(u, v) then Relax(i/, v, w) fi 5 od 6 od 7 foreach (u, v) G E do 8 if v.d > u.d + 1^(1/, v) then return Falše fi 9 od i o return True o 9. května 2016 16 / 42 (d) (e) výpočet algoritmu Bellman-Ford, hledáme nejkratší cesty z vrcholu a v každé iteraci cyklu 2-6 relaxujeme hrany v pořadí (c, e), (d, e), (6, d), (c, d), (6, c), (a,c), (a, 6) barevně jsou vyznačeny hrany grafu předchůdců Gp BM 9. května 2016 17 / 42 N ej kratší cesty Algoritmus Bellmana a Forda Korektnost 1 Lema 2 Když graf G neobsahuje cyklus záporné délky dosažitelný z s, tak po \V\ — 1 iteracích cyklu 3-5 pro všechny vrcholy v platí v.d = v). nechť v je dosažitelný z s a nechť p = (vq, v\, ..., Vk) je nejkratší jednoduchá cesta z s do v (vq = s, vj~ — v) protože cesta p neobsahuje cyklus, má nanejvýš \V\ — 1 hran, tj. k < \V\ — 1 v každé iteraci cyklu se relaxují všechny hrany grafu, speciálně • v první iterace se relaxuje hrana (vo,vi) • v druhé iteraci se relaxuje hrana (^1,^2) • v k-té iteraci se relaxuje hrana (vk-i,Vk) indukcí ověříme, že po z-té iteraci platí Vi.d — ô(s, vi) o 9. května 2016 18 / 42 N ej kratší cesty Algoritmus Bellmana a Forda Korektnost 2 Lema 3 Když graf G neobsahuje cyklus záporné délky dosažitelný z s, tak algoritmus vráti hodnotu True. ■ po ukončení výpočtu platí pro každou hranu (u, v) G E v.d = S(s,v) < 5(5, u) + w(u, v) — u.d + w(u,v) m žádná hrana není napjatá a test na řádku 8 nevrátí hodnotu False o 9. května 2016 19 / 42 N ej kratší cesty Algoritmus Bellmana a Forda Korektnost 3 Lema 4 Když graf G obsahuje cyklus záporné délky dosažitelný z s, tak algoritmus vráti hodnotu False. ■ nechť c = (vq, v\, ..., Vk), vq = vj~ je cyklus záporné délky dosažitelný z s, ■ předpokládejme, že algoritmus vráti hodnotu True, tj. pro každou hranu cyklu platí vi.d < Vi-i.d + w(ví-i, v i) ■ sumací přes všechny vrcholy cyklu k k k k i—\ i=l i=l i=l ■ každý vrchol se vyskytuje právě jednou v součtech Yli=i vi-i-d a Yli=i vi-d m k k k ^2vi-!.d = ^2vi.d => 0 < y^w^j-^Vj) i—\ i=l i=l ■ spor s předpokladem o délce cyklu c 9. května 2016 20 / N ej kratší cesty Algoritmus Bellmana a Forda Složitost složitost algoritmu Bellmana a Forda ■ inicializace má složitost Q (V) ■ relaxace hrany má konstantní složitost ■ cyklus 3 - 5 má složitost Q (E); počet jeho opakování je V — 1 ■ celková složitost je OiVE) jiný zápis: 0(mn), kde n je počet vrcholů a m je počet hran grafu existuje efektivnější řešení? ne lehce najdeme graf a takové pořadí relaxace jeho hran, pro které je nutných V — 1 iterací 111 otázka vhodného pořadí relaxace hran ano vhodné pořadí hran dokážeme určit pro speciální typy grafů • acyklické grafy • grafy bez záporných hran o 9. května 2016 21 / 42 Nejkratší cesty v orientovaném acyklickém grafu ■ optimálně pořadí relaxace hran v Bellmanově - Fordově algoritmu je takové, že vždy relaxujeme hranu (u,v) pro kterou u.d — ô(s,u) ■ pro obecný graf určit pořadí relaxací tak, aby byla dodržena uvedená podmínka, může být stejně náročné jako vypočíst nejkratší cesty ■ speciálně pro acyklické grafy se toto pořadí dá vypočíst jednoduše: požadovanou vlastnost má topologické uspořádání vrcholů grafu A u.d + w(u, v) then Relax(i/, v, w) fi 6 od 7 od ■ časová složitost Q(V + E) ■ topologické uspořádání garantuje, že hrany každé cesty jsou relaxované v pořadí, v jakém se vyskytují na cestě 9. května 2016 Dijkstrův algoritmus ■ pro reprezentaci množiny vrcholů určených k prozkoumání využívá prioritní frontu, kde priorita vrcholu v je určena hodnotou v.d ■ Dijkstrův algoritmus můžeme nahlížet i jako efektivní implementaci prohledávání grafu do šířky, na rozdíl od BFS neukládáme vrcholy, které mají být prozkoumané, do fronty, ale do prioritní fronty ■ řeší problém SSSP pro grafy s nezáporným ohodnocením hran o 9. května 2016 24 / 42 N ej kratší cesty Dijkstrův algoritmus Dijkstrův algoritmus Dijkstra(G, w, s) 1 Init_SSSP(G,s) 2 S ^0 3 Q 4r- V 4 while Q ^ 0 do 5 u f- Extract_Min((5) 6 S^Su{u} 7 foreach (u, v) G E do 8 if v.d > u.d + w(u, v) then Relax(í/, v, w) fi 9 od i o od ■ algoritmus udržuje dvě množiny S vrcholy, pro které je již vypočtena délka nej kratší cesty Q prioritní fronta, Q = V \ S ■ algoritmus vybírá vrchol u £ Q s nejmenší hodnotou u.d a relaxuje hrany vycházející z u o 9. května 2016 25 / 42 N ej kratší cesty Dijkstrův algoritmus Dijkstrúv algoritmus - príklad vrcholy se přidávají do množiny S v pořadí s, y, z, x Korektnost Lema 5 (Invariant cyklu while) Na začátku iterace while cyklu platí v.d — ô(s, v) pro všechny vrcholy v G S. Inicializace na začátku S — 0 a tvrzení platí triviálně Ukončení na konci Q = 0, tj. S = V a v.d = v) pro všechny v E V Iterace potřebujeme prokázat, že když u přesuneme do S, tak u.d — S(u.s) ■ když u není dosažitelný z 5 tak tvrzení platí protože u.d — ô(s, u) — oo ■ v opačném případě nechť p je nejkratší cesta z s do u\ cestu p můžeme dekomponovat na dvě cesty s x —)► y ^ tak, že bezprostředně před zařazením ^ do 5 všechny vrcholy cesty pi patří do 5 a y ^ 5 ■ x G £ x.d = x) ■ při zařazení x do 5 byla relaxovaná hrana (x, y)) a 5 ^> x —)► y je nejkratší cesta do y =^> y.d = ô(s, y) ■ hrany mají nezápornou délku =^> ô(s,y) < ô(s,u) ■ v dané iteraci jsme vybrali vrchol u =^> u.d < y.d ■ spojením dostáváme u.d < y.d — ô(s, y) < ô(s, u) =^> u.d < ô(s, u) BM 9. května 2016 27 / 42 N ej kratší cesty Dijkstrův algoritmus Složitost Dijkstrova algoritmu Q (V) operací Insert (do fronty přidá nový objekt) Q(V) operací Extract_Min (z fronty odstraní objekt s minimálním klíčem) Q (E) operací DecreaseJKey (objektu ve frontě sníží hodnotu klíče) složitost algoritmu závisí od způsobu implementace prioritní fronty Q pole složitost Q(V -V + E - í) = Q(V2) Insert má složitost 6(1) Extract_Min má složitost 6(V) DecreaseJKey má složitost 6(1) binární halda složitost 6(V log V + E log V) Insert má složitost Q (log V) Extract_Min má složitost Q (log V) DecreaseJKey má složitost Q (log V) Fibonacciho halda složitost 6(VlogV + E) Insert má složitost 6(1) Extract JVIin má složitost Q (log V) Decrease_Key má složitost 6(1) o 9. května 2016 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Optimalizace Dijkstrova algoritmu pro hledání nejkratší cesty mezi dvěma vrcholy s a t optimalizace 1 výpočet ukončíme když vrchol t odebereme z prioritní fronty 0 9. května 2016 29 / 42 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Optimalizace Dijkstrova algoritmu pro hledání nejkratší cesty mezi dvěma vrcholy sat optimalizace 2 - dvousměrné hledání (bidirectional search) ■ současně spouštíme (dopředný) výpočet Dijkstrova algoritmu z vrcholu s a (zpětný) výpočet z vrcholu t, vždy jednu iteraci každého výpočtu ■ dopředný výpočet používá frontu Q f a přiřazuje vrcholům hodnoty .df a .717, zpětný frontu Qt a přiřazuje hodnoty .db a .tt^ ■ výpočet ukončíme když nějaký vrchol w je odstraněn z obou front QfaQb ■ po ukončení najdeme vrchol x s minimální hodnotou x.df + x.d^ (pozor, nemusí to být vrchol w) ■ využitím atributů .717 a .tt^ najdeme nejkratší cestu z s do x a nejkratší cestu z x do t; jejich spojením dostaneme nejkratší cestu z s do t o 9. května 2016 30/4 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Optimalizace Dijkstrova algoritmu pro hledání nejkratší cesty mezi dvěma vrcholy s a t optimalizace 3 - heuristika A* ■ pokud bychom dovedli spolehlivě zjistit, že nejkratší cesta z s do t nepovede přes vrchol v, mohli bychom zpracování vrcholu v a hran s ním incidentních přeskočit pracovali bychom s menší grafem, a tedy rychleji ■ jestliže dva vrcholy jsou stejně daleko od s, chceme při průzkumu preferovat ten, který je blíže k cílovému vrcholu t ■ pro odhad preferencí používáme ohodnocení vrcholů - potenciál h : V —>* M ■ Dijkstrův algoritmus s heuristikou se od klasického liší v tom, že při výběru vrcholu z prioritní fronty vybíráme vrchol s nejnižší hodnotou v.d + h{v) ■ jak volit potenciál a proč může urychlit výpočet? o 9. května 2016 31 / Nejkratší cesta mezi dvěma vrcholy Heuristika A* - přípustný potenciál Potenciál je přípustný právě když pro každou hranu (u,v) £ E splňuje podmínku h{u) < w(u, v) + h{y) a pro vrchol t platí h{t) — 0. ■ pro libovolnou cestu p = (vq = u, v\,..., Vk = t) z u do t b přípustný potenciál platí k-l > h(v0) - h(vi) + h(vi) - h(v2) + ... + h{yk-i) - h(vk) — h{u) — h{t) — h{u) t.j. potenciál vrcholu u je dolním odhadem délky cesty z u do t o 9. května 2016 32 / 42 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Heuristika A* - úprava ohodnocení grafu pomoci potenciálu ■ vytvoríme nové ohodnocení grafu w' : E —>* M, které definujeme jako w'(u, v) — w(u, v) — h{u) + h{v) ■ když h je přípustný potenciál, tak pro nové ohodnocení grafu a pro každou hranu grafu platí w'(u, v) > 0 t.j. pro výpočet nejkratších cest můžeme použít Dijkstrův algoritmus ■ nové ohodnocení wf nemění nejkratší cesty, protože pro každou cestu p z s do t platí wř(p) — w(p) + h{t) — h(s) a potenciálový rozdíl medzi s a t je pro všechny cesty zsdot stejný o 9. května 2016 33 / 42 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Heuristika A* - úprava ohodnocení grafu pomoci potenciálu ■ aby hodnoty h měly příznivý vliv na rychlost výpočtu, měli by hodnoty h(v) být dolním odhadem vzdálenosti z vrcholu v do cílového vrcholu t\ čím je odhad přesnější, tím je výpočet rychlejší ■ Dijkstrův algoritmus s heuristikou se od klasického liší v tom, že při výběru vrcholu z prioritní fronty vybíráme vrchol s nejnižší hodnotou v.d + h{v) ■ za předpokladu, že ohodnocení vrcholů h splňuje pro všechny hrany (x,y) grafu podmínku w(x,y) > h(x) — h(y), Dijkstrův algoritmus s heuristikou je korektní důkaz probíhá analogicky jako pro Dijkstrův algoritmus o 9. května 2016 34 / N ej kratší cesty Dijkstrův algoritmus a obecné grafy graf se záporně ohodnocenými hranami ale bez cyklů záporné délky ■ algoritmus najde korektní řešení (po každé změně hodnoty u.d vrátime vrchol u do fronty) ■ složitost výpočtu může být až exponenciální vůči velikosti grafu ■ v praxi někdy rychlejší než algoritmus Bellmana a Forda graf s cykly záporné délky ■ výpočet algoritmu není konečný o 9. května 2016 35 / 42 N ej kratší cesty Lineární nerovnice Úloha lineárního programování pro danou m x n matici A a vektory b — (6i,..., bm) a c — (ci,..., cn) najít vektor x = (xi,... , xn) G MJ1, který optimalizuje hodnotu účelové funkce X^ľ=i c*x* P^' SP'n^n 1 ohraničení Ax < b příklad minimalizovat — 2xi — 3x2 — X3 při splnění ohraničení —x\ — x2 — X3 < 3 3xi + 4x2 - 2x3 < 10 2xi - 4x2 < 2 4xi — x2 + X3 < 0 xi, x2, x3 > 0 přípustné řešení (0, 0, 0) optimální řešení (0, 5, 5) o 9. května 2016 36 / 42 N ej kratší cesty Lineární nerovnice Úloha lineárního programování význam • mnoho problémů dokážeme vyjádřit jako úlohu lineárního programování (např. problém nej kratší cesty) • pro řešení těchto problémů potom stačí použít algoritmus pro řešení úlohy lineárního programování1 algoritmická složitost • existují polynomiální algoritmy pro řešení úlohy lineárního programování • pro řešení speciálních případů úlohy lineárního programování existují mnohem rychlejší algoritmy • problém lineárních ohraničení je příkladem takovéto speciální úlohy • ukážeme postup založený na SSSP viz kurz IA101 Algoritmika pro těžké problémy 0 9. května 2016 37 / 42 Problém lineárních nerovnic ■ je daná množina nerovnic tvaru xi — Xj < bk, kde x jsou proměnné, 1 <, z, j < n b jsou konstanty, 1 < k < m ■ úkolem je najít takové hodnoty proměnných x, které splňují všechny nerovnice (tzv. přípustné řešení; v případě, že neexistuje žádné přípustné řešení, tak výstupem je Falše příklad X\ — X2 < 5 X\ — Xs < 6 < - 1 < - ■2 X4. — X\ < - 3 přípustné řešení x — (0, —4, —5, —3) 9. května 2016 38 / 42 N ej kratší cesty Lineární nerovnice Graf lineárních nerovnic ohodnocený, orientovaný graf G — (V, E) ■ V = {v0,vi,... ,vn} (jeden vrchol pro každou proměnnou plus vrchol vq) m E — {(ví, v j) | x j — Xi