3. Turistika na Orave vzorové riešenie

4 4
1 3
1 2
2 1
4 1

3

Niečo o probléme najdlhšej cesty

Tak čo to teda tá úloha po nás vlastne chce? Máme Oravu, ktorá je orientovaným grafom. Máme v ňom nájsť najdlhšiu cestu. Hľadanie najdlhšej cesty v grafe znie ako celkom štandardný problém. Tak ak nevieme, pogooglime, pohľadáme, a čo nezistíme. Pre všeobecný graf je to NP-ťažký problém, teda ho deterministicky vieme riešiť len exponenciálnym algoritmom. Na druhú stranu, ak vieme že graf je strom alebo acyklický orientovaný graf, vieme ho vyriešiť v lineárnom čase od počtu vrcholov a hrán.

Tesne! Orava je totiž orientovaná, no nie acyklická. No a čo to hovorí tá špeciálna záruka v zadaní?

“Nech by ste svoju prechádzku začali pri ktorejkoľvek prírodnej kráse, ak ju na tom istom mieste chcete aj skončiť, je zaručené, že viete navštíviť nanajvýš štyri rôzne iné prírodné krásy – a to bez ohľadu na to, ako budete chodiť a či niektoré prírodné krásy (vrátane tej, kde ste začali a skončili) navštívite viackrát.”

Inak povedané, na Orave neexistuje silno súvislý komponent (odteraz SSK) ktorý by mal viac ako päť vrcholov. Od Oravy a acyklickým orientovaným grafom, na ktorom by sme úlohu vedeli vyriešiť jednoducho, nie je veľmi ďaleko. Musíme jej len trošku pomôcť.

Riešenie pre acyklické grafy

Na obyčajnom orientovanom acyklickom grafe vieme nájsť najdlhšiu cestu nasledovne: zoraďme si vrcholy topologicky, prechádzajme vrcholy v tomto poradí (začínajúc od vrcholov, do ktorých nevedie žiadna hrana) a počítajme pre každý z nich dĺžku najdlhšej cesty končiacej v ňom. Najdlhšia cesta končiaca v \(A\) je najdlhšia cesta do niektorého vrcholu \(B\), od ktorého vedie k \(A\) hrana, plus hrana z \(B\) do \(A\).

Takže keď chceme zistiť dĺžku najdlhšej cesty končiacej v \(A\), iba sa pozrieme na všetky vrcholy, z ktorých do \(A\) vedie hrana, a vyberieme ten, ktorý má svoju “dĺžku” najväčšiu (jeho dĺžku už poznáme, lebo vrcholy prechádzame podľa topologického usporiadania). Toto číslo zväčšíme o \(1\) (zarátame poslednú hranu \(BA\)), a toto je hľadaná dĺžka pre \(A\).

Kde je problém so silno súvislými komponentmi?

SSK nám robia problémy preto, že nám umožňujú chodiť “donekonečna”, pričom navštívime niektoré vrcholy viackrát. To nechceme, lebo to nesúhlasí s definíciou cesty – v ceste sa na rozdiel od sledu vrcholy neopakujú. (V acyklických grafoch tento problém nie je, lebo v nich je najdlhší sled zároveň aj najdlhšou cestou.)

Chceli by sme preto každý SSK nahradiť niečím tak, aby dĺžka najdlhšej cesty zostala rovnaká, ale aby sme dostali acyklický graf. Na tomto grafe by sme potom mohli spustiť algoritmus z úvodu.

Takže náš algoritmus bude mať nasledovnú formu: nájdi všetky SSK (napr. pomocou Tarjanovho algoritmu na hľadania SSK), zostrojíme nový graf, a na ňom pustíme algoritmus z úvodu. Ako ale upraviť SSK tak, aby sme dostali acyklický graf a informácia o najdlhšej ceste zostala zachovaná?

Transformácia

Uvedomme si: každú cestu v grafe vieme rozdeliť na niekoľko častí takých, že každá časť leží celá v jednom SSK. Časť môže byť aj prázdna (\(0\) hrán) a je to vlastne cesta medzi dvoma (nie nutne rôznymi) vrcholmi z toho istého SSK. Medzi týmito časťami sa presúvame hranami, ktoré vedú medzi rôznymi SSK.

Časti vieme “odsimulovať” nasledovne. Časť cesty vlastne znamená, že sme vošli do nejakého SSK (alebo sme v ňom začali), a potom z neho vyjdeme (alebo v ňom skončíme). Každý vrchol SSK teda zdvojíme – budeme mať vstupné vrcholy, a výstupné vrcholy. Každá hrana medzi týmito vrcholmi bude reprezentovať cestu v pôvodnom SSK, a bude môcť vychádzať iba zo vstupných vrcholov, a vchádzať len do výstupných. Dĺžka hrany bude rovná dĺžke cesty, ktorú reprezentuje. (Napríklad ak sme mali v pôvodnom SSK vrcholy \(A, B, C\) a hrany \(AB, BC, CA\), tak v novom grafe budeme mať vrcholy \(A_{in}, A_{out}, B_{in}, B_{out}, C_{in}, C_{out}\), cesta \(ABC\) by bola reprezentovaná hranou \(A_{in}C_{out}\) s dĺžkou \(2\), a cesta \(CA\) by bola reprezentovaná hranou \(C_{in}A_{out}\) s dĺžkou \(1\). Takisto netreba zabudnúť na prázdne cesty, ktoré sú reprezentované hranami dĺžky \(0\).)

Kedže nás zaujíma najdlhšia cesta, tak medzi dvoma vrcholmi \(A_{in}, B_{out}\) pridáme iba jednu hranu, a to tú, ktorá reprezentuje najdlhšiu cestu z \(A\) do \(B\). Tú si môžeme dovoliť nájsť exponenciálnym algoritmom, nakoľko SSK obsahujúci \(A\) a \(B\) má nanajvýš \(5\) vrcholov – takže to bude len konštantne veľa operácii. Toto spravíme pre každú dvojicu (nie nutne rôznych) vrcholov z toho istého SSK, čo je nanajvýš \(5 \cdot 5 = 25\) dvojíc pre každý SSK – opäť konštanta. A počet SSK je \(O(n)\), čiže si to celé môžeme dovoliť.

Nakoniec, prechody medzi rôznymi SSK zariadime tak, že pre každú hranu \(AB\) v pôvodnom grafe, kde \(A\) a \(B\) sú v rôznych SSK, pridáme hranu \(A_{out}B_{in}\).

Výsledný algoritmus má časovú zložitosť \(O(n + m)\), teda úmernú veľkosti pôvodného grafu. Nový graf je totiž len konštantne-veľakrát väčší od pôvodného.