Recepty z programátorské kuchařky
Minimální kostra

Představme si následující problém: Chceme určit silnice, které se budou v zimě udržovat sjízdné, a to tak, abychom celkově udržovali co nejméně kilometrů silnic, a přesto žádné město od ostatních neodřízli.

Města a silnice si můžeme představit jako graf, o kterém nyní budeme předpokládat, že je souvislý. Kdyby nebyl, náš problém nijak vyřešit nelze. Výsledný podgraf/seznam silnic, který řeší náš problém se sněhem, nazývají matematici minimální kostra grafu.

Pokud vůbec netušíte, co je to graf, přečtěte si úvodní grafovou kuchařku.

Co se v souvislém grafu přesně myslí pod pojmem kostra? Nazveme jí libovolný podgraf, který obsahuje všechny vrcholy a zároveň je stromem. Strom jsme si definovali v kuchařce o grafech; jsou to přesně ty grafy, které jsou souvislé (z každého vrcholu „dojedeme“ do každého jiného) a bez kružnice (takže nemáme v silniční síti žádné přebytečné cesty).

Pokud každou hranu grafu ohodnotíme nějakou vahou, což v našem případě bude vždy kladné číslo, dostaneme ohodnocený graf. V takových grafech pak obvykle hledáme mezi všemi kostrami kostru minimální, což je taková, pro kterou je součet vah jejích hran nejmenší možný.

Graf může mít více minimálních koster – například jestliže jsou všechny váhy hran jedničky, všechny kostry mají stejnou váhu n-1 (kde n je počet vrcholů grafu), a tedy jsou všechny minimální.

Pro vyřešení problému hledání minimální kostry se nám bude hodit datová struktura Disjoint-Find-Union (DFU). Ta umí pro dané disjunktní množiny (disjunktní znamená, že každé 2 množiny mají prázdný průnik neboli žádné společné prvky) rychle rozhodnout, jestli dva prvky patří do stejné množiny, a provádět operaci sjednocení dvou množin.

Algoritmus

Algoritmus na hledání minimální kostry, který si předvedeme, je typickou ukázkou tzv. hladového algoritmu. Nejprve setřídíme hrany vzestupně podle jejich váhy. Kostru budeme postupně vytvářet přidáváním hran od té s nejmenší vahou tak, že hranu do kostry přidáme právě tehdy, pokud spojuje dvě (prozatím) různé komponenty souvislosti vytvořeného podgrafu. Jinak řečeno, hranu do vytvářené kostry přidáme, pokud v ní zatím neexistuje cesta mezi vrcholy, které zkoumaná hrana spojuje.

Je zřejmé, že tímto postupem získáme kostru, tj. acyklický podgraf grafu, který je souvislý (pokud vstupní graf je souvislý, což mlčky předpokládáme). Než si ukážeme, že nalezená kostra je opravdu minimální, podívejme se na časovou složitost našeho algoritmu: Pokud vstupní graf má N vrcholů a M hran, tak úvodní setřídění hran vyžaduje čas O(M log M) (použijeme některý z rychlých třídicích algoritmů popsaných v jednom z minulých dílů kuchařky) a poté se pokusíme přidat každou z M hran.

V druhé části kuchařky si ukážeme datovou strukturu, s jejíž pomocí bude M testů toho, zda mezi dvěma vrcholy vede hrana, trvat nejvýše O(M log N). Celková časová složitost našeho algoritmu je tedy O(M log N) (všimněte si, že log M≤ log N²=2 log N). Paměťová složitost je lineární vzhledem k počtu hran, tj. O(M).

Důkaz správnosti

Zbývá dokázat, že nalezená kostra vstupního grafu je minimální. Bez újmy na obecnosti můžeme předpokládat, že váhy všech hran grafu jsou navzájem různé: Pokud tomu tak není již na začátku, přičteme k některým z hran, jejichž váhy jsou duplicitní, velmi malá kladná celá čísla tak, aby pořadí hran nalezené naším třídicím algoritmem zůstalo zachováno. Tím se kostra nalezená hladovým algoritmem nezmění, a pokud bude tato kostra minimální s modifikovanými váhami, bude minimální i pro původní zadání.

