1. Postav cesty! vzorové riešenie

Na začiatok si pripomeňme zadanie úlohy. Dostali sme mapu Absurdistanu, na ktorej bolo \(n\) miest, medzi ktorými viedli nejaké cesty. Našou úlohou bolo vybrať cesty, ktoré sa budú rekonštruovať. Cieľom bolo vybrať takýchto ciest čo najmenej, lebo rekonštrukcia je drahá, ale zároveň docieliť, aby sa medzi každými dvoma mestami dalo cestovať iba po zrenovovaných cestách.

Skôr ako sa pustíme do riešenia, musíme si zadefinovať pojem komponent, ktorý budeme počas tohto vzorového riešenia hojne používať. Komponentom nazývame skupinu miest, medzi ktorými sa dá pohybovať iba po zrekonštruovaných cestách.

Na obrázku nižšie si môžete pozrieť ako môže vyzerať Absurdistan. Červenou farbou sú označené zrekonštruované cesty. Na obrázku naľavo sú 3 komponenty – (A, E, H, I), (D, G) a (C, B, F, J). Na obrázku napravo sú komponenty až 4 – (A), (E, H, I, F, G), (D) a (C, B, J). Všimnite si, že aj osamotený vrchol tvorí komponent.

Ak sme ešte nezrekonštruovali žiadnu cestu, v Absurdistane sa nachádza \(n\) komponentov – každé mesto tvorí samostatný komponent odkiaľ sa nevieme pohnúť ďalej. No a našou úlohou je zrekonštruovať také cesty, aby bol v Absurdistane iba jeden komponent, ktorý obsahuje všetky mestá. Potom sa z definície dá dostať z každého mesta do každého iného iba po zrekonštruovaných cestách.

Podúlohy a) a b)

Ako však zistíme, ktoré cesty chceme vybrať? Skúsme ich postupne rekonštruovať, je úplne jedno v akom poradí. Aby sme však nezrenovovali všetky cesty, vždy pred renováciou si položíme dôležitú otázku: Pomôže nám rekonštrukcia tejto cesty?

Predstavme si, že uvažujeme o ceste, ktorá vedie medzi mestami X a Y. V úvahu pripadajú dve možnosti. Obe tieto mestá ležia v tom istom komponente, teda už sa medzi nimi dá pohybovať iba po zrekonštruovaných cestách. V takom prípade nám však rekonštrukcia cesty medzi X a Y v ničom nepomôže. Ak už existoval spôsob ako medzi týmito dvoma mestami prejsť iba po zrekonštruovaných cestách, vždy, keď by sme chceli použiť túto priamu cestu, môžeme to radšej obísť. A ušetríme si jednu rekonštrukciu.

Druhá možnosť nastane ak mestá X a Y neležia v tom istom komponente. V takom prípade nám rekonštrukcia tejto cesty pomôže, lebo odteraz sa budeme vedieť dostať z X do Y (a naopak). A nielen to. Ak mesto A bolo v tom istom komponente ako X a mesto B v tom istom komponente ako Y, tak zrazu sa vieme dostať aj z mesta A do mesta B a to iba po zrekonštruovaných cestách. Stačí ak najskôr pôjdeme z A do X (takýto spôsob existuje, lebo sú v tom istom komponente), potom prejdeme po novozrekonštruovanej ceste do Y a odtiaľ do mesta B (takýto spôsob existuje, lebo sú v tom istom komponente). Zrekonštruovanie tejto cesty nám teda spojilo príslušné dva komponenty a nahradilo ich jedným väčším.

A to je v konečnom dôsledku náš cieľ. Spojiť \(n\) samostatných komponentov do jedného veľkého. Takýto postup vieme aj veľmi jednoducho zapísať a pochopia ho aj vaši rodičia:

postupne pre každú cestu v Absurdistane sprav:
    ak sa mestá na koncoch tejto cesty nachádzajú v rovnakom komponente
    (dá sa medzi nimi dostať iba po zrekonštruovaných cestách), tak:
        s touto cestou nič nerob
    ak sa nenachádzajú v rovnakom komponente, tak:
        zrekonštruuj túto cestu

Tento postup určite povedie k tomu, že nám ostane jeden veľký komponent a teda sa budeme vedieť dostať odvšadiaľ všade iba po zrekonštruovaných cestách. Vyberie však tento postup minimálny počet ciest? A koľko ich vlastne vyberie?

Spomeňme si, čo sa stane ak v tomto postupe zrekonštruujeme nejakú cestu – spojíme dva komponenty do jedného väčšieho. To znamená, že počet komponentov klesne o 1. No a ak sme začínali s \(n\) komponentami (každé mesto je samostatný komponent) a skončili sme s 1 komponentom, museli sme takéto spájanie spraviť presne \(n-1\) krát. Zrekonštruovali sme teda \(n-1\) ciest.

