Kapitola 13

Kombinatorická optimalizace

Tři příklady

Pohyb robotu ve skladu

Popis skladu, popis robotu (poloha a směr), příkazy (vykonání každého příkazu trvá 1 vteřinu),

START: pokud robot stojí, začne se pohybovat v přímém směru a urazí vzdálenost 0,5m, po vykonání příkazu je v pohybu,

MOVE(x): pokud je robot v pohybu, pokračuje v pohybu v přímém směru do vzdálenosti x metrů, po vykonání příkazu je v pohybu, x může nabývat hodnot x = 1, 2, 3,

STOP: pokud je robot v pohybu, začne ve stejném směru zpomalovat a během 0,5m se zastaví,

TURN(dir): pokud robot stojí, otočí se o 90^{o} ve směru dir, který může nabývat hodnot +, což znamená otočení proti směru hodinových ručiček, a −, která znamená otočení po směru hodinových ručiček, po vykonání příkazu robot opět stojí.

Pomocí těchto příkazů můžeme naprogramovat pohyb robotu po skladu. Příklad dvou různých programů pro pohyb mezi dvěma stejnými místy. Hledáme pohyb, který trvá nejkratší možnou dobu. Horní odhad (mez) a dolní odhad (mez) pro celkovou dobu trvání přesunu.

Horní odhad získáme tak, že ukážeme příklad pohybu. Najít nějaký dolní odhad je složitější.

Tvrzení 13.1 Má-li počáteční poloha robotu souřadnice (i, j), v ní je robot otočený jižním směrem, a konečná poloha robotu má souřadnice (k, l), kde k > i a l > j, pak nejkratší cesta trvá aspoň

6 + ⌈\frac{k − i − 1}{3}⌉ + ⌈\frac{l − j − 1}{3}⌉

vteřin. Symbol ⌈x⌉, kde x je reálné číslo, označuje nejmenší celé číslo větší nebo rovné x.

Důkaz. Na přednášce. □

Matenatický model úlohy

Orientovaný graf, vrcholy možné polohy robotu, hrany odpovídají změnám polohy robotu po jednom příkazu. Vrcholy grafu jsou trojice (i, j, dir), kde dir ∈ {N, S, E, W } a i, j jsou čísla tvaru t/2, kde t je přirozené číslo. Velikost čísel i, j je dána velikostí skladu. Můžeme například předpokládat, že 1 ≤ i ≤ 49 a 1 ≤ j ≤ 79, pokud má sklad velikost 50 × 80 metrů.

Hrany určené jednotlivými příkazy popíšeme následovně. Napřed příkaz START:

(i, j, N) ⟶ (i, j + 1/2, N), i ∈ {1, 2, …, 49}, j ∈ {1, 2, …, 78}, (i, j, S) ⟶ (i, j − 1/2, S), i ∈ {1, 2, …, 49}, j ∈ {2, 3, …, 79}, (i, j, E) ⟶ (i + 1/2, j, E), i ∈ {1, 2, …, 48}, j ∈ {1, 2, …, 79}, (i, j, W) ⟶ (i − 1/2, j, W), i ∈ {2, 3, …, 49}, j ∈ {1, 2, …, 79}.

Některé z těchto hran nemusí existovat, pokud jsou v okolí bodu o souřadnicích (i, j) nějaké překážky.

Příkaz TURN(+) vede k následujícím hranám.

(i, j, N) ⟶ (i, j, W), i ∈ {1, 2, …, 49}, j ∈ {1, 2, …, 79},

(i, j, W) ⟶ (i, j, S), i ∈ {1, 2, …, 49}, j ∈ {1, 2, …, 79},

(i, j, S) ⟶ (i, j, E), i ∈ {1, 2, …, 49}, j ∈ {1, 2, …, 79},

(i, j, E) ⟶ (i, j, N), i ∈ {1, 2, …, 49}, j ∈ {1, 2, …, 79}.

Podobně můžeme vypsat hrany pro všechny ostatní příkazy. Některé hrany nebudou do grafu zařazené kvůli překážkám ve skladu. Řešení úlohy spočívá v nalezení nejkratší orientované cesty v grafu např. mezi počátečním vrcholem (i, j, S) a koncovým vrcholem (k, l, W).