Označme si nyní T_alg kostru nalezenou hladovým algoritmem a T_min nějakou minimální kostru. Co by se stalo, kdyby byly různé? Víme, že všechny kostry mají stejný počet hran, takže musí existovat alespoň jedna hrana e, která je v T_alg, ale není v T_min. Ze všech takových hran si vyberme tu, která má nejmenší váhu, tedy kterou algoritmus přidal jako první. Když se podíváme na stav algoritmu těsně před přidáním e, vidíme, že sestrojil nějakou částečnou kostru F, která je ještě součástí jak T_min, tak T_alg.

Přidejme nyní hranu e ke kostře T_min. Tím vznikl podgraf vstupního grafu, který zjevně obsahuje nějakou kružnici C – už před přidáním hrany e totiž T_min byla souvislá. Protože kostra T_alg neobsahuje žádnou kružnici, na kružnici C musí být alespoň jedna hrana e^′, která není v T_alg.

Všimněme si, že hranu e^′ nemohl algoritmus zpracovat před hranou e: hrana e^′ neleží v T_min na žádném cyklu, takže tím spíš netvoří cyklus v F, a kdyby ji algoritmus zpracoval, musel by ji přidat do F, což, jak víme, neučinil. Z toho plyne, že váha hrany e^′ je větší než váha hrany e. Když nyní z kostry T_min odebereme hranu e^′ a přidáme místo ní hranu e, musíme opět dostat souvislý podgraf (e a e^′ přeci ležely na společné kružnici), tudíž kostru vstupního grafu. Jenže tato kostra má celkově menší váhu než minimální kostra T_min, což není možné. Tím jsme došli ke sporu, a proto T_min a T_alg nemohou být různé.

Cvičení

• V důkazu jsme předpokládali, že váhy hran jsou různé (resp. jsme je různými udělali). Není potřeba i v samotném algoritmu přičítat velmi malá čísla k hranám se stejnou vahou?

Disjoint-Find-Union

Datová struktura DFU slouží k udržování rozkladu množiny na několik disjunktních podmnožin (čili takových, že žádné dvě nemají společný prvek). To znamená, že pomocí této struktury můžeme pro každé dva z uložených prvků říci, zda patří či nepatří do stejné podmnožiny rozkladu.

V algoritmu hledání minimální kostry budou prvky v DFU vrcholy zadaného grafu a budou náležet do stejné podmnožiny rozkladu, pokud mezi nimi v již vytvořené části kostry existuje cesta. Jinými slovy podmnožiny v DFU budou odpovídat komponentám souvislosti vytvářené kostry.

S reprezentovaným rozkladem umožňuje datová struktura DFU provádět následující dvě operace:

• find: Test, zda dva prvky leží ve stejné podmnožině rozkladu. Tato operace bude v případě našeho algoritmu odpovídat testu, zda dva vrcholy leží ve stejné komponentě souvislosti.
• union: Sloučení dvou podmnožin do jedné. Tuto operaci v našem algoritmu na hledání kostry provedeme vždy, když do vytvářené kostry přidáme hranu (tehdy spojíme dvě různé komponenty souvislosti dohromady).

Povězme si nejprve, jak budeme jednotlivé podmnožiny reprezentovat. Prvky obsažené v jedné podmnožině budou tvořit zakořeněný strom. V tomto stromu však povedou ukazatele (trochu nezvykle) od listů ke kořeni. Operaci find lze pak jednoduše implementovat tak, že pro oba zadané prvky nejprve nalezneme kořeny jejich stromů. Jsou-li tyto kořeny stejné, jsou prvky ve stejném stromu, a tedy i ve stejné podmnožině rozkladu. Naopak, jsou-li různé, jsou zadané prvky v různých stromech, a tedy jsou i v různých podmnožinách reprezentovaného rozkladu. Operaci union provedeme tak, že mezi kořeny stromů reprezentujících slučované podmnožiny přidáme ukazatel a tím tyto dva stromy spojíme dohromady.

