L04: Optimalizace sítě a „hladové“ algoritmy

V reálném světě nejsou všechna spojení stejná. Chemická vazba mezi dvěma atomy C–C má určitou délku a energii, která je jiná než u vazby C–H (Mimochodem, jaké jsou vazebné energie a délky těchto vazeb?).
Cesta z Prahy do Brna trvá déle než z Prahy do Kladna. Máme tu další terminologii:

• Váha hrany: Číslo přiřazené hraně, které udává jakoby „cenu“ za průchod touto hranou.
• Využití: GPS navigace (nejrychlejší trasa), logistika (nejlevnější rozvoz), biologie (nejmenší energetický výdej při tvorbě cév), chemie (délka vazeb) atd.

Představte si, že máte propojit několik vesnic optickým kabelem. Nebo že tkáň potřebuje vyživit skupinu buněk novými cévami (proces zvaný angiogeneze). Cílem je propojit VŠECHNY uzly tak, aby se spotřebovalo co NEJMÉNĚ materiálu a energie.

Výsledná síť musí mít dvě základní vlastnosti:

1. Je to strom (kostra): Nesmí tam být žádné cykly (kruhy). Cyklus znamená, že jsme někam natáhli zbytečný kabel nebo cévu navíc.
2. Je minimální: Součet vah všech použitých hran je nejmenší možný.

Jak příroda (nebo počítač) najde nejlevnější kostru? Používá takzvaný Hladový algoritmus. „Hladový“ se mu říká proto, že se v každém kroku snaží urvat to aktuálně nejlepší a nejlevnější sousto, aniž by dlouze plánoval dopředu.

Postup (Algoritmus – zkus si ho nakreslit :-)):

1. Vypiš si všechny existující hrany a seřaď je od nejlevnější po nejdražší.
2. Vezmi tu úplně nejlevnější hranu a nakresli ji (přidej do sítě).
3. Vezmi další nejlevnější hranu v pořadí.
   • Zeptej se: „Nevytvoří tato hrana cyklus (kruh) s těmi, co už mám nakreslené?“
     • ANO, vytvoří: Hranu zahoď, je zbytečná.
     • NE, nevytvoří: Hranu nakresli (přidej do sítě).
4. Kroky opakuj od bodu 2, dokud nejsou propojeny všechny uzly.

Úkol: Po ničivé vichřici v horské oblasti spadly všechny sloupy elektrického vedení. K dispozici máme jen omezené množství drahého kabelu. Naším úkolem je co nejlevněji propojit elektrárnu (E) se třemi kritickými body: nemocnicí (N), školou (Š) a vodárnou (V).
Vyzkoušej si algoritmus na návrhu propojení těchto několika míst ve městě elektrickou sítí. Výchozí situaci popisuje tato matice:

A jak vypadá graf, z této matice?

Obr. 1: Ukázka grafu elektrické sítě s vyznačenou váhou hran (vzdáleností v km).

Jak bude vypadat minimální kostra tohoto grafu? Aplikujme společně Kruskalův algoritmus...

Překvapivé zjištění matematiky: Přestože algoritmus uvažuje jen o aktuálně nejlevnějším kroku a nijak „neplánuje“, u hledání minimální kostry tento „hloupý“ postup zaručeně vede k absolutně nejlepšímu celkovému výsledku!

Řešení bylo jednoduché, protože jsme nemuseli žádnou hranu zahazovat. Stačilo vzít tři „nejlevnější“ hrany :-).

Obr. 2: Ukázka grafu elektrické sítě s vyznačenou váhou hran (vzdáleností v km) a nalezenou minimální kostrou grafu (zeleně).