Erdösovo číslo

Matematická formulace opět spočívá v tom, že máme nějaký neorientovaný graf. Jeho vrcholy jsou jednotliví vědci (matematici), dva vrcholy jsou spojené hranou, pokud tito dva vědci napsali společný vědecký článek. Najít Erdösovo číslo e(X) nějakého matematika X znamená najít nejkratší cestu v tomto grafu z vrcholu E odpovídajícího P. Erdösovi do vrcholu odpovídajícího badatelovi X. Horní odhad Erdösova čísla e(X) najdeme tak, že ukážeme nějakou cestu z vrcholu E do vrcholu X. Dokázat dolní odhad čísla e(X) je mnohem obtížnější.

Ideální štafeta

Štafetový závod v běhu sestává ze 14 úseků různé délky a obtížnosti. Máme k dispozici 14 běžců, ze kterých máme sestavit ideální štafetu, tj. přiřadit jim jednotlivé úseky podle jejich výkonnosti tak, aby celkový čas byl co nejmenší. Můžeme to udělat tak, že v rámci tréninku necháme vždy všechny členy týmu uběhnout každý úsek štafety a změříme jejich čas. Výsledky tréninků můžeme zapsat do čtvercové matice A = (a_{ij}) řádu 14, kde číslo a_{ij} je čas, kterého dosáhl běžec i na úseku j. Naším úkolem je vybrat z matice A 14 prvků tak, abychom z každého řádku vybrali jedno číslo (každý člen týmu běží nějaký úsek) a z každého sloupce jedno číslo (každý úsek štafety běží pouze jeden člen týmu) tak, aby jejich součet byl co nejmenší.

Také tuto úlohu můžeme formulovat pomocí grafů. Vrcholy grafu G budou množina I členů týmu a množina J úseků běhu. Mezi každým vrcholem i ∈ I a vrcholem j ∈ J bude neorientovaná hrana. Tato hrana bude ohodnocena číslem a_{ij}, které bude znamenat dobu, jakou trvalo při tréninku běžci i uběhnout úsel j. Hledáme perfektní párování v grafu G, tj. množinu hran F, tak aby z každého vrcholu grafu G vycházela právě jedna hrana množiny F, pro kterou je souhodnot hran z F co nejmenší.

Také v tomto případě je jednoduché najít některý horní odhad času, který potřebuje ideální štafeta k proběhnutí celé trasy. Najdeme jakékoliv perfektní párování a sečteme hodnoty hran, které do tohoto párování patří. Dolní odhad můžeme najít například tak, že sečteme nejkratší časy, kterých členové týmu dosáhli na jednotlivých úsecích.

Hledání nejkratší cesty v grafu Prohledávání grafu do šířky Máme graf G = (V, E) (orientovaný nebo neorientovaný), V je množina

vrcholů a E je množina hran. První algoritmus pro nalezení nekratší cesty z daného vrcholu s ∈ V do libovolného jiného vrcholu v ∈ V se nazývá prohledávání grafu do šířky, anglicky breadth-first search, zkráceně BFS. Budeme potřebovat jednu další datovou strukturu queue Q, česky fronta, kterou je v každém okamžiku nějaká posloupnost

Q = v_{1}, v_{2}, …, v_{r}

vrcholů grafu (V, E). Fronta Q bude inicializována vložením jednoho vrcholu Q := s.

Kromě toho lze s datovou strukturou Q provádět tři operace. head(Q) vrátí první vrchol v_{1} fronty Q = v_{1}, v_{2}, …, v_{r}, enqueue(Q) přidá nový vrchol v jako poslední prvek ke Q, dequeue(Q) odebere první prvek v_{1} z Q = v_{1}, v_{2}, …, v_{r}. Algoritmus BFS systematicky prohledává graf G gtak, že pro každé při-

rozené číslo k napřed probere všechny vrcholy, které jsou ve vzdálenosti k od vrcholu s, než najde jakýkoliv vrchol ve vzdálenosti k + 1 od s.