Implementace dvou výše popsaných operací, jak jsme se ji právě popsali, následuje. Pro jednoduchost množina, jejíž rozklad reprezentujeme, bude množina čísel od 1 do N. Rodiče jednotlivých vrcholů stromu si pak pamatujeme v poli parent, kde 0 znamená, že prvek rodiče nemá, tj. že je kořenem svého stromu. Funkce root(v) vrátí kořen stromu, který obsahuje prvek v.

var parent: array[1..N] of integer;

procedure init;
var i: integer;
begin
  for i:=1 to N do parent[i]:=0;
end;

function root(v: integer):integer;
begin
  if parent[v]=0 then root:=v
  else root:=root(parent[v]);
end;

function find(v, w: integer):boolean;
begin
  find:=(root(v)=root(w));
end;

procedure union(v, w: integer);
begin
  v:=root(v); w:=root(w);
  if v<>w then parent[v]:=w;
end;

S právě předvedenou implementací operací find a union by se ale mohlo stát, že stromy odpovídající podmnožinám budou vypadat jako „hadi“, a pokud budou obsahovat N prvků, na nalezení kořene bude potřeba čas O(N).

Ke zrychlení práce DFU se používají dvě jednoduchá vylepšení:

• union by rank: Každý prvek má přiřazen rank. Na začátku jsou ranky všech prvků rovny nule. Při provádění operace union připojíme strom s kořenem menšího ranku ke kořeni stromu s větším rankem. Ranky kořenů stromů se v tomto případě nemění. Pokud kořeny obou stromů mají stejný rank, připojíme je libovolně, ale rank kořenu výsledného stromu zvětšíme o jedna.
• path compression: Ve funkci root(v) přepojíme všechny prvky na cestě od prvku v ke kořeni rovnou na kořen, tj. změníme jejich rodiče na kořen daného stromu.

Než si obě metody blíže rozebereme, podívejme se, jak se změní implementace funkcí root a union:

var parent: array[1..N] of integer;
    rank: array[1..N] of integer;

procedure init;
var i: integer;
begin
  for i:=1 to N do
    begin
      parent[i]:=0;
      rank[i]:=0;
    end;
end;

{změna path compression}
function root(v: integer): integer;
begin
  if parent[v]=0 then root:=v
  else begin
    parent[v]:=root(parent[v]);
    root:=parent[v];
  end;
end;

{stejná jako minule}
function find(v, w: integer):boolean;
begin
  find:=(root(v)=root(w));
end;

{změna kvůli union by rank}
procedure union(v, w: integer);
begin
  v:=root(v);
  w:=root(w);
  if v=w then exit;
  if rank[v]=rank[w] then
    begin
      parent[v]:=w;
      rank[w]:=rank[w]+1;
    end
  else if rank[v]<rank[w] then
    parent[v]:=w
  else
    parent[w]:=v;
end;

Zaměřme se nyní blíže na metodu union by rank. Nejprve učiníme následující pozorování: Pokud je prvek v s rankem r kořenem stromu v datové struktuře DFU, pak tento strom obsahuje alespoň 2^r prvků.

Naše pozorování dokážeme indukcí podle r. Pro r=0 tvrzení zřejmě platí. Nechť tedy r>0. V okamžiku, kdy se rank prvku v mění z r-1 na r, slučujeme dva stromy, jejichž kořeny mají rank r-1. Každý z těchto dvou stromů má dle indukčního předpokladu alespoň 2^r-1 prvků, a tedy výsledný strom má alespoň 2^r prvků, jak jsme požadovali.

