Stavový automat jako graf
Recept stav — přechod — cena z [L2.9] zůstává v platnosti. Mění se odpověď na první otázku: u pana Dow Jonese stačil jako stav rok, u řidiče autobusu hodina. Hlavolamy z přednášky — slidy je vedou pod hlavičkou SPT.automaton — potřebují víc: stav je celý „snímek“ situace. Ukážeme si to na odměřování vody (slide 26, zkouška 24. 5. 2011) a na převádění lidí přes most (slide 27).
Odměřování vody: co všechno musí být ve stavu
Stojíš u jezera s prázdnou 3litrovou a prázdnou 5litrovou lahví. Úkol: mít přesně 4 litry ve větší lahvi. Žádné rysky, žádné odhadování — povolené jsou jen tři druhy manipulací: napustit láhev z jezera po okraj, vylít láhev celou do jezera, přelít z jedné lahve do druhé (přeléváš, dokud se zdrojová nevyprázdní, nebo cílová nenaplní). Anglický originál zadání je v úloze T01 níže.
Zkus sám: recept začíná otázkou „co je stav?“. Jaká nejmenší informace tady určuje, co všechno můžeš udělat dál?
Dvojice $(x, y)$: $x \in \{0, \ldots, 3\}$ litrů v trojce, $y \in \{0, \ldots, 5\}$ litrů v pětce. Jedno číslo nestačí — které manipulace jsou povolené i jak dopadne přelití závisí na obou obsazích (jezero je nekonečné, to si pamatovat nemusíme). Stavů je nanejvýš $4 \cdot 6 = 24$ — konečně malý stavový prostor (state space).
Zkus sám: vypiš všechny tahy, které jdou udělat ze stavu $(3, 2)$.
Čtyři: napustit pětku $\to (3,5)$, vylít trojku $\to (0,2)$, vylít pětku $\to (3,0)$, přelít trojku do pětky (vejdou se všechny 3 litry) $\to (0,5)$. Napustit trojku ani přelít z pětky do trojky nejde — trojka je plná. Obecný stav má až 6 odchozích hran: 2× napustit, 2× vylít, 2× přelít.
Zkus sám: co je start a co cíl? Pozor, cíl je záludnější, než vypadá.
Start $s = (0,0)$. Cíl ale není jeden vrchol: „4 litry ve větší lahvi“ splňuje každý stav s $y = 4$, tedy množina $\{(0,4), (1,4), (2,4), (3,4)\}$. Hledáme nejkratší cestu z $s$ do nejbližšího z nich — buď spočítáme vzdálenosti do všech a vezmeme minimum, nebo elegantně přidáme super-cíl $t$ a hranu s cenou $0$ z každého cílového stavu do $t$. (Které cílové stavy jsou vůbec dosažitelné, předem nevíme — ukáže to až prohledávání.)
Tomu, co jsme právě postavili, se říká stavový automat (state automaton): množina stavů + pravidla přechodů. Zásadní rozdíl proti [L2.9]: graf není v zadání ani „schovaný“ v časové ose. Vyrábí se z pravidel — hranu poznáš tak, že na stav aplikuješ povolený tah. Vrcholy grafu jsou všechny dosažitelné stavy a které to jsou, zjistíš až průchodem.
Stejný automat, různé váhy
Zadání ze slidu 26 chce postupně tři různé věci — a všechny tři se řeší na témže grafu, jen s jinými cenami hran:
Zkus sám: jaké váhy zvolíš pro „nejmenší počet manipulací“?
Každá manipulace je jeden tah → $c(e) = 1$ pro všechny hrany. Délka cesty = počet manipulací.
Zkus sám: a pro „nejméně přemístěné vody“ a „nejméně vody vylité zpět do jezera“?
Cena hrany = objem vody, kterou daný tah přemístí (napuštění $3-x$ resp. $5-y$ litrů, vylití $x$ resp. $y$, přelití přelitý objem). Pro třetí otázku platí cenu jen hrany „vylít do jezera“ ($x$ resp. $y$ litrů), všechno ostatní má cenu $0$. Nuly nevadí — Dijkstra [L2.4] chce jen $c \ge 0$, ne $c > 0$.
| Otázka | Cena hrany (tahu) | Algoritmus |
|---|---|---|
| min. počet manipulací | $1$ za každý tah | Dijkstra; při jednotkových vahách zavírá stavy po „vlnách“ podle počtu tahů — tomu se říká prohledávání do šířky (breadth-first search, BFS) |
| min. přemístěná voda | objem přemístěný tahem | Dijkstra [L2.4] (váhy $\ge 0$) |
| min. voda vylitá do jezera | objem jen u „vylít“, jinak $0$ | Dijkstra (nulové váhy jsou povolené) |
Běh: vlna stavovým prostorem
Zkus sám (na papír, než pustíš krokování): najdi posloupnost manipulací, která skončí se 4 litry v pětce. Kolik tahů potřebuješ nejméně?
Jde to na 6 tahů: napustit pětku $(0,5)$, přelít do trojky $(3,2)$, vylít trojku $(0,2)$, přelít zbytek do trojky $(2,0)$, napustit pětku $(2,5)$, dolít trojku $(3,4)$. Že méně tahů nestačí, ukáže běh níže — vlna dorazí k prvnímu cílovému stavu přesně v 6. vrstvě.
Pusť si běh pro jednotkové váhy. Dijkstra s cenami $1$ zavírá stavy přesně po vrstvách „dosažitelné na $k$ tahů“ — sleduj, jak se vlna šíří a jak se stavový prostor teprve při běhu vynořuje z pravidel:
Stejný princip poběží i v příští lekci [L2.11] Časově expandovaná síť (constrained SP) — časově expandovaná síť je také stavový automat, jen se stavem „(kde jsem, kolik je hodin)“.
Pozor: tři pasti stavových automatů- Stav nese méně, než musí. U mostu (úloha T02) nestačí pamatovat si, kdo už přešel — bez polohy baterky model dovolí přejít potmě. Test z [L2.9] zpřísni: „určuje stav přesnou množinu povolených tahů?“ Když ne, něco do stavu chybí.
- Cíl je množina stavů. Odpověď je minimum přes všechny cílové stavy (nebo vzdálenost do super-cíle). Kdo si vybere jen jeden cílový stav, může minout kratší řešení končící v jiném.
- Stavová exploze. Dvě lahve = $24$ stavů, pohoda. Most se $4$ lidmi = $2^4 \cdot 2 = 32$ stavů, s $n$ lidmi $2^n \cdot 2$ — formulace je pořád korektní, ale graf roste exponenciálně s počtem „věcí ve stavu“. U zkoušky velikost stavového prostoru vždy vyčísli.
Key takeaways — L2.10- Stav = úplná konfigurace problému (obsahy obou nádob; kdo je na kterém břehu a kde je baterka). Test: stav musí určovat přesnou množinu povolených tahů.
- Hrany se generují z pravidel (povolené tahy s cenou), graf nikdo nedá seznamem — dosažitelné stavy odhalí až prohledávání.
- Cíl bývá množina stavů → minimum přes cíle, nebo super-cíl $t$ napojený hranami s cenou $0$.
- Stejný automat, různé váhy = různé otázky (počet tahů / čas / objem). Váhy $\ge 0$ → Dijkstra [L2.4]; jednotkové váhy = vlna po vrstvách (BFS).
- Velikost stavového prostoru vyčísli — roste exponenciálně s počtem složek stavu ($2^n \cdot 2$ u mostu).
“You are on the bank of the lake and you have one 3-liter bottle and one 5-liter bottle. Both bottles are empty and your task is to have exactly 4 liters in the bigger bottle. You have no other equipment to measure the water level.
(a) Represent the problem by the graph.
(b) Set-up suitable weights and formulate the shortest path problem to find
- solution with the minimum number of manipulations,
- solution with the minimum amount of manipulated water,
- solution with the minimum amount of water poured back in the lake.
(c) During some manipulations you have to be very careful - for example when one bottle is filled completely but the other one does not become empty. Find the solution which minimizes the number of such manipulations.
(d) Is it possible to have 5 liters while using 4-liter and 6-liter bottles?”
a) Co je v zadání?
Hlavolam s přeléváním: 3litrová a 5litrová láhev, obě prázdné, cíl 4 litry v pětce. Části (a) a (b) jsou přesně látka této lekce (reprezentace grafem + tři volby vah), (c) přidává čtvrtou volbu vah pro „opatrné“ manipulace a (d) je rychlá otázka na jinou dvojici objemů — pozor, odpověď není graf, ale argument.
b) Co k tomu budeme potřebovat?
- Tato lekce — stav $(x,y)$, tahy jako hrany, cíl jako množina stavů, volby vah.
- [L2.9] Modelování reálné úlohy jako SP — recept stav — přechod — cena a korespondence řešení ↔ cesta.
- [L2.4] Dijkstrův algoritmus (běh) — předpoklad $c \ge 0$.
c) Jak nad úlohou uvažovat?
Projdi recept: co je stav, kolik jich nejvýš je, jaké tahy z obecného stavu vedou? Kde je start a co všechno je cíl? Pro každou odrážku v (b) si polož otázku „kolik tenhle konkrétní tah stojí?“ — graf se nemění, mění se jen $c(e)$. V (c) nejdřív přesně popiš, který tah je „opatrný“, a teprve pak mu dej cenu. V (d) hledej invariant: vlastnost, kterou žádný tah nepokazí, a kterou cíl porušuje.
d) Úplné řešení (vlastní — banka úlohu řešenou nemá; optima ověřena strojovým prohledáním celého stavového prostoru)
(a) Graf. Vrcholy = stavy $(x, y)$, $x \in \{0,\ldots,3\}$, $y \in \{0,\ldots,5\}$ (nejvýše 24). Hrany = manipulace: napustit ($(x,y) \to (3,y)$, resp. $(x,5)$), vylít ($\to (0,y)$, resp. $(x,0)$), přelít z trojky do pětky $\to (x - m,\, y + m)$ s $m = \min(x,\, 5 - y)$ a symetricky zpět. Start $s = (0,0)$; cílová množina $\{(x, 4)\}$, napojená hranami s cenou $0$ na super-cíl $t$. Z 24 stavů je dosažitelných 16 a mají dohromady 58 hran; z cílů jsou dosažitelné jen $(3,4)$ a $(0,4)$ — viz krokovaný běh ve výkladu.
(b) Tři volby vah (graf je pořád stejný):
- Minimum manipulací: $c(e) = 1$. Optimum je 6 tahů: $(0,0) \xrightarrow{+5} (0,5) \xrightarrow{5 \to 3} (3,2) \xrightarrow{-3} (0,2) \xrightarrow{5 \to 3} (2,0) \xrightarrow{+5} (2,5) \xrightarrow{5 \to 3} (3,4)$.
- Minimum přemístěné vody: $c(e) =$ objem přemístěný tahem. Optimální je tatáž cesta: $5 + 3 + 3 + 2 + 5 + 1 = \mathbf{19}$ litrů.
- Minimum vody vylité do jezera: $c(e) =$ objem jen u tahů „vylít“, jinak $0$. Optimum 3 litry (jediné vylití $(3,2) \to (0,2)$ na téže cestě). Nula nejde: bez vylévání voda v lahvích nikdy neubývá a dosažitelných je jen 8 stavů $\{(0,0), (3,0), (0,5), (3,5), (0,3), (3,2), (3,3), (1,5)\}$ — žádný s $y = 4$.
(c) Opatrné manipulace. Zadání je vymezuje příkladem; přirozené čtení: přelití, při kterém se cílová láhev naplní po okraj, ale zdrojová se nevyprázdní — musíš hlídat hladinu, abys nepřelil (modelovací volba, kterou u zkoušky napiš explicitně). Dej $c(e) = 1$ těmto přelitím a $0$ všem ostatním tahům → Dijkstra s vahami $0/1$. Optimum je 1 opatrná manipulace, např. $(0,0) \xrightarrow{+3} (3,0) \xrightarrow{3 \to 5} (0,3) \xrightarrow{+3} (3,3) \xrightarrow{3 \to 5} (1,5)^{\,!} \xrightarrow{-5} (1,0) \xrightarrow{3 \to 5} (0,1) \xrightarrow{+3} (3,1) \xrightarrow{3 \to 5} (0,4)$ — opatrné je jen přelití $(3,3) \to (1,5)$. Stojí to ale 8 tahů; šestitahová cesta z (b) má opatrná přelití dvě ($(0,5) \to (3,2)$ a $(2,5) \to (3,4)$) — různé váhy, různí vítězové.
(d) Lahve 4 l a 6 l → 5 litrů? Ne. Invariant: oba obsahy zůstávají sudé. Na začátku $(0,0)$ sudé; napuštění dá 4 nebo 6, vylití 0, a přelitý objem $m = \min(x,\, 6 - y)$ (resp. $\min(y,\, 4 - x)$) je rozdíl/minimum sudých čísel, tedy sudý. Stav s 5 litry je lichý → nedosažitelný. (Obecně: dosažitelné objemy jsou násobky $\gcd$ objemů lahví, zde $\gcd(4,6) = 2$.)
“Homework - Formulate the shortest path problem:
Four people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. They have one torch and, because it's night, the torch has to be used when crossing the bridge. One person can cross the bridge in 1 minute, one person in 2 minutes, one person in 5 minutes, and another person in 9 minutes. When two people cross the bridge together, they must move at the slower person's pace. The question is, can they all get across the bridge in 16 minutes or less?”
a) Co je v zadání?
Klasický hlavolam: čtyři lidé s časy 1, 2, 5 a 9 minut, most unese dva, baterka je jedna a přes most musí s každým přechodem — takže se s ní musí i vracet. Úkol: formulovat jako problém nejkratší cesty a rozhodnout, zda existuje plán do 16 minut.
b) Co k tomu budeme potřebovat?
- Tato lekce — stav jako konfigurace, hrany generované tahy, vyčíslení stavového prostoru.
- [L2.4] Dijkstrův algoritmus (běh) — váhy (časy) jsou kladné.
c) Jak nad úlohou uvažovat?
Co je stav? „Kdo už je na druhém břehu“ je málo — promysli, proč (kdo se může vrátit a s čím?). Co je tah a kolik stojí, když jdou dva? Kolik má automat stavů? A než pustíš Dijkstru, zkus plán vymyslet ručně: intuice „nejrychlejší dělá převozníka a vodí ostatní“ — spočítej ji; jde to líp?
d) Úplné řešení (vlastní — banka úlohu řešenou nemá)
Graf. Stav $= (S, b)$, kde $S \subseteq \{1, 2, 5, 9\}$ je množina lidí na výchozím břehu a $b \in \{\text{L}, \text{R}\}$ je poloha baterky. Bez $b$ to nejde: tahy zpět smí dělat jen někdo na břehu s baterkou. Stavů je $2^4 \cdot 2 = 32$. Hrany: je-li $b = \text{L}$, vyber jednoho nebo dva lidi z $S$ a pošli je tam — cena $= \max$ jejich časů, baterka se přepne na R; je-li $b = \text{R}$, vyber jednoho nebo dva z doplňku $S$ a pošli je zpět (s baterkou), cena opět $\max$. Start $s = (\{1,2,5,9\}, \text{L})$, cíl $t = (\emptyset, \text{R})$ — tady je cíl výjimečně jediný stav. Otázka zadání = „je délka nejkratší $s$–$t$ cesty $\le 16$?“; časy jsou kladné → Dijkstra [L2.4].
Odpověď: ano, přesně 16 minut. Převozník dá jen 18: $\{1,9\}$ tam (9), 1 zpět (1), $\{1,5\}$ tam (5), 1 zpět (1), $\{1,2\}$ tam (2). Trik je poslat dva nejpomalejší spolu, aby se devítka a pětka neplatily zvlášť: $\{1,2\}$ tam (2), 1 zpět (1), $\{5,9\}$ tam (9), 2 zpět (2), $\{1,2\}$ tam (2) — celkem $2+1+9+2+2 = 16$. Dijkstra tuhle cestu najde sama (a zaručí, že méně než 16 nejde); cesta je na obrázku pod úlohou.
Vyčíslení (patří k formulaci): $|V| = 2^n \cdot 2$, z každého stavu vede nejvýše $\binom{k}{1} + \binom{k}{2}$ tahů ($k$ = počet lidí na břehu s baterkou), tedy $|E| = O(2^n n^2)$ — pro $n = 4$ směšné, obecně exponenciální (past č. 3 z výkladu).