Toto je však aj dôvod, prečo je tento počet zrekonštruovaných ciest najmenší možný. Ľubovoľná rekonštrukcia niektorej cesty vie spojiť najviac dva komponenty. A preto musíme zrekonštruovať aspoň \(n-1\) ciest.

Podúloha c)

V podúlohe c) je situácia trochu komplikovanejšia. Za rekonštrukciu cesty totiž musíme zaplatiť, v tomto prípade 1 alebo 2 milióny dolárov. Našou úlohou je opäť zrekonštruovať také cesty, aby sa medzi každými dvoma mestami dalo pohybovať iba po zrekonštruovaných cestách, ale zároveň chceme zaplatiť čo najmenej peňazí.

Pri predchádzajúcej úlohe sme si ukázali, že musíme postaviť aspoň \(n-1\) ciest. Táto podmienka sa nezmení ani teraz. Ak by sme totiž postavili viac ciest, určite sa nájde taká, ktorej nezrekonštruovanie neporuší podmienku zo zadania. A ak ju nezrenovujeme, tak samozrejme ušetríme nejaké doláre.

Líši sa však táto úloha až tak veľmi od úlohy predchádzajúcej? Cesty predsa majú len dve možné ceny. Znie prirodzene, že ak chceme za rekonštrukciu zaplatiť čo najmenej peňazí, chceme zrekonštruovať čo najviac ciest s cenou 1. Najlepšie by dokonca bolo, ak by sme nemuseli zrekonštruovať žiadnu cestu s cenou 2.

Čo sa stane ak použijeme postup z podúlohy b), ale spustíme ho iba pre cesty s cenou 1? Medzi niektorými mestami sa bude dať prechádzať a získame tak niekoľko komponentov. V prípade, že nám ostane iba jeden komponent, tak algoritmus môžeme ukončiť, našli sme riešenie s cenou \(n-1\), čo je najmenšia cena, ktorú vieme získať. Čo však v prípade, že tých komponentov ostane viacero?

Uvedomme si, že žiadna cesta s cenou 1 nám už nepomôže. To že sme ju nezrekonštruovali znamená, že vedie medzi dvoma mestami, medzi ktorými sa vieme pohybovať len po zrekonštruovaných cestách. Zároveň sme však použili najväčší počet ciest s cenou 1, aké sme použiť mohli. Skúsili sme totiž každú jednu z nich a nezrekonštruovali sme iba tie, ktoré nám nespojili žiadne dva komponenty. Ostáva nám teda už len pospájať zvyšné komponenty pomocou ciest s cenou 2.

A to vieme spraviť úplne rovnako. Pre každú cestu s cenou 2 sa spýtame, či nám jej zrekonštruovanie pomôže, teda či jej koncové mestá ležia v tom istom komponente. Ak neležia, takúto cestu zrekonštruujeme, čím zmenšíme počet komponentov. Samozrejme, cesty s cenou 1, ktoré sme sa rozhodli zrekonštruovať, pokladáme pri cestách s cenou 2 za zrekonštruované.

postupne pre každú cestu s cenou 1 sprav:
    ak sa mestá na koncoch tejto cesty nachádzajú v rovnakom komponente
    (dá sa medzi nimi dostať iba po zrekonštruovaných cestách), tak:
        s touto cestou nič nerob
    ak sa nenachádzajú v rovnakom komponente, tak:
        zrekonštruuj túto cestu

postupne pre každú cestu s cenou 2 sprav:
    ak sa mestá na koncoch tejto cesty nachádzajú v rovnakom komponente
    (dá sa medzi nimi dostať iba po zrekonštruovaných cestách), tak:
        s touto cestou nič nerob
    ak sa nenachádzajú v rovnakom komponente, tak:
        zrekonštruuj túto cestu

Podúloha d)

Vymyslieť správne riešenie tejto podúlohy, kde má každá cesta inú cenu, by malo byť pomerne jednoduché. Samozrejme, že chceme uprednostňovať lacnejšie cesty. A nechceme vybrať cestu, ktorá spája dve mestá, ktoré už sú v tom istom komponente. Môžeme preto použiť riešenie z podúlohy b), akurát nebudeme cesty spracovávať v ľubovoľnom poradí, ale od najlacnejšej po najdrahšiu. Aj toto je však veľmi ľahko zapísateľné.

usporiadaj všetky cesty od najlacnejšej po najdrahšiu
postupne pre každú cestu v usporiadanom poradí sprav:
    ak sa mestá na koncoch tejto cesty nachádzajú v rovnakom komponente
    (dá sa medzi nimi dostať iba po zrekonštruovaných cestách), tak:
        s touto cestou nič nerob
    ak sa nenachádzajú v rovnakom komponente, tak:
        zrekonštruuj túto cestu