Z našeho pozorování ihned plyne, že rank každého prvku je nejvýše  log₂ N a prvků s rankem r je nejvýše N/2^r (všimněme si, že rank prvku v DFU se nemění po okamžiku, kdy daný prvek přestane být kořen nějakého stromu).

Když tedy provádíme jen union by rank, je hloubka každého stromu v DFU rovna ranku jeho kořene, protože rank kořene se mění právě tehdy, když zvětšujeme hloubku stromu o jedna. A protože rank každého prvku je nanejvýš  log₂ N, hloubka každého stromu v DFU je také nanejvýš  log₂ N. Potom ale procedura root spotřebuje čas nejvýše O(log N), a tedy operace find a union stihneme v čase O(log N).

Amortizovaná časová složitost

Abychom mohli pokračovat dále, musíme si vysvětlit, co je amortizovaná časová složitost. Řekneme, že nějaká operace pracuje v amortizovaném čase O(t), pakliže provedení libovolných k takových operací trvá nejvýše O(kt). Přitom provedení kterékoliv konkrétní z nich může vyžadovat čas větší. Tento větší čas je pak v součtu kompenzován kratším časem, který spotřebovaly některé předchozí operace.

Nejdříve si předveďme tento pojem na jednoduchém příkladě. Řekněme, že máme číslo zapsané ve dvojkové soustavě. Přičíst k tomuto číslu jedničku jistě netrvá konstantní čas, neboť záleží na tom, kolik jedniček se vyskytuje na konci zadaného čísla. Pokud se nám ale povede ukázat, že N přičtení jedničky k číslu, které je na počátku nula, zabere čas O(N), pak můžeme říci, že každé takové přičtení trvalo amortizovaně O(1).

Jak tedy ukážeme, že N přičtení jedničky k číslu zabere čas O(N)? Použijeme k tomu „penízkovou metodu“. Každá operace nás bude stát jeden penízek, a pokud jich na N operací použijeme jen O(N), bude tvrzení dokázáno.

Každé jedničce, kterou chceme přičíst, dáme dva penízky. V průběhu celého přičítání bude platit, že každá jednička ve dvojkovém zápisu čísla má jeden penízek (když začneme jedničky přičítat k nule, tuto podmínku splníme). Přičítání bude probíhat tak, že přičítaná jednička se „podívá“ na nejnižší bit (tj. ve dvojkovém zápisu na poslední cifru) zadaného čísla (to ji stojí jeden penízek). Pokud je to nula, změní ji na jedničku a dá jí svůj zbylý penízek. Pokud to je jednička, vezme si přičítaná jednička její penízek (čili už má zase dva), změní zkoumanou jedničku na nulu a pokračuje u dalšího bitu, atd.

Takto splníme podmínku, že každá jednička v dvojkovém zápisu čísla má jeden penízek. Tedy N přičítání nás stojí 2N penízků. Protože počet penízků utracených během jedné operace je úměrný spotřebovanému času; vidíme, že všech N přičtení proběhne v čase O(N). Není těžké si uvědomit, že přičtení některých jedniček může trvat až O(log N), ale amortizovaná časová složitost přičtení jedné jedničky je konstantní.

Dokončení analýzy DFU

Pokud bychom prováděli pouze path compression a nikoliv union by rank, dalo by se dokázat, že každá z operací find a union vyžaduje amortizovaně čas O(log N), kde N je počet prvků. Toto tvrzení nebudeme dokazovat, protože tím bychom si nijak oproti samotnému union by rank nepomohli. Proč tedy vlastně hovoříme o obou vylepšeních? Inu proto, že při použití obou metod současně dosáhneme mnohem lepšího amortizovaného času O(α(N)) na jednu operaci find nebo union, kde α(N) je inverzní Ackermannova funkce. Její definici můžete nalézt na konci kuchařky, zde jen poznamenejme, že hodnota inverzní Ackermannovy funkce α(N) je pro všechny praktické hodnoty N nejvýše čtyři. Čili dosáhneme v podstatě amortizovaně konstantní časovou složitost na jednu (libovolnou) operaci DFU.