Po ukončení algoritmu údaj d[v] pro v ∈ V obsahuje délku nějaké nejkratší cesty z vrcholu s do vrcholu v, a pro každé v ≠ s hodnota π[v] obsahuje předchůdce v v nějaké nejkratší cestě z s do v, případně se rovná NIL, pokud žádná taková cesta neexistuje. Algoritmus BFS rovněž označí každý vrchol v v okamžiku, kdy se s ním poprvé setká. To zapíšeme jako mark v.

Algoritmus BFS(G=(V,E),s)

FOR u ∈ V \ {s} DO d[u] := ∞

π[u] := NIL

END mark s d[s] := 0 Q := s WHILE q ≠ ∅ DO

u := head(Q)

FOR all v such that (u, v) ∈ E DO IF v not marked THEN

mark v

d[v] := d[u] + 1
π[v] := u
enqueu(Q, v)

END END dequeue(Q)

END

Napřed odhadneme dobu trvání algoritmu pomocí několika drobných pozorování. Každý vrchol je připojen do fronty Q nejvýše jednou ihned poté, co je označen, proto cyklus WHILE proběhne nejvýše |V |-krát. Operace s frontou Q, tj. head(Q), enqueue(Q, v) a dequeue(Q), vyžadují každá konstantní dobu. Proto celková doba provádění operací mimo cyklus FOR uvnitř WHILE cyklu se rovná O(|V |). Uvnitř tohoto FOR cyklu zpracováváme každou hranu (u, v) ∈ E nejvýše jednou. Doba, kterou vyžaduje zpracování jedné hrany je konstantní, čili průběh FOR cyklu vyžaduje čas O(|E|). Platí proto

Lemma 13.2 Algoritmus BFS vyžaduje čas O(|V | + |E|).

Vzdálenost mezi vrcholy s, v ∈ V v grafu G, tj. počet hran v nejkratší cestě mezi vrcholy s a v označíme δ(s, v).

Lemma 13.3 Platí δ(s, v) ≤ d[v] pro každý vrchol v ∈ V.

Důkaz. Algoritmus BFS najde nějakou cestu mezi vrcholy s a v ≠ s délky d[v], vrcholy této cesty v opačném pořadí jsou

v, π[v], π[π[v]], …, s.

Proto δ(s, v) ≤ d[v] pro libovolný vrchol v ∈ V, v ≠ s. Dokazovaná neorvnost platí rovněž v případě v = s, neboť d[s] = 0. □

Lemma 13.4 Předpokládejme, že v nějakém okamžiku průběhu algoritmu BFS fronta Q = v_{1}, v_{2}, …, v_{r}. Potom platí

• existuje přirozené číslo l takové, že d[l] ∈ {l, l + 1} pro každé i = 1, 2, …, r,

• d[v_{i}] ≤ d[v_{i+1} ] pro libovolné i = 1, 2, …, r − 1.

Důkaz. Budeme postupovat indukcí podle počtu operací enqueue a dequeue. Na počátku je Q = s a tvrzení očividně platí.

Nyní předpokládejme, že v průběhu algoritmu je Q = v_{1}, v_{2}, …, v_{r} a fronta Q splňuje obě podmínky. Operace dequeue je zachová. Pokud uděláme operaci enqueue(Q, v) v případě, že d[v_{1}] < d_{[}v_{r}], pak d[v] = d[v_{1}]+1 = d[v_{r}] a obě vlastnosti z tvrzení lemmatu platí. Pokud d_{[}v_{1}] = d_{[}v_{r}] = l, pak d[v] = d[v_{1}] + 1 = l + 1 a obě tvrzení lemmatu jsou opět splněná. □

Věta 13.5 Po skončení algoritmu BFS platí pro každý vrchol v ∈ V, že δ(s, v) = d[v].

Důkaz. Budeme postupovat indukcí podle δ(s, v). Je-li δ(s, v) = 0, platí v = s a d[s] = 0. Protože se v průběhu algoritmu hodnota d[v] nemění pro žádný vrchol v ∈ V, platí rovněž na konci algoritmu d[s] = 0 = δ(s, s).