Toto riešenie je dokonca také isté ako riešenie v podúlohe c), aj tam totiž s cestami robíme zakaždým to isté, a spracovávame ich v utriedenom poradí. Najskôr všetky s cenou 1, potom všetky s cenou 2.

To, čo je ťažké na tejto podúlohe je dokázať, že takéto riešenie je správne a naozaj nájde najlacnejšie možné riešenie.

Predpokladajme, že naše riešenie je zlé. To znamená, že existuje iné, optimálne riešenie, v ktorom za zrekonštruovanie zaplatíme najmenšie množstvo dolárov. Vieme, že aj toto riešenie musí rekonštruovať \(n-1\) ciest, rovnako koľko zrekonštruuje aj naše riešenie¹. Tieto dve riešenia sa však v niečom musia líšiť.

Predpokladajme, že optimálne riešenie zrekonštruuje cestu medzi mestami X a Y, ale naše riešenie túto cestu nezrekonštruuje. Prečo to nespraví? Jediný dôvod nezrekonštruovať túto cestu, má naš algoritmus v prípade, ak v okamihu keď sa rozhoduje o zrekonštruovaní tejto cesty, patria mestá X a Y do rovnakého komponentu. To ale znamená, že v Absurdistane existuje medzi mestami X a Y taká trasa, ktorá vedie iba po cestách lacnejších ako cesta z X do Y.

Odkiaľ sme toto zistili? Cesty predsa spracovávame v usporiadanom poradí od najlacnejších. Takže ak sa v našom riešení mestá X a Y nachádzali v tom istom komponente (a preto sme nezrekonštruovali cestu medzi X a Y), tak medzi týmito mestami sa dalo dostať iba po zrekonštruovaných, a teda lacnejších cestách.

Čo to znamená, pre naše optimálne riešenie? Odstráňme z neho cestu medzi X a Y. V takomto riešení sa teraz medzi týmito dvoma mestami nedá dostať. Musíme teda pridať nejakú cestu, ktorou to opravíme. Zoberme si iba cesty z trasy medzi X a Y, ktorá obsahuje iba cesty lacnejšie ako cesta medzi X a Y. Aspoň jedna z týchto ciest toto pokazené optimálne riešenie opraví. Spraví ale aj niečo viac. Keďže pridaná cesta bola lacnejšia ako cesta, ktorú sme odstránili, vytvorili sme riešenie, ktoré je ešte lepšie ako optimálne riešenie. Ale to predsa nie je možné! Čo to znamená? Že sme sa pomýlili v úplne prvom predpoklade, ktorý tvrdil, že naše riešenie je zlé. Naše riešenie je teda naozaj správne a nájde najlacnejšie možné riešenie.

Na obrázku je znázornené to, čo som sa snažil vysvetliť v predchádzajúcom odstavci. Modrou farbou sú znázornené cesty, ktoré zrekonštruuje optimálne riešenie. Oranžové (a červená) cesty označujú trasu medzi mestami X a Y, ktoré obsahujú iba cesty lacnejšie ako priama cesta medzi týmito dvoma mestami. Takúto cestu nám zaručuje naše riešenie a fakt, že naše riešenie nerekonštruuje cestu medzi X a Y. Všimnite si, že ak vymeníme modrú cestu s cenou 10 za červenú cestu s cenou 5, dostaneme riešenie, v ktorom sa stále dá dostať odvšadiaľ všade, ale naviac je o 5 miliónov dolárov lacnejšie.

Záver

Problém, ktorý ste riešili v tomto príklade je problém grafový a volá sa hľadanie najlacnejšej kostry. A algoritmus, ktorý sme si tu predviedli sa skutočne používa, napríklad keď telekomunikácie potrebujú zistiť, kam zakopať káble tak, aby ich to vyšlo čo najlacnejšie, ale aj pri veľa iných problémoch. Názov tohto algoritmu je Kruskalov algoritmus.

V skutočnosti je ešte o chlp komplikovanejší. Aj keď nám ľuďom sa zdá podmienka ak sa dve mestá nachádzajú v rovnakom komponente vcelku jednoduchá a zrozumiteľná, počítačom to až tak jasné nie je. To čo ste vyriešili v tejto úlohe je preto iba polovica problému, druhá polovica sa zaujíma o to, ako má počítač zistiť, či sú dve mestá v tom istom komponente a ako to má zistiť dostatočne rýchlo. To však na riešenie tejto úlohy nebolo potrebné, možno si vás to nájde v nejakom ďalšom kole :)