Dokázat výše zmíněný odhad časové složitosti funkcí α(N) je docela těžké, my si zde předvedeme poněkud horší, ale technicky výrazně jednodušší časový odhad O((N+L) log ^* N), kde L je počet provedených operací find nebo union a log ^* N je tzv. iterovaný logaritmus, jehož definice následuje. Nejprve si definujeme funkci 2↑k rekurzivním předpisem:

Máme tedy 2↑1=2, 2↑2=2²=4, 2↑3=2⁴=16, 2↑4=2¹⁶=65536, 2↑5=2⁶⁵⁵³⁶, atd. A konečně, iterovaný logaritmus  log ^* N čísla N je nejmenší přirozené číslo k takové, že N≤ 2↑k. Jiná (ale ekvivalentní) definice iterovaného logaritmu je ta, že log ^* N je nejmenší počet, kolikrát musíme číslo N opakovaně zlogaritmovat, než dostaneme hodnotu menší nebo rovnu jedné.

Zbývá provést slíbenou analýzu struktury DFU při současném použití obou metod union by rank a path compression. Prvky si rozdělíme do skupin podle jejich ranku: k-tá skupina prvků bude tvořena těmi prvky, jejichž rank je mezi (2↑(k-1))+1 a 2↑k. Např. třetí skupina obsahuje ty prvky, jejichž rank je mezi 5 a 16. Prvky jsou tedy rozděleny do 1+ log ^* log N=O(log ^* N) skupin. Odhadněme shora počet prvků v k-té skupině:

Teď můžeme provést časovou analýzu funkce root(v). Čas, který spotřebuje funkce root(v), je přímo úměrný délce cesty od prvku v ke kořeni stromu. Tato cesta je pak následně rozpojena a všechny prvky na ní jsou přepojeny přímo na kořen stromu. Rozdělíme rozpojené hrany této cesty na ty, které „naúčtujeme“ tomuto volání funkce root(v), a ty, které zahrneme do faktoru O(N log ^* N) v dokazovaném časovém odhadu. Do volání funkce root(v) započítáme ty hrany cesty, které spojují dva prvky, které jsou v různých skupinách. Takových hran je zřejmě nejvýše O(log ^* N) (všimněte si, že ranky prvků na cestě z listu do kořene tvoří rostoucí posloupnost).

Uvažme prvek v v k-té skupině, který již není kořenem stromu. Při každém přepojení rank rodiče prvku v vzroste. Tedy po 2↑k přepojeních je rodič prvku v v (k+1)-ní nebo vyšší skupině. Pokud v je prvek v k-té skupině, pak hrana z něj na cestě do kořene bude účtována volání funkce root(v) nejvýše (2↑k)-krát. Protože k-tá skupina obsahuje nejvýše N/(2↑k) prvků, je počet takových hran pro všechny prvky této skupiny nejvýše N. A protože počet skupin je nejvýše O(log ^* N), je celkový počet hran, které nejsou započítány voláním funkce root(v), nejvýše O(N log ^* N). Protože funkce root(v) je volána 2L-krát, plyne časový odhad O((N+L) log ^* N) z právě dokázaných tvrzení.

Inverzní Ackermannova funkce α(N)

Ackermannovu funkci lze definovat následující konstrukcí:

Ackermannova funkce s jedním parametrem A(k) je pak rovna hodnotě A_k(2), takže A(2)=A₂(2)=8, A(3)=A₃(2)=2¹¹, A(4)=A₄(2)≈ 2↑2048 atd… Hodnota inverzní Ackermannovy funkce α(N) je tedy nejmenší přirozené číslo k takové, že N≤ A(k)=A_k(2). Jak je vidět, ve všech reálných aplikacích platí, že α(N)≤ 4.

Dan Kráľ, Martin Mareš a Milan Straka