Předpokládejme nyní, že δ(s, v) = k > 0 a že tvrzení věty platí pro všechny vrcholy u ∈ V, pro které je δ(s, u) < k. Musí existovat vrchol u ∈ V takový, že δ(s, u) = k − 1 a (u, v) ∈ E. Je to vrchol předcházející v v libovolné cestě z vrcholu s do vrcholu v, která má nejkratší možnou délku. Označme u_{0} první z těchto vrcholů u, který se objeví ve frontě Q. Každý z těchto vrcholů u se musí objevit ve frontě Q, protože podle indukčního předpokladu platí d[u] = δ(s, u) = k − 1, proto hodnota d[u] = k − 1 byla v průběhu algoritmu stanovena a ihned poté byl vrchol u přidán do Q.

Pokud vrchol v nebyl označen v okamžiku, kdy se vrchol u_{0} stal prvním členem fronty Q, dostaneme d[v] = d[u_{0}] + 1 = k a důkaz je dokončen. Může se stát, že v okamžiku, kdy se vrchol u_{0} stal prvním členem fronty Q, byl už vrchol v označen? V takovém případě by byl vrchol v označen v okamžiku, kdy byl nějaký jiný vrchol u_{1} na prvním místě fronty Q a existovala by hrana (u_{1}, v). V takovém případě by muselo platit δ(s, u_{1}) < δ(s, u_{0}) = k−1, neboť vrchol u_{0} byl první mezi vrcholy u, ze kterých vede hrana do vrcholu v a pro které platí δ(s, u) = k − 1. Potom by ale platilo δ(s, v) = δ(s, u_{1}) + 1 < k, což je spor s předpokladem δ(s, v) = k. Tento spor dokazuje, že vrchol v je ve skutečnosti neoznačen v okamžiku, kdy se u_{0} stal prvním členem posloupnosti Q. □

Dijkstrův algoritmus

V tomto případě budeme předpokládat, že hrany grafu G = (V, E) jsou ohodnocené nezápornými reálnými čísly, kterým říkáme váha hrany (u, v). Budeme ji označovat w(u, v) nebo také w(e), je-li e = (u, v). Je-li

p : u = u_{0}, u_{1}, …, u_{r} = v

nějaká cesta z vrcholu u do vrcholu v v grafu G, pak číslo

w(p) = ∑_{i=1}^{r−1}w(u_{i}, u_{i+1} )

nazýváme váhou cesty p. Vzdáleností δ(u, v) nazýváme nejmenší váhu všech cest z vrcholu u do vrcholu v v grafu G. V případě, že w(e) = 1 pro každou hranu e ∈ E, je vzdálenost δ(u, v) prostě počtem hran v nejkratší cestě z vrcholu u do vrcholu v v grafu G = (V, E).

Dijkstrův algoritmus počítá vzdálenost δ(u, v) mezi libovolnými dvěma vrcholy grafu G = (V, E), ve kterém má každá hrana e ∈ E přiřazenou nezápornou váhu w(e). Stejně jako v případě BFS algoritmu po skončení Dijkstrova algoritmu známe pro každý vrchol v ∈ V hodnotu d[v], váhu nejkratší cesty z nějakého pevně zvoleného vrcholu s ∈ V do vrcholu v.

Dále je výstupem Dijkstrova lagoritmu vrchol π[v], který předchází vrchol v v nějaké cestě s nejmenší váhou z vrcholu s do vrcholu v. Narorozdíl od algoritmu BFS se hodnota d[v] může v průběhu Dikstrova lagoritmu měnit.

Také Dijkstrův algoritmus bude využívat datovou strukturu–frontu Q, která bude posloupností nějakých vrcholů grafu G uspořádaných podle současné velikosti funkce d od nejmenší po největší. Můžeme zjišťovat, je-li fronta Q prázdná. S frontou Q můžeme dělat dvě operace:

• extract min(Q) odstraní z Q vrchol s nejmenší hodnotou d[v] mezi všemi vrcholy fronty Q,

• decrease key(Q, v, ρ), která stanoví novou hodnotu d[v] = ρ, pokud pro původní hodnotu d[v] platilo d[v] < ρ.

Dijkstrův algoritmus postupně vytváří množinu vrcholů S, pro které už byla nejkratší cesta z vrcholu s nalezena. Tato množina je na počátku prázdná a postupně se zvětšuje.

