Bellmanův princip optimality + Bellmanova rovnice
Prerekvizity: [L2.1] Záporné váhy ano, záporné cykly ne — od teď v celé kapitole standardně předpokládáme graf bez záporných cyklů (víme už, proč: jinak je úloha NP-těžká). V této lekci si odvodíme strukturální vlastnost, díky které jde vzdálenosti počítat, místo abychom je hledali probíráním všech cest.
Proč nestačí „projít všechny cesty“
Vzdálenost $l(s,w)$ jsme v [L2.1] definovali jako délku nejkratší $s$–$w$ cesty — a taky jsme si ukázali, že nejkratší cesta vždy existuje (když je $w$ dosažitelný). Definice ale neříká nic o tom, jak ji najít.
Zkus sám: kolik různých $s$–$w$ cest může mít graf s $n$ vrcholy? Stačil by „hrubou silou“ výčet všech cest?
Až exponenciálně mnoho. Stačí si představit „řetěz diamantů“: $s$ → (nahoru nebo dolů) → spoj → (nahoru nebo dolů) → spoj → … → $w$. Každý diamant zdvojnásobí počet cest, takže $k$ diamantů dá $2^k$ cest. Výčet všech cest je tedy beznadějný — potřebujeme strukturální vlastnost, která dovolí skládat vzdálenosti z menších vzdáleností, bez probírání cest.
Podcesta nejkratší cesty je sama nejkratší
Vezmi nejkratší cestu $P$ z $s$ do $w$ a označ její poslední hranu $e = (v, w)$. Když hranu $e$ odstřihneš, zbude začátek cesty — z $s$ do $v$.
Zkus sám: může být ten zbylý začátek z $s$ do $v$ „špatný“, tj. ne-nejkratší $s$–$v$ cesta?
Intuice říká, že ne — a zdůvodnění je výměnný argument (sporem): kdyby existovala kratší $s$–$v$ cesta $Q$, vyměníme začátek — vezmeme $Q$ a přilepíme hranu $e=(v,w)$. Dostaneme spojení z $s$ do $w$ kratší než $P$, což je spor s tím, že $P$ je nejkratší.
Jeden háček tu ale je: co když $Q$ prochází přes $w$? Pak $Q + e$ opakuje vrchol $w$ — není to cesta, ale jen sled [L0.3], a sled nejkratší cestu „nepřebije“ jen tak. Přesně tady do hry vstoupí předpoklad bez záporných cyklů — viz důkaz níže.
Slidy tuhle vlastnost vyslovují obecně pro libovolný vrchol na nejkratší cestě (nejen předposlední) — říká se jí optimal substructure (optimální podstruktura):
Mějme graf bez záporných cyklů. Pokud nejkratší cesta z $s$ do $w$ obsahuje vrchol $v$, pak její úsek z $s$ do $v$ je nejkratší $s$–$v$ cesta, úsek z $v$ do $w$ je nejkratší $v$–$w$ cesta a platí $$l(s,w) = l(s,v) + l(v,w).$$
Věta přesně: Bellmanův princip optimality
Přesná formulace ze slidu 13 je o kousek jemnější — počítá hrany. Značení: $P^k$ je nejkratší mezi všemi $s$–$w$ cestami s nejvýše $k$ hranami a $P^{k}[s,v]$ znamená úsek cesty $P^k$ od $s$ do $v$.
Mějme digraf $G$, váhy $c : E(G) \to \mathbb{R}$, bez záporných cyklů. Nechť $k \in \mathbb{N}$ a $s$, $w$ jsou dva vrcholy. Nechť $P^k$ je nejkratší mezi všemi $s$–$w$ cestami s nejvýše $k$ hranami a $e = (v,w)$ jeho poslední hrana. Pak $P^{k-1}[s,v]$ (tj. $P^k$ bez hrany $e$) je nejkratší mezi všemi $s$–$v$ cestami s nejvýše $k-1$ hranami.
Zkus sám: proč se věta obtěžuje s počítáním hran („nejvýše $k$“), místo aby mluvila prostě o nejkratších cestách?
Dva důvody:
- Verze s počtem hran je silnější a obecnější: každá cesta má nejvýše $|V|-1$ hran, takže volbou $k \ge |V|-1$ dostaneš „obyčejnou“ verzi o nejkratších cestách zadarmo.
- Přesně v tomhle tvaru (po vrstvách „nejvýše $k$ hran“) větu později použijí algoritmy, které vzdálenosti budují postupným přidáváním hran — uvidíš to u Bellman-Forda [L2.12]; jeho důkaz korektnosti na této větě stojí a probereme ho až v [L3.7] Korektnost Bellman-Forda.
Důkaz sporem — dva případy
Předpokládejme pro spor, že existuje $s$–$v$ cesta $Q$ kratší než $P^{k-1}[s,v]$, s nejvýše $k-1$ hranami. Rozlišíme, jestli $Q$ prochází vrcholem $w$, nebo ne.
Zkus sám — případ 1: $Q_1$ je kratší než $P^{k-1}[s,v]$, má nejvýše $k-1$ hran a vrchol $w$ neobsahuje. Kde je spor?
Přilep hranu $e$ (slide 13):
$$c(E(Q_1)) \lt c(E(P^{k-1}[s,v])) \quad \ldots \text{ přičti } c(e)$$ $$c(E(Q_1)) + c(e) \lt c(E(P^{k-1}[s,v])) + c(e) = c(E(P^k))$$$Q_1$ neobsahuje $w$, takže $Q_1 + e$ je pořádná cesta z $s$ do $w$ — a má nejvýše $(k-1)+1 = k$ hran. Jenže je kratší než $P^k$, který byl mezi takovými cestami nejkratší. Spor. (Všimni si: tady jsme záporné cykly vůbec nepotřebovali.)
Zkus sám — případ 2: $Q_2$ vrchol $w$ obsahuje, takže $Q_2 + e$ není cesta. Jak spor zachránit — a kde se konečně použije „bez záporných cyklů“?
Rozstřihni $Q_2$ ve vrcholu $w$ na dva úseky (slide 14):
$$c(E(Q_2[s,w])) + c(E(Q_2[w,v])) \lt c(E(P^{k-1}[s,v])) \quad \ldots \text{ přičti } c(e)$$ $$c(E(Q_2[s,w])) + \underbrace{c(E(Q_2[w,v])) + c(e)}_{\ge\, 0} \lt \underbrace{c(E(P^{k-1}[s,v])) + c(e)}_{c(E(P^k))}$$Klíčový krok: úsek $Q_2[w,v]$ spolu s hranou $e=(v,w)$ tvoří cyklus ($w \to \dots \to v \to w$) — a graf nemá záporné cykly, takže jeho váha je $\ge 0$. Když člen $\ge 0$ vynecháme, nerovnost se jen zesílí:
$$c(E(Q_2[s,w])) \lt c(E(P^k))$$Jenže $Q_2[s,w]$ je $s$–$w$ cesta (úsek cesty $Q_2$) s nejvýše $k-1$ hranami — kratší než $P^k$. Spor. Tohle je přesně místo, kvůli kterému celá kapitola předpokládá grafy bez záporných cyklů: se záporným cyklem by se „objížďka přes $w$“ mohla vyplatit a princip optimality by padl (protipříklad si spočítáš v úloze T02).
Bellmanova rovnice
Princip optimality teď otočíme v návod na výpočet. Chci znát $l(s,w)$ a vím, že nejkratší cesta do $w$ musí do $w$ nějakou hranou přijít.
Zkus sám: poslední hrana nejkratší $s$–$w$ cesty vede z nějakého vrcholu $v$. Vyjádři $l(s,w)$ jen pomocí vzdáleností $l(s,v)$ a vah hran $c(v,w)$.
Dvě pozorování:
- Pro každý vrchol $v$ s hranou do $w$ platí $l(s,w) \le l(s,v) + c(v,w)$ — to je přesně důsledek trojúhelníkové nerovnosti z [L2.1] (cesta přes $v$ je jedna z možností).
- Pro vrchol $v$, ze kterého vede poslední hrana nejkratší cesty, platí podle principu optimality rovnost: $l(s,w) = l(s,v) + c(v,w)$.
Dohromady: $l(s,w)$ je minimum výrazu $l(s,v) + c(v,w)$ přes možné předchůdce $v$.
$$l(s,w) = \min_{v \ne w}\,\{\,l(s,v) + c(v,w)\,\}$$
platí, pokud graf neobsahuje záporný cyklus.
Jak číst: minimum běží fakticky přes předchůdce $w$ — pro neexistující hranu ber $c(v,w) = \infty$. Rovnice je vyslovena pro cílové vrcholy $w \ne s$; pro start klademe $l(s,s) = 0$ (prázdná cesta).
Vyzkoušej si rovnici na konkrétním vrcholu — známe vzdálenosti do všech předchůdců $w$ a krokujeme minimum:
Zkus sám: rovnice mluví o $l(s,v)$ — tedy o dalších neznámých. Není to definice kruhem? K čemu je rovnice, která vzdálenosti jen „svazuje mezi sebou“?
Je to soustava rovnic: jedna rovnice pro každý vrchol $w$, neznámé jsou všechny vzdálenosti $l(s,\cdot)$. A přesně tak na ni budeme nahlížet: algoritmy téhle kapitoly jsou různé strategie, jak soustavu vyřešit —
- Dijkstra [L2.4]: vyhodnocuje rovnice „od nejbližších vrcholů“ (potřebuje nezáporné váhy),
- Bellman-Ford [L2.12]: vyhodnocuje je opakovaně po vrstvách „nejvýše $k$ hran“ (zvládne záporné váhy),
- SP v DAG [L2.13]: vyhodnocí je v topologickém pořadí jedním průchodem,
- Floyd-Warshall [L2.14]: řeší rovnice pro všechny dvojice najednou.
Společný elementární krok všech čtyř — porovnání $l(w)$ s $l(v) + c(v,w)$ pro jednu hranu — se jmenuje relaxace hrany a je to přesně téma příští lekce [L2.3].
Pozor: „bez záporných cyklů“ není okrasná fráze- Bellmanova rovnice i princip optimality předpokládají graf bez záporného cyklu. Se záporným cyklem rovnice prostě neplatí — minimum na pravé straně „podleze“ skutečnou vzdálenost, protože odpovídá sledu, ne cestě (spočítáš v T02; souvisí s rozbitou trojúhelníkovou nerovností z [L2.1]).
- V důkazu se předpoklad používá jen v případu 2 (objížďka přes $w$ + poslední hrana = cyklus s váhou $\ge 0$). Když se na ústní zeptají „kde přesně důkaz potřebuje nezáporné cykly?“, tohle je odpověď.
Key takeaways — L2.2- Optimal substructure: nejkratší cesta se skládá z nejkratších segmentů — obsahuje-li nejkratší $s$–$w$ cesta vrchol $v$, je $l(s,w) = l(s,v) + l(v,w)$.
- Bellmanův princip optimality (přesná verze): je-li $P^k$ nejkratší $s$–$w$ cesta s nejvýše $k$ hranami a $e=(v,w)$ její poslední hrana, pak $P^{k-1}[s,v]$ je nejkratší $s$–$v$ cesta s nejvýše $k-1$ hranami. Důkaz sporem; předpoklad „bez záporných cyklů“ je potřeba jen v případě, kdy kratší objížďka prochází přes $w$.
- Bellmanova rovnice: $l(s,w) = \min_{v \ne w}\{\,l(s,v) + c(v,w)\,\}$ — platí v grafu bez záporného cyklu; „$\le$“ je trojúhelníková nerovnost, „$=$“ dosahuje předchůdce na nejkratší cestě.
- Tato vlastnost je důvod, proč fungují Dijkstra [L2.4], Bellman-Ford [L2.12], SP v DAG [L2.13] i Floyd [L2.14] — všechny jsou strategie řešení Bellmanovy rovnice; jejich společný lokální krok je relaxace hrany [L2.3].
Suppose we have digraph $G$, weights $c : E(G) \to \mathbb{R}$, no negative cycles. Let $k \in \mathbb{N}$, and let $s$ and $w$ be two vertices. Let $P^k$ be a shortest one among all $s$-$w$-paths with at most $k$ edges, and let $e = (v,w)$ be its final edge. Prove that $P^{k-1}[s,v]$ (i.e. $P^k$ without the edge $e$) is a shortest one among all $s$-$v$-paths with at most $k-1$ edges.
a) Co je v zadání?
Dokázat Bellmanův princip optimality v přesné formulaci s počtem hran: odstřihnutím poslední hrany nejkratší „$\le k$-hranové“ cesty vznikne nejkratší „$\le (k-1)$-hranová“ cesta do předposledního vrcholu. Na této větě stojí důkaz korektnosti Bellman-Forda (probereme v [L3.7]) a SP důkazy jsou u ústní/důkazového slotu oblíbené — klíčem je struktura sporu a místo, kde se použije předpoklad bez záporných cyklů.
b) Co k tomu budeme potřebovat?
- [L2.1] Záporné váhy ano, záporné cykly ne — záporný cyklus, rozdíl cesta vs. sled.
- [L0.3] Cesta, sled, tah, cyklus — slepení dvou cest nemusí být cesta.
- Tato lekce — výměnný argument a rozdělení na dva případy.
c) Jak nad úlohou uvažovat?
Jdi sporem: předpokládej kratší $s$–$v$ cestu $Q$ s nejvýše $k-1$ hranami. Přirozený tah je „přilep hranu $e$ a překonej $P^k$“ — ale ohlídej si, jestli $Q + e$ je vůbec cesta. To přirozeně rozdělí důkaz na dva případy podle toho, zda $Q$ obsahuje vrchol $w$. V druhém případě hledej v obrázku cyklus — a vzpomeň si, co o cyklech říká předpoklad věty.
d) Úplné řešení
Sporem. Nechť existuje $s$–$v$ cesta $Q$ s $|E(Q)| \le k-1$ a $c(E(Q)) \lt c(E(P^{k-1}[s,v]))$. Rozlišíme dva případy.
Případ 1: $Q_1$ neobsahuje $w$. Přičtením $c(e)$ k oběma stranám:
$$c(E(Q_1)) \lt c(E(P^{k-1}[s,v]))$$ $$c(E(Q_1)) + c(e) \lt c(E(P^{k-1}[s,v])) + c(e) = c(E(P^k))$$Protože $Q_1$ neobsahuje $w$, je $Q_1$ + $e$ regulérní $s$–$w$ cesta s nejvýše $(k-1)+1 = k$ hranami — a je kratší než $P^k$. To je spor s volbou $P^k$ (nejkratší mezi $s$–$w$ cestami s nejvýše $k$ hranami).
Případ 2: $Q_2$ obsahuje $w$. Rozdělíme $Q_2$ ve vrcholu $w$ na dvě části a přičteme $c(e)$:
$$c(E(Q_2[s,w])) + c(E(Q_2[w,v])) \lt c(E(P^{k-1}[s,v]))$$ $$c(E(Q_2[s,w])) + \underbrace{c(E(Q_2[w,v])) + c(e)}_{\ge\, 0} \lt \underbrace{c(E(P^{k-1}[s,v])) + c(e)}_{c(E(P^k))}$$Úsek $Q_2[w,v]$ spolu s hranou $e = (v,w)$ tvoří cyklus; graf nemá záporné cykly, takže označený součet je $\ge 0$ a lze ho z levé strany vypustit:
$$c(E(Q_2[s,w])) \lt c(E(P^k))$$Jenže $Q_2[s,w]$ je $s$–$w$ cesta s nejvýše $k-1$ hranami, tedy přípustný kandidát pro $P^k$ — a je kratší. Spor.
V obou případech spor ⟹ žádná kratší $Q$ neexistuje a $P^{k-1}[s,v]$ je nejkratší mezi $s$–$v$ cestami s nejvýše $k-1$ hranami. $\blacksquare$
Pointa k ústní: předpoklad „no negative cycles“ se použije pouze v případu 2 — zaručuje, že cyklus $Q_2[w,v] + e$ má nezápornou váhu.
Bellman's equation $l(s,w) = \min_{v \ne w} \{l(s,v) + c(v,w)\}$ holds if the graph does not contain a negative cycle. Consider the digraph with nodes $i$, $j$, $k$ and edges $(i,j)$ with weight $5$, $(i,k)$ with weight $6$, $(j,k)$ with weight $-1$, and $(k,j)$ with weight $-2$. Evaluate both sides of Bellman's equation for $s = i$ and $w = j$. Does the equation hold? Explain why.
a) Co je v zadání?
Stejný trojvrcholový graf, na kterém v [L2.1] (úloha T01) padla trojúhelníková nerovnost. Teď na něm máme vyhodnotit obě strany Bellmanovy rovnice pro $s=i$, $w=j$ a vysvětlit výsledek.
b) Co k tomu budeme potřebovat?
- Tato lekce — Bellmanova rovnice a její předpoklad „bez záporného cyklu“.
- [L2.1] — vzdálenost = délka nejkratší cesty; co dělá záporný cyklus se sledy.
c) Jak nad úlohou uvažovat?
Levá strana: spočti $l(i,j)$ výčtem cest (graf je maličký). Pravá strana: minimum běží přes $v \in \{i, k\}$ — nezapomeň na člen $v=i$ s $l(i,i)=0$. Až ti vyjdou různá čísla, ptej se: kterému spojení z $i$ do $j$ odpovídá hodnota pravé strany? Je to cesta?
d) Úplné řešení
Levá strana. $i$–$j$ cesty (tj. cesty z $s=i$ do $j$): přímá hrana $i \to j$ (délka $5$) a $i \to k \to j$ (délka $6 - 2 = 4$). Tedy $l(i,j) = 4$.
Pravá strana. Kandidáti $v \ne j$ s hranou do $j$:
- $v = i$: $\;l(i,i) + c(i,j) = 0 + 5 = 5$,
- $v = k$: $\;l(i,k) + c(k,j) = 4 + (-2) = 2$ (kde $l(i,k) = \min\{6,\; 5-1\} = 4$ po cestě $i \to j \to k$).
Minimum je $\min\{5, 2\} = 2$.
Závěr: $4 = l(i,j) \ne \min_{v \ne j}\{l(i,v) + c(v,j)\} = 2$ — rovnice neplatí. Nic jiného se čekat nedalo: graf obsahuje záporný cyklus $j \to k \to j$ s váhou $(-1) + (-2) = -3$, takže předpoklad rovnice je porušen.
Proč přesně to selhalo: hodnota $2$ na pravé straně odpovídá slepení nejkratší $i$–$k$ cesty ($i \to j \to k$) s hranou $(k,j)$. To ale není cesta — vrchol $j$ se opakuje. Je to sled $i \to j \to k \to j$, který obsahuje právě ten záporný cyklus; v důkazu principu optimality je to přesně případ 2, kde se bez nezáporného cyklu nelze obejít. Stejný mechanismus rozbil trojúhelníkovou nerovnost v [L2.1] T01 — všimni si, že porušený důsledek $l(i,j) \le l(i,k) + c(k,j)$ je přesně člen $v=k$ z Bellmanovy rovnice.