Úloha 3.u1: Odklízení cest (5 b)

Zadáno v čísle 23.3.

Řešeno v čísle 23.5.

Zadání

V džungli je mnoho rozcestí a pěšinek mezi nimi. Bohužel jsou cestičky zarostlé a Jonášovi s Jájou bude nějakou dobu trvat je opět zprůchodnit. Jája má mapku, která obsahuje informace o tom, jak dlouho jim bude trvat jednotlivé cestičky prosekat. Některá rozcestí jsou navíc označená, neboť by skrz ně mohla vést cesta ven z džungle. Na jednom takovém rozcestí aktuálně Jája s Jonášem stojí. Potřebovali by zjistit, kolik času budou muset strávit čištěním cest, než bude možné se dostat na všechna označená rozcestí. Čas potřebný na opětovné proběhnutí již jednou zprůchodněné cesty můžeme zanedbat. Také můžete předpokládat, že všechny cesty jsou průchozí v obou směrech a jejich prosekání bude trvat stejně dlouho nezávisle na tom, ze které strany postupujete.

Pro tento problém zatím nikdo neumí najít optimální řešení výrazně rychleji než zkoušením všech možností, kterých je opravdu hodně. Zkus ale najít algoritmus, který se k optimálnímu řešení přiblíží i v rozumném čase – třeba takový, jehož řešení bude v nejhorším případě dvojnásobkem optima a stihne ho nalézt v čase $\mathcal{O}(n^4)$, kde $n$ je počet všech rozcestí na mapě.1

Pokud ti problém pořád přijde moc složitý, část bodů dostaneš i za řešení, které předpokládá, že Jonáš s Jájou potřebují navštívit všechna rozcestí.


1) To jest, algoritmus smí provést řádově nejvýš $n^4$ (elementárních) kroků. Může provést např. $42n^4$ kroků nebo $5n^4 + 3n^2 + \log n$ kroků nebo $n^2$ kroků, ale už ne například $n^5$ kroků. Podrobněji se o měření efektivity algoritmů můžete dočíst v jedné z programátorských kuchařek:
http://ksp.mff.cuni.cz/kucharky/slozitost/

Řešení

Nejprve lehčí varianta: Pokud znáte problém hledání minimální kostry, tak se dalo nahlédnout, že se jedná právě o něj. K úspěšnému vyřešení to ale nebylo zapotřebí.

Vybereme si jedno rozcestí (například to, kde Jonáš s Jájou právě stojí), které prohlásíme za navštívené (všechna ostatní jsou nenavštívená) a zapamatujeme si všechny cesty, které z něj vedou. Dále budeme postupovat následujícím způsobem: Pokud už nemáme zapamatovanou žádnou neprosekanou cestu, tak to znamená, že žádné navštívené rozcestí nemá nenavštívené sousední rozcestí a tudíž jsme prohledali vše, co jsme mohli, a skončíme. Jinak ze všech ještě neprosekaných cest, které si pamatujeme, vybereme tu, kterou umíme prosekat nejrychleji. Pokud tato cesta vede mezi dvěma již navštívenými rozcestími, tak ji zapomeneme a celý postup opakujeme. V opačném případě spojuje navštívené rozcestí s nenavštíveným. Cestu prosekáme, její nenavštívený konec prohlásíme za navštívený a zapamatujeme si všechny ostatní cesty, které z něj vedou.

Důkaz správnosti: Pro spor nechť existují nějaké cesty, které jsme prosekali, ačkoliv nebyly součástí ideálního řešení. Z těchto cest vybereme tu, kterou jsme prosekali jako první. V momentě, kdy jsme tuto cestu prosekávali, se jednalo o nejsnadněji prosekatelnou cestu vedoucí z libovolného navštíveného rozcestí do libovolného nenavštíveného rozcestí.