Dijkstra(G, s)

FOR u ∈ V DO d[u] := ∞

π[u] := NIL

END

d[s] := 0

S := ∅

Q := V

WHILE Q ≠ ∅ DO u := extract min(Q) S := S ∪ {u} FOR všechny v ∈ V takové, že (u, v) ∈ E DO IF d[v] > d[u] + w(u, v) THEN

d[v] := d[u] + w(u, v)
π[v] := u
decrease key(Q, v, d[v])

END END

END

Lemma 13.6 Dijkstrův algoritmus vyžaduje čas O(|V |^{2} + |E|).

Důkaz. V cyklu FOR uvnitř cyklu WHILE zpracováváme každou hranu (u, v) ∈ E nejvýše jednou. Proto cyklus FOR vyžaduje celkem čas O(|E|). Při každém průběhu cyklu WHILE odstraníme z fronty Q jeden vrchol, celkový počet průběhů cyklu WHILE se tak rovná |V |. Při každém průběhu musíme najít vrchol v ∈ Q s nejmenší hodnotou d[v]. To vyžaduje prohlédnout všechny vrcholy fronty Q, která má nejvýše |V | prvků. Toto prohlížení vyžaduje čas O(|V |). Celkem tedy WHILE cyklus vně cyklu FOR vyžaduje čas O(|V |^{2}). Celkem tak Dijkstrův algoritmus vyžaduje čas O(|V |^{2} + |E|). □

Věta 13.7 V okamžiku, kdy je v Dijkstrově algoritmu vrchol v zařazen do množiny S, platí rovnost d[v] = δ(s, v). Po skončení Dijkstrova algoritmu tak pro každý vrchol v platí d[v] = δ(s, v).

Důkaz. Budeme postupovat sporem. Předpokládejme, že existuje vrchol u ∈ V, pro který v okamžiku zařazení do množiny S platí d[u] ≠ δ(s, u). Buď u_{0} první vrchol, pro který v okamžiku zařazení do S platí d[u_{0}] ≠ δ(s, u_{0}). Potom platí

• u_{0} ≠ s,

neboť s je první vrchol zařazený do S a to v okamžiku, kdy d[s] = 0 = δ(s, s). Dále platí, že

• existuje nějaká cesta z s do vrcholu u_{0} v grafu G,

protože v opačném případě by platilo δ(s, u_{0}) = ∞ = d[u_{0}] v okamžiku zařazení u_{0} do množiny S.

Uvažujme nyní nejkratší cestu z s do u_{0}. Protože platí s ∈ S a zatím u_{0} ∉ S, existuje v této cestě první vrchol y, pro který platí y ∉ S. Jeho předchůdce označíme x. Protože x ∈ S, platí d[x] = δ(s, x) protože u_{0} byl první vrchol, pro který v okamžiku zařazení do S platila nerovnost d[u_{0}] ≠ δ(s, u_{0}).

Dále si uvědomme, že nějaká nejkratší cesta z s do y musí procházet vrcholem y. (V opačném případě by totiž bylo možné zkrátit zvolenou nejkratší cestu z s do u_{0} procházející vrcholem x.) To ale znamená, že

δ(s, y) = δ(s, x) + w(x, y) = d[x] + w(x, y).

V okamžiku zařazení x do množiny S bzyla ale hodnota d[y] upravena na d[y] := d[x] + w(x, y) = δ(s, y), pokud již d[y] tuto hodnotu neměla.

To znamená

d[y] = δ(s, y) ≤ δ(s, u_{0}) ≤ d[u_{0}],

neboť každá hrana má nezápornou váhu a protože d[u_{0}] je v každém okamžiku horním odhadem pro vzdálenost δ(s, u_{0}).

Naopak platí d[u_{0}] ≤ d[y], neboť u_{0} a y nejsou v tomto okamžiku prvky S a vrchol u_{0} byl vybrán pro zařazení do S z fronty Q, protože hodnota d[u_{0}] byla menší nebo rovná d-hodnotě libovolného jiného vrcholu z fronty Q. Tím je dokázána rovnost d[u_{0}] = d[y] = δ(s, u_{0}), což je ve sporu s výběrem vrcholu u_{0}. □