Modelování reálné úlohy jako SP (DAG / stavový prostor)
Zkouškové úlohy ze Slotu 2 často nezačínají obrázkem grafu, ale příběhem a větou „formulate this as a shortest path problem“. V [L2.8] Dangerous adventure byla mapa (graf) aspoň daná a vymýšlel se jen převod vah. Dnes nedostaneš vůbec nic — ani vrcholy, ani hrany. Ukážeme si to na dvou klasických úlohách ze zkouškových reportáží: investicích pana Dow Jonese a směnách řidiče autobusu.
Pan Dow Jones investuje
Panu Dow Jonesovi je 50 let a chce v 65 letech vybrat ze svého penzijního účtu co nejvíc peněz. Na 15 let dopředu zná všechny investiční příležitosti — každá má počáteční rok $k$, dobu splatnosti (maturity period) $p$ let a zhodnocení (appreciation) $a$ za celé období splatnosti. V každém okamžiku má všechny peníze vložené v nejvýše jedné příležitosti (nedělí je). Konkrétní tabulka deseti příležitostí je v úloze T01 níže; zkouška chce: zformuluj to jako problém nejkratší cesty.
Zkus sám: žádný graf v zadání není. Co zvolíš za vrcholy?
Hledej veličinu, která se příběhem „vine“ a po které se postupuje vpřed: tady je to čas. Vrchol = rok $t \in \{0, 1, \ldots, 15\}$ (věk $50 + t$). Start $s$ = rok $0$, cíl $t$ = rok $15$. Vrchol čteme jako stav: „peníze jsou volné v roce $t$“.
Zkus sám: nemusí být součástí stavu i aktuální částka na účtu?
Ne — a to je klíčové pozorování. Každá příležitost násobí částku faktorem $1 + a$ bez ohledu na to, kolik peněz zrovna je; množina budoucích možností závisí jen na roce, ne na částce. Stav má nést přesně tu informaci, která rozhoduje o budoucnosti — tady stačí rok. (Kdyby výnos závisel na výši vkladu, rok by nestačil a stav by musel být bohatší.)
Zkus sám: co budou hrany? Pozor — příležitost a končí v roce 4, ale žádná jiná příležitost v roce 4 nezačíná (začátky jsou 0, 1, 2, 3, 5, 6, 7, 8, 11, 13). Co s tím?
Příležitost $(k, p, a)$ je hrana $k \to k + p$ s násobkem $1 + a$. Jenže jen s těmito hranami by z roku 4 nevedlo nic a model by tvrdil, že po příležitosti a už investování skončilo. Přidej proto čekací hranu $t \to t+1$ s násobkem $1$ pro každý rok: peníze mohou rok ležet na účtu. („V jediné příležitosti“ znamená, že je nedělí mezi víc příležitostí najednou — ne že nesmí ležet ladem.)
Zkus sám: cesta $0 \to 15$ teď odpovídá investiční strategii. Jaká je její hodnota — a jaký SP problém vlastně řešíme? (Vzpomeň si na [L2.7].)
Výsledná částka = vklad $\times$ součin násobků $1 + a_e$ přes hrany cesty a chceme ji maximalizovat. To je přesně situace pro $-\log$ z [L2.7]: polož $c(e) := -\log(1 + a_e)$ a minimalizuj součet. Jenže $1 + a_e \ge 1$, takže $-\log(1 + a_e) \le 0$ — všechny váhy jsou nekladné ($\le 0$) (investiční hrany záporné, čekací hrany mají $-\log 1 = 0$). Dijkstra [L2.4] je tedy mimo hru.
Zkus sám: záporné váhy — je to katastrofa? Kdy přesně jsou záporné váhy skutečný problém ([L2.1])?
Problém nejsou záporné hrany, ale záporné cykly [L2.1]. A náš graf žádný cyklus nemá: každá hrana vede z dřívějšího roku do pozdějšího. Je to DAG [L0.4] — vrcholy dokonce už od začátku stojí na přímce v topologickém uspořádání a všechny hrany jdou zleva doprava. Bez cyklů není ani záporný cyklus, takže nejkratší cesta je dobře definovaná.
Stejnou věc lze říct i bez $-\log$: maximalizace zhodnocení je nejdelší cesta v DAG s vahami $\log(1 + a_e)$ — a právě acykličnost ji dělá řešitelnou (v obecném grafu je nejdelší cesta těžká, podrobně v lekci [L2.17]). Jak nejkratší/nejdelší cestu v DAG spočítat v lineárním čase jedním průchodem zleva doprava, ukáže lekce [L2.13]; intuice už ale máš: stačí vyhodnocovat Bellmanovu rovnici [L2.2] po vrcholech v topologickém pořadí.
Recept: stav — přechod — cena (— kontrola)- Stav = vrchol. Minimální informace, která určuje budoucí možnosti. Test: „když znám stav, vím přesně, co všechno teď můžu udělat?“
- Přechod = hrana, cena = co stojí. Elementární rozhodnutí, které mění stav. Nezapomeň na „nicnedělací“ přechody (čekání). Součiny a maximalizaci převeď přes $-\log$ [L2.7].
- $s$, $t$ a korespondence. U zkoušky explicitně napiš: každé přípustné řešení úlohy $\leftrightarrow$ nějaká $s$–$t$ cesta a hodnota řešení = délka cesty. Bez této věty formulace není úplná.
- Kontrola. Podívej se na znaménka vah a na cykly výsledného grafu — teprve podle toho vyber algoritmus (tabulka níže).
Řidič autobusu: stav nemusí být jen „čas“
Druhá zkoušková klasika (z knihy Network Flows, Ahuja–Magnanti–Orlin): autobusový provoz běží od 9 do 17 hodin a je potřeba ho celý pokrýt směnami řidičů. K dispozici jsou směny 9–11, 9–13, 12–14, 12–16, 12–17, 14–16 a 15–17, každá s danou cenou; směny se smějí překrývat. Cíl: pokrýt celou dobu 9–17 co nejlevněji — a zadání výslovně chce formulaci, aby šla úloha vyřešit Dijkstrou.
Zkus sám: použij recept naivně — vrchol = hodina 9…17, směna $[a, b]$ = hrana $a \to b$ s cenou směny. Najdi cestu $9 \to 17$. Kde to skřípe?
Cesta neexistuje: po směně 9–13 stojíš ve vrcholu 13, ale žádná směna ve 13 nezačíná (začátky jsou 9, 12, 14, 15); po 9–11 stojíš v 11 — totéž. Přitom pokrytí existuje: 9–13 a 12–17 dohromady pokryjí všechno, jen se překrývají. Naivní model překryv zakazuje, je tedy moc přísný — zakazuje přípustná řešení.
Zkus sám: jak překryv povolit jedinou levnou úpravou grafu?
Čti vrchol jako stav „provoz je pokryt od 9 do $t$“. Pokrytí se nepokazí tím, že ho v duchu o hodinu „zkrátíme“: přidej hranu zpět $t \to t - 1$ s cenou $0$. Pak $9 \xrightarrow{9\text{–}13} 13 \xrightarrow{0} 12 \xrightarrow{12\text{–}17} 17$. Hrana zpět říká: další směna smí začít už o hodinu dřív, než dosavadní pokrytí končí — to je přesně povolený překryv.
Zkus sám: najdi v obrázku nejlevnější pokrytí (ceny směn jsou ilustrační — ve zkouškové reportáži se nedochovaly).
Optimum je 115: směny 9–13 (45), 12–16 (40) a 15–17 (30), tedy cesta $9 \to 13 \to 12 \to 16 \to 15 \to 17$ se dvěma hranami zpět. Srovnej: 9–13 + 12–17 dá $45 + 75 = 120$; 9–13 + 12–14 + 14–16 + 15–17 dá $45 + 25 + 25 + 30 = 125$.
Zkus sám: je tenhle graf DAG? A smí na něj Dijkstra?
DAG to není — hrany zpět tvoří s dopřednými hranami cykly (např. $12 \to 14 \to 13 \to 12$). Ale Dijkstra [L2.4] DAG nepotřebuje: potřebuje nezáporné váhy, a ty tu jsou (ceny směn $> 0$, hrany zpět $= 0$). Všimni si zrcadlové situace k panu Dow Jonesovi: tam DAG se zápornými vahami (Dijkstra ne, acykličnost zachraňuje), tady cykly s nezápornými vahami (Dijkstra ano).
Kontrola po modelování: který algoritmus?
Formulací práce nekončí — poslední krok receptu je podívat se, jaký graf nám vlastně vznikl:
| Výsledný graf | Algoritmus |
|---|---|
| váhy $\ge 0$ (na cyklech nezáleží) | Dijkstra [L2.4] — $O(n^2)$, resp. $O(|E| \log |V|)$ s haldou |
| DAG [L0.4] (váhy libovolné, i záporné; zvládne i nejdelší cestu) | jeden průchod v topologickém pořadí — lekce [L2.13], $O(|V| + |E|)$ |
| záporné váhy a cykly zároveň | Bellman-Ford — lekce [L2.12]; pozor, záporný cyklus dělá SP nedefinovaným [L2.1] |
Pozor: tři modelovací pasti- Zapomenuté čekací / zpětné hrany. Model bez nich prohlásí řešitelnou úlohu za neřešitelnou (Dow Jones bez čekání, řidič bez překryvu). Po sestavení grafu si vždy ručně přelož jedno konkrétní přípustné řešení na $s$–$t$ cestu — když to nejde, chybí hrany.
- Stav nese málo informace. Stav musí určovat všechny budoucí možnosti. U Dow Jonese stačí rok jen proto, že zhodnocení je multiplikativní a na částce nezávislé. Jakmile budoucnost závisí na víc věcech (kdo kde stojí, kolik vody je v nádobě…), patří do stavu všechny — to je téma příští lekce [L2.10] Stavový automat jako graf.
- „Pustím Dijkstru“ bez kontroly vah. Maximalizace přes $-\log$ násobků $\ge 1$ dává záporné váhy — Dijkstra na ně mlčky vrátí špatný výsledek (protipříklad v [L2.4]). Záchranou je tady acykličnost, ne Dijkstra.
Key takeaways — L2.9- Recept modelování: stav = vrchol (minimální informace určující budoucnost), přechod = hrana s cenou (včetně „čekání“), $s$, $t$ + explicitní korespondence řešení úlohy ↔ $s$–$t$ cesta.
- Úlohy s časovou osou: vrcholy = časové body, hrany = příležitosti/směny s cenou; hrany vedou vpřed v čase → graf je DAG [L0.4].
- Maximalizace zhodnocení = nejdelší cesta v DAG; přes $-\log$ [L2.7] nejkratší cesta se zápornými vahami — v DAG to nevadí, žádný cyklus = žádný záporný cyklus [L2.1].
- Stav může být i „pokryto do $t$“ — hrany zpět s cenou 0 povolí překryv směn; váhy $\ge 0$ → Dijkstra [L2.4] funguje i mimo DAG.
- Po modelování zkontroluj znaménka vah a cykly → volba algoritmu: Dijkstra / topologický průchod [L2.13] / Bellman-Ford [L2.12].
“Mr. Dow Jones, 50 years old, wishes to place his Individual Retirement Account funds in various investment opportunities so that at the age of 65 years, when he withdraws the funds, he has accrued maximum possible amount of money. Assume that Mr. Jones knows the investment alternatives for the next 15 years - each opportunity has starting year $k$, maturity period $p$ (in years) and appreciation $a$ it offers for the maturity period. How would you formulate this investment problem as a shortest path problem, assuming that at any point in time, Mr. Jones invests all his funds in a single investment alternative.”
| opportunity | a | b | c | d | e | f | g | h | i | j |
|---|---|---|---|---|---|---|---|---|---|---|
| starting year | 0 | 1 | 3 | 2 | 5 | 6 | 7 | 8 | 11 | 13 |
| maturity period | 4 | 5 | 6 | 5 | 4 | 5 | 6 | 5 | 4 | 2 |
| appreciation | 3.9% | 4.7% | 6.2% | 4.2% | 3.8% | 4.1% | 5.2% | 5.8% | 4.1% | 3.2% |
a) Co je v zadání?
Patnáctiletý horizont (roky 0–15, věk 50–65), deset příležitostí — každá je trojice (počáteční rok $k$, splatnost $p$ let, zhodnocení $a$ za celé období). Peníze jsou vždy vcelku v nejvýše jedné příležitosti. Úkolem je formulace: popsat graf (vrcholy, hrany, váhy) a zdůvodnit, že nejkratší cesta v něm odpovídá strategii s maximálním výnosem. Konkrétní optimum spočítat můžeš, ale otázka zní „how would you formulate“.
b) Co k tomu budeme potřebovat?
- Tato lekce — recept stav–přechod–cena, čekací hrany.
- [L2.7] Transformace −log — max součin → min součet.
- [L0.4] Strom, kostra, les, DAG — topologické uspořádání, acykličnost.
- [L2.1] Záporné váhy ano, záporné cykly ne — proč záporné váhy v DAG nevadí.
- [L2.2] Bellmanova rovnice — pro výpočet hodnot po topologickém pořadí.
c) Jak nad úlohou uvažovat?
Polož si otázky receptu: Co je stav (a proč v něm nemusí být částka)? Co je přechod a co stojí? Jak se dostaneš přes roky, kdy žádná příležitost nezačíná? Co přesně maximalizuješ a kterou lekcí to převedeš na součet? A nakonec kontrola: jaké znaménko mají váhy a proč to tady nevadí?
d) Úplné řešení
Graf. Vrcholy $V = \{0, 1, \ldots, 15\}$ = roky (stav „peníze jsou volné v roce $t$“); $s = 0$, $t = 15$. Hrany: pro každou příležitost $(k, p, a)$ hrana $k \to k + p$ s násobkem $1 + a$; pro každý rok $t \le 14$ čekací hrana $t \to t + 1$ s násobkem $1$ (peníze leží na účtu — „single investment alternative“ zakazuje dělit peníze, ne nechat je ležet). Každá strategie investování ↔ právě jedna cesta $0 \to 15$ a výsledná částka = vklad $\times$ součin násobků podél cesty.
Převod na nejkratší cestu. Maximalizujeme součin $\prod_e (1 + a_e)$ → podle [L2.7] polož $c(e) := -\log(1 + a_e)$ a minimalizuj $\sum_e c(e)$; logaritmus je rostoucí, takže vítězná cesta se nemění. Váhy vyjdou nekladné ($1 + a_e \ge 1$): investiční hrany záporné, čekací hrany mají váhu $0$. To je v pořádku: všechny hrany vedou z dřívějšího roku do pozdějšího, graf je DAG [L0.4] (roky na přímce = topologické uspořádání), takže neobsahuje žádný cyklus — tím spíš žádný záporný [L2.1] a nejkratší cesta je dobře definovaná. (Ekvivalentně: nejdelší cesta v DAG s vahami $\log(1 + a_e)$.) Dijkstra [L2.4] se kvůli záporným vahám použít nesmí; v DAG stačí vyhodnotit Bellmanovu rovnici [L2.2] po vrcholech zleva doprava — algoritmus s $O(|V| + |E|)$ podrobně v lekci [L2.13]. Tím je formulace (= požadovaná odpověď) hotová.
Bonus: konkrétní optimum. Označ $v(t)$ nejlepší dosažitelný násobek v roce $t$ a vyhodnocuj multiplikativní obdobu Bellmanovy rovnice zleva doprava, $v(w) = \max_{(u,w)} v(u) \cdot m(u,w)$ (stejný princip jako multiplikativní pravidlo v [L2.7], T01b). Hodnota se mění jen v koncových letech příležitostí (mezi nimi ji kopírují čekací hrany):
| roky $t$ | 0–3 | 4–5 | 6–8 | 9–10 | 11–12 | 13–14 | 15 |
|---|---|---|---|---|---|---|---|
| $v(t)$ | $1$ | $1{,}039$ | $1{,}047$ | $1{,}0785$ | $1{,}0899$ | $1{,}1077$ | $\mathbf{1{,}1432}$ |
| vítězná hrana | — | a | b | e | f | h | j |
Rozhodující porovnání: rok 9: $\max(1{,}047;\; c\!: 1{,}062;\; e\!: 1{,}039 \cdot 1{,}038 = 1{,}0785)$ → e; rok 13: $\max(1{,}0899;\; g\!: 1{,}047 \cdot 1{,}052 = 1{,}1014;\; h\!: 1{,}047 \cdot 1{,}058 = 1{,}1077)$ → h; rok 15: $\max(1{,}1077;\; i\!: 1{,}0899 \cdot 1{,}041 = 1{,}1346;\; j\!: 1{,}1077 \cdot 1{,}032 = 1{,}1432)$ → j. Zpětným čtením vítězných hran: rok počkat, b (roky 1–6), dva roky počkat, h (8–13), j (13–15); celkem $1{,}047 \cdot 1{,}058 \cdot 1{,}032 \approx 1{,}1432$, tedy asi +14,3 % za 15 let.
Formulace problému tak, aby šel vyřešit Dijkstrou. Máme řidiče autobusu a směny v době 9-17. K dispozici jsou různé časy směn (9-11, 9-13, 12-14, 12-16, 12-17, 14-16, 15-17 cca) a ke směnám ceny. Je to někde v knížce Network Flows - Ahuja, Magnanti, Orlin.
a) Co je v zadání?
Provoz 9–17 hodin je třeba beze zbytku pokrýt směnami z daného seznamu (časy v přepisu jsou „cca“); každá směna má cenu, směny se mohou překrývat. Minimalizuje se celková cena. Konkrétní ceny se v reportáži nedochovaly — v ukázce výkladu jsme zvolili ilustrační (30, 45, 25, 40, 75, 25, 30). Odpovědí je formulace grafu, na kterém problém vyřeší Dijkstra.
b) Co k tomu budeme potřebovat?
- Tato lekce — stav „pokryto do $t$“ a hrany zpět s cenou 0.
- [L2.4] Dijkstrův algoritmus (běh) — předpoklad nezáporných vah, složitost.
c) Jak nad úlohou uvažovat?
Začni receptem: co je stav? (Pozor — „hodina 9…17“ sama o sobě nestačí, rozmysli si, co vrchol znamená.) Proč naivní hrany „směna = $a \to b$“ nestačí — najdi pokrytí, které jim unikne. Jak levně povolit překryv? A nakonec kontrola pro Dijkstru: jsou všechny váhy nezáporné? Vadí, že graf není DAG?
d) Úplné řešení
Graf. Vrcholy $V = \{9, 10, \ldots, 17\}$, vrchol $t$ = stav „provoz je souvisle pokryt od 9 do $t$“; $s = 9$ (nic nepokryto, hodnota 9 = začátek), cíl $17$. Hrany dvojího druhu:
- pro každou směnu $[a, b]$ s cenou $c_{ab}$ hrana $a \to b$ s vahou $c_{ab}$ (směnu lze „přiložit“, právě když pokrytí sahá aspoň do jejího začátku);
- pro každé $t \ge 10$ hrana zpět $t \to t - 1$ s vahou $0$ (pokrytí do $t$ je i pokrytím do $t-1$ — tím se povolí překryv směn).
Korespondence. Každá $9$–$17$ cesta vybírá množinu směn, jejichž sjednocení souvisle pokrývá 9–17 (každá směnová hrana začíná v už pokrytém čase a posune pokrytí do svého konce), a její délka = součet cen vybraných směn. Obráceně: libovolné přípustné pokrytí seřaď podle začátků směn a přelož na cestu — mezi koncem jedné směny a začátkem další sestup hranami zpět (zadarmo). Nejkratší cesta tedy odpovídá nejlevnějšímu pokrytí. (Optimální cesta žádnou směnu nezopakuje — opakování by jen přičetlo kladnou cenu.)
Kontrola pro Dijkstru. Všechny váhy jsou nezáporné (ceny směn $> 0$, hrany zpět $0$) — přesně předpoklad Dijkstry [L2.4]. Graf kvůli hranám zpět není DAG, ale to Dijkstrovi nevadí; na 9 vrcholech běží v $O(n^2)$, obecně $O(|E| \log |V|)$ s haldou. Tím je požadovaná formulace hotová.
Na ilustračních cenách z výkladu vyjde optimum $115$: $9 \xrightarrow{9\text{–}13\,(45)} 13 \xrightarrow{0} 12 \xrightarrow{12\text{–}16\,(40)} 16 \xrightarrow{0} 15 \xrightarrow{15\text{–}17\,(30)} 17$ — viz zvýrazněná cesta na obrázku pod úlohou.