Ideální řešení musí obsahovat posloupnost prosekaných cest, která vede z jednoho konce této „zbytečně“ prosekané cesty na druhý, a tato posloupnost nutně obsahuje cestu, o které jsme v době prosekání té zbytečně prosekané cesty věděli, ale tehdy jsme ji neprosekali. Existuje pouze jeden důvod, proč jsme něco takového mohli udělat – tu námi „zbytečně“ prosekanou cestu nebylo těžší prosekat než tu, kterou jsme tehdy neprosekali. Je dobré si uvědomit, že obě cesty mohly být stejně namáhavé k prosekání.

Můžeme tedy vzít ideální řešení, odstranit z něj tehdy neprosekanou cestu a přidat do něj námi „zbytečně“ prosekanou cestu. Tím se řešení nezhorší, zůstane platným a (což je důležité) odsuneme tím moment, kdy jsme se od ideálního řešení odchýlili. Tímto způsobem pak můžeme postupně odsouvat naše odchýlení od ideálního řešení tak dlouho, že k němu nikdy nedojde.

Časová náročnost bude záviset na tom, jak přesně si budeme pamatovat cesty, které možná ještě budeme chtít prosekat. Pokud použijeme obyčejnou haldu, dostaneme řešení v čase $\mathcal{O}(m \log m)$, kde $m$ je počet cest v džungli. Tento výsledek se ještě dá několika triky vylepšit, zájemce si dovolím odkázat na skripta Krajinou grafových algoritmů1.

Těžší varianta: Jedná se o problém Steinerova stromu. Použijeme Floydův-Warshallův algoritmus2 k spočítání nejkratších cest mezi každými dvěma označenými vrcholy. Tento algoritmus běží v $\mathcal{O}(n^3)$. V úplném grafu tvořeném označenými vrcholy a váhami nejkratších cest mezi nimi nalezneme minimální kostru podobně, jako v lehčí variantě, a to v čase $\mathcal{O}(k^2 \log k)$, kde $k$ je počet označených vrcholů, protože tento (úplný) graf obsahuje právě $k(k-1)/2 \le k^2$ hran. Pro každou hranu této minimální kostry pak prosekáme odpovídající nejkratší cestu v původním grafu (kterou si můžeme pamatovat z Floyd-Warshallova algoritmu). Ježto $k^2\log k$ je menší než $n^3$, celý algoritmus poběží ve stejném čase jako hledání všech nejkratších cest, tedy v $\mathcal{O}(n^3)$.


a: Optimální řešení „velikosti“ OPT.
  
b: Sled délky $2\, \mathrm{OPT}$ navštěvující všechny označené vrcholy.

c: Sled navštěvující označené vrcholy ve stejném pořadí jako sled z předchozího obrázku, ale jdoucí nejkratšími cestami. Jeho délka je tedy nejvýše $2\, \mathrm{OPT}$.
  
d: Odstraněním některých hran z předchozího sledu dostaneme kostru v grafu označených vrcholů. Algoritmem nalezená minimální kostra nemůže být tedy na prosekání težší.

Obrázek 1: Náznak důkazu, že námi nalezené řešení je nejhůře dvakrát tak těžké na prosekání, než optimální řešení.

Takhle nalezené řešení je nejvýše dvojnásobkem optima (viz Obrázek 1): Optimem je strom. Pokud uvážíme nejkratší sled3 po optimem vybraných hranách, který navštěvuje všechny označené vrcholy a začíná a končí ve stejném vrcholu, tak zjevně každou hranu používá právě dvakrát. Pokud označené vrcholy budeme navštěvovat ve stejném pořadí, ale pokaždé půjdeme nejkratší cestou, tak jsme zjevně celkovou délku tahu neprodloužili a v nejhorším případě jsme každou hranu použili pouze jednou, což znamená, že jsme prosekáváním museli strávit nejvýše dvakrát tolik času. Naším algoritmem nalezené řešení, které z nejkratších cest mezi označenými vrcholy vybírá minimální kostru, pak určitě nebude horší.

Matej


1) http://mj.ucw.cz/vyuka/ga/

2) Viz například http://mj.ucw.cz/vyuka/ads/26-cesty.pdf

3) Sled v grafu je posloupnost vrcholů taková, že mezi každými po sobě jdoucími vrcholy vede hrana. Jak vrcholy, tak hrany se mohou ve sledu opakovat.