Časově expandovaná síť (constrained SP)
Zkouška 9. 7. 2021 dala na každou hranu dvě čísla: délku a dobu průchodu — a chtěla nejkratší cestu, která stihne časový limit. V [L2.10] Stavový automat jako graf jsme si slíbili, že tahle úloha je taky stavový automat, jen se stavem „(kde jsem, kolik je hodin)“. Dnes ten slib splníme — konstrukci se říká time-expanded network (časově expandovaná síť) a celá úloha constrained shortest path (nejkratší cesta s omezením).
Dvě čísla na hraně: délka a doba
Každá hrana $(i,j)$ sítě $G$ nese délku $c_{ij} \in \mathbb{R}$ (tu minimalizujeme) a dobu průchodu (traversal time) $\tau_{ij} \in \mathbb{Z}_0^+$ (tu jen hlídáme). Hledáme cestu z $s$ do $t$ s nejmenším součtem délek mezi cestami, jejichž součet dob nepřekročí limit $\tau$. Na tomhle grafu (vlastní příklad — rukopisný graf z písemky se nedochoval čitelně) si to ohmatej, limit je $\tau = 4$:
Zkus sám: najdi nejkratší cestu jen podle délek $c$ (na doby nehleď). Stihne limit $\tau = 4$?
Nejlevnější je $s \to a \to t$ s délkou $1 + 1 = 2$. Jenže její doba je $2 + 3 = 5 > 4$ — limit poruší. Obyčejná Dijkstra [L2.4] nad $c$ tedy vrátí nepřípustnou odpověď.
Zkus sám: tak vezmeme místo toho nejrychlejší cestu (Dijkstra nad dobami $\tau_{ij}$). Pomůže to?
Nejrychlejší je $s \to b \to t$ s dobou $1 + 1 = 2$ — limit splní, ale stojí $4 + 4 = 8$. Správná odpověď je přitom $s \to a \to b \to t$: délka $1 + 1 + 4 = 6$, doba $2 + 1 + 1 = 4 \le 4$. Tenhle kompromis neuvidí ani jedno z obou jednokriteriálních hledání. Nejkratší cesta umí optimalizovat jen jedno číslo — druhé kritérium musíme dostat do grafu.
Expanze: kopie vrcholu pro každý čas
Zkus sám: recept z [L2.9]/[L2.10] začíná otázkou „co je stav?“. Jaká informace tady určuje, co můžu dělat dál?
Nestačí vědět, kde jsem — záleží i na tom, kolik času už uteklo (od toho se odvíjí, které pokračování ještě stihnu). Stav je dvojice $(v, k)$: vrchol $v$ a čas $k \in \{0, \ldots, \tau\}$. Víc pamatovat netřeba: budoucnost závisí jen na pozici a zbývajícím čase.
Postavíme tedy nový graf $H$ — časovou expanzi sítě $G$ s limitem $T := \tau$:
$$V(H) = \{(v, k) : v \in V(G),\ k = 0, 1, \ldots, T\},$$
a pro každou původní hranu $(i,j) \in E(G)$ a každé $k$ takové, že $k + \tau_{ij} \le T$, přidáme hranu
$$\big((i,k),\ (j,\, k + \tau_{ij})\big) \in E(H) \quad \text{s cenou } c_{ij}.$$
Všimni si, co se stalo s limitem: hrany, které by ho přestřelily ($k + \tau_{ij} > T$), vůbec nevzniknou. Omezení už není „podmínka navíc“ — je zadrátované do tvaru grafu. V $H$ zbývá optimalizovat jediné kritérium, délky $c_{ij}$.
Zkus sám: kde v $H$ začínáme a kde končíme? Pozor, cíl je záludný stejně jako v [L2.10].
Start je kopie $(s, 0)$. Cíl ale není jeden vrchol: „dorazit do $t$ nejpozději v čase $T$“ splňuje každá kopie $(t, k)$, $k = 0, \ldots, T$ — cíl je množina. Řešení známe z [L2.10]: přidej super-cíl $t^*$ a hrany $(t,k) \to t^*$ s cenou $0$, pak hledej obyčejnou nejkratší cestu $(s,0) \to t^*$.
Alternativa z vzorového řešení: přidej čekací hrany $(v,k) \to (v,k+1)$ s cenou $0$ (stejný trik jako čekání u pana Dow Jonese v [L2.9]) a hledej cestu jen do $(t, T)$. Čekací hrany totiž převedou podmínku „příchod nejpozději v $T$“ na „příchod přesně v $T$“ — kdo dorazí dřív, počká zadarmo.
Takhle vypadá expanze našeho příkladu pro $T = 4$ (řádky = vrcholy $G$, sloupce = čas):
Spousta kopií je mrtvá: do $(s,1), \ldots, (s,4)$ nebo $(t,0)$ nic nevede, z $(a,4)$ a $(b,4)$ se už nikam nestihne. Rukopisné řešení z písemky k tomu má lakonickou poznámku „remove all disconnected nodes and invalid paths“ — škrtnout je můžeš, ale nemusíš: prohledávání se k nim stejně nikdy nedostane.
Běh: Dijkstra na expandované síti
Zkus sám (než pustíš krokování): kolik vrcholů a hran má $H$ pro náš příklad?
Kopií je $|V(G)| \cdot (T+1) = 4 \cdot 5 = 20$, plus super-cíl $t^*$, celkem $21$. Hran: kopie původních hran $3 + 4 + 4 + 2 + 4 = 17$ (hrana $s \to a$ má 3 kopie, $a \to t$ jen 2 — víc se jich do limitu nevejde) a $5$ nulových hran do $t^*$, celkem $22$. Vyčíslení velikosti patří k formulaci — to je lekce z [L2.10].
Délky v našem příkladu jsou nezáporné, takže na $H$ stačí Dijkstra [L2.4] z $(s,0)$:
Co expanze stojí — a co všechno vydrží
Cena za trik: $H$ má $n(\tau+1)$ vrcholů a nejvýše $m(\tau+1)$ hran (plus hrany super-cíle). Velikost tedy roste s číselnou hodnotou limitu $\tau$, ne s délkou jeho zápisu — pro malý graf a $\tau = 10^6$ má expanze miliony kopií. Pro rozumně malá $\tau$ je to ale naprosto praktická a u zkoušky standardní konstrukce.
Zkus sám: zadání připouští $c_{ij} \in \mathbb{R}$ — klidně záporné délky. Kdy to v $H$ vadí?
Skoro nikdy! Pokud mají všechny hrany $\tau_{ij} \ge 1$, vede každá hrana $H$ do ostře vyššího času — po hranách se nedá vrátit, takže $H$ nemá cykly: je to DAG [L0.4]. Záporné délky pak nevadí; dokonce i záporný cyklus v $G$ se v $H$ neškodně „rozbalí“ do konečného řetězu kopií, protože každý jeho oběh spotřebuje čas a limit ho utne. Na DAG navíc existuje levný průchod v topologickém pořadí [L2.13].
Pozor jen na hrany s $\tau_{ij} = 0$: ty zůstávají uvnitř jedné časové vrstvy, cyklus z takových hran v $H$ přežije — a má-li zápornou délku, jsme zpět u potíží z [L2.1]. (Záporné hrany bez záporných cyklů řeší Bellman-Fordův algoritmus [L2.12] — příští lekce.)
Silná souvislost ti cestu nezaručí
Zkus sám: část (b) zkouškové úlohy. Je-li $G$ silně souvislý (z každého vrcholu se dá dojet do každého), existuje přípustná cesta vždy?
Ne. Silná souvislost říká jen, že nějaká cesta $s \to t$ existuje — neříká nic o jejím čase. Stačí protipříklad ze vzorového řešení: dva vrcholy, hrana $s \to t$ s dobou $10$, hrana $t \to s$ s dobou $10$, limit $\tau = 5$. Graf je silně souvislý, ale žádná $s$–$t$ cesta limit nesplní. V expandované síti se to projeví čistě: z $(s,0)$ nevede vůbec žádná hrana ($0 + 10 > 5$), takže $t^*$ zůstane nedosažitelný — $l(t^*) = \infty$.
Pozor: tři pasti časové expanze- „Nejpozději v $\tau$“ ≠ „přesně v $\tau$“. Bez čekacích hran je cílem celá množina kopií $(t,0), \ldots, (t,\tau)$ (super-cíl $t^*$); kdo hledá cestu jen do $(t,\tau)$, řeší jinou úlohu — a může mu vyjít $\infty$, i když přípustná cesta existuje. S čekacími hranami je naopak jediný cíl $(t,\tau)$ v pořádku.
- „Silně souvislé ⇒ cesta existuje“ je polopravda. Limit může zabít všechny $s$–$t$ cesty najednou (protipříklad výše) — přesně na to se ptá část (b) zkoušky.
- Velikost vyčísli. $n(\tau+1)$ vrcholů a až $m(\tau+1)$ hran — roste s hodnotou $\tau$, ne s velikostí zápisu zadání. U zkoušky počty kopií a hran vždy uveď (stejná disciplína jako stavová exploze v [L2.10]).
Key takeaways — L2.11- Časová expanze: kopie $(v,k)$ pro $k = 0,\ldots,\tau$; hrana $(i,j)$ s dobou $\tau_{ij}$ a délkou $c_{ij}$ dává hrany $(i,k) \to (j,\,k+\tau_{ij})$ s cenou $c_{ij}$, ale jen pro $k + \tau_{ij} \le \tau$ — limit je zadrátovaný do grafu.
- Constrained SP (doba $\le \tau$) = obyčejné SP v $H$ z $(s,0)$ do super-cíle $t^*$ (kopie $(t,k)$ napojené hranami s cenou $0$); ekvivalentně čekací hrany $(v,k) \to (v,k+1)$ s cenou $0$ a jediný cíl $(t,\tau)$.
- Velikost: $n(\tau+1)$ vrcholů, až $m(\tau+1)$ hran — roste s číselnou hodnotou $\tau$.
- $\tau_{ij} \ge 1$ ⇒ $H$ je DAG (čas jen roste) — záporné délky, ba i záporný cyklus v $G$, nevadí; pozor na hrany s $\tau_{ij} = 0$.
- I v silně souvislém grafu nemusí cesta v limitu existovat ($s \rightleftarrows t$ s dobami $10$, $\tau = 5$).
“In a network $G$ we associate two numbers with each arc: its length $\ell_e \in \mathbb{R}$ and its traversal time $\tau_{ij} \in \mathbb{Z}_0^+$. We would like to determine a shortest-length path from the source node $s$ to the sink node $t$ with the additional constraint that the traversal time of the path does not exceed $\tau$.
a) Formulate this problem as a shortest path problem (hint: use time expansion of the network).
b) Does the path necessarily exist if the network $G$ is strongly connected?”
a) Co je v zadání?
Přesně látka této lekce: síť se dvěma čísly na hraně (délka, doba průchodu), hledá se nejkratší cesta $s \to t$ s dobou nejvýše $\tau$. Část (a) chce konstrukci (převod na obyčejné SP přes časovou expanzi — nápověda ji rovnou prozrazuje), část (b) je rychlá rozhodovací otázka s argumentem: ano s důkazem, nebo ne s protipříkladem.
b) Co k tomu budeme potřebovat?
- Tato lekce — kopie $(v,k)$, podmínka $k + \tau_{ij} \le \tau$, super-cíl / čekací hrany.
- [L2.10] Stavový automat jako graf — cíl jako množina stavů → super-cíl, vyčíslení velikosti.
- [L2.9] Modelování reálné úlohy jako SP — recept stav–přechod–cena, čekací hrany.
- [L2.4] Dijkstrův algoritmus (běh) — řešení výsledného SP pro $c \ge 0$.
c) Jak nad úlohou uvažovat?
V (a) piš konstrukci formálně: co jsou vrcholy $H$ (a co kopie znamená), které hrany vzniknou a s jakou cenou, kde je start a co všechno je cíl. Nezapomeň na podmínku $k + \tau_{ij} \le \tau$ — bez ní limit nikde není! — a na to, že cíl je množina kopií. Na závěr vyčísli velikost $H$. V (b) si rozmysli, co silná souvislost zaručuje (existenci nějaké cesty) a co ne (její dobu) — protipříklad pak stačí dvouvrcholový.
d) Úplné řešení (dle vzorového řešení banky #11)
(a) Časově expandovaný graf. Položme $T := \tau$. Vytvoříme graf $H$ s vrcholy
$$V(H) = \{(v, k) : v \in V(G),\ k = 0, 1, \ldots, T\}.$$
Vrchol $(v,k)$ znamená „cesta je ve vrcholu $v$ v čase $k$“. Pro každou původní hranu $(i,j) \in E(G)$ a každé $k$ takové, že $k + \tau_{ij} \le T$, přidáme hranu
$$\big((i,k),\ (j,\, k + \tau_{ij})\big) \in E(H) \quad \text{s cenou } c_{ij}.$$
Pak řešíme obyčejný problém nejkratší cesty z $(s, 0)$ do libovolného z vrcholů $(t, k)$, $k = 0, \ldots, T$. Ekvivalentně: přidáme umělý cíl $t^*$ a nulové hrany $(t,k) \to t^*$ pro $k = 0, \ldots, T$ a hledáme nejkratší cestu $(s,0) \to t^*$. Každá cesta v $H$ odpovídá cestě v $G$ se stejnou délkou a dobou průchodu $\le T$ a naopak — hrany porušující limit v $H$ neexistují. Velikost: $|V(H)| = n(T+1) + 1$, $|E(H)| \le m(T+1) + (T+1)$.
Poznámka (čekací hrany): místo mnoha kopií cíle $(t,k)$ lze přidat čekací hrany $(v,k) \to (v, k+1)$ s cenou $0$ a hledat cestu jen z $(s,0)$ do $(t,T)$. Tyto hrany pouze převádějí podmínku „příchod nejpozději v čase $T$“ na „příchod přesně v čase $T$“.
(b) Existence: NE. Silná souvislost nezaručuje přípustnost při časovém limitu. Protipříklad: $s \to t$ s dobou průchodu $10$, $t \to s$ s dobou průchodu $10$, limit $T = 5$. Graf je silně souvislý, ale žádná $s$–$t$ cesta limit nesplní. (Takhle stručně — „it doesn't necessarily exist, its possible that all paths violate the constraint of not exceeding $\tau$“ — to stálo v dochovaném studentském řešení a bylo uznáno ✓.)