Pokud bychom hledali libovolné slovo s nejdelším společným koncovým úsekem, stačilo by použít datovou strukturu trie (neboli písmenkový strom – to je zakořeněný strom, v jehož kořeni se rozhodujeme podle prvního písmene slova, na další hladině podle druhého, pak podle třetího, atd.). Do trie bychom přidali všechna slova ze seznamu pozpátku a stejně tak požadované slovo bychom hledali od konce. Ve chvíli, kdy se dostaneme do uzlu u, který nemá vhodného následníka, nebo nalezneme vyhledávané slovo celé, známe nejdelší koncový úsek, kterého můžeme dosáhnout (odpovídá písmenům na cestě z kořene trie do u). Tento koncový úsek však může sdílet více slov – taková slova jsou právě ta, která končí v u nebo v jeho podstromě.
Jak ale vybrat lexikograficky nejmenší? Přímočaré řešení by spočívalo v nalezení všech slov, která se nachází v podstromu u, a následném výběru lexikografického minima. Nalezení všech slov se dá udělat průchodem do hloubky, avšak uvědomíme-li si, že počet takových slov může být srovnatelný s velikostí celého seznamu slov, zjistíme, že jsme si moc nepomohli oproti triviálnímu řešení, které vždy projde celý seznam a má složitost O(maximální délka slova · velikost seznamu).
Pokusme se trii upravit tak, abychom se časově náročnému výběru lexikografického minima vyhnuli. Zapamatujme si v každém uzlu u trie lexikograficky nejmenší slovo (resp. ukazatel na něj, abychom neplýtvali pamětí), mající koncový úsek odpovídající cestě z kořene trie do u. V takto upravené trii budeme moci nalézt lexikograficky nejmenší slovo s maximálním společným úsekem v čase O(délka hledaného slova) a vypsat v čase O(délka minimálního slova), což je jistě optimální, protože to odpovídá času na načtení vstupu a vypsání výsledku. Stejně tak paměťová složitost bude lineární vzhledem k velikosti seznamu, protože velikost abecedy je konstantní a v každém uzlu trie je navíc pouze jeden ukazatel.
Konstrukce takovýchto ukazatelů je celkem jednoduchá, pokud si uvědomíme následující – nechť va, vb, ...vz jsou syny uzlu u. Pak lexikograficky nejmenší slovo v uzlu u stačí vybírat z nejmenších slov v uzlech va, vb, ...vz a případně slova, které končí v u. Stačí tedy procházet trii do hloubky a vždy při návratu z rekurze spočítat pro daný vrchol minimální slovo (těch je maximálně 26, což odpovídá velikosti abecedy, a tedy i počtu synů uzlů trie). Jediný zádrhel je ukryt v porovnávání minimálních slov v každém uzlu trie.
Je totiž potřeba si uvědomit, že synů uzlu je sice konstantní počet, nicméně minimální slova mohou být relativně dlouhá, a tak nalezení všech minimálních slov může trvat až O(maximální délka slova ·velikost seznamu) (velikost trie je lineární vzhledem k velikosti slovníku). To je trochu škoda. My ale naštěstí známe slova dopředu, a tak si je můžeme očíslovat podle lexikografického pořadí a porovnávat jen jejich indexy. Hledané lexikografické pořadí jsme schopni získat za pomoci jiné trie v čase O(velikost seznamu), což je zjevně optimální, a to tak, že nejprve vložíme všechna slova do trie (tentokrát odpředu) a tu pak šikovně celou projdeme (vždy budeme volit „nejmenšího” ještě nepoužitého syna). Tak jsme schopni předzpracovat seznam slov v celkovém čase O(velikost seznamu).
Úlohu bychom řešit mohli přímočaře: Nejprve odstraňme úředníky, kteří nemají žádného (ani nepřímého) podřízeného schopného styku s veřejností (to lze snadno udělat jedním průchodem v čase O(N)). Pro každého úředníka k si pak spočítáme množinu úkonů Uk, které po něm nějaký zájemce může požadovat, a množinu úkonů Vk, které může přeposlat svému nadřízenému.
Smí-li úředník vykonávat úkon u, pak zjevně Vk=Uk\{u}. Má-li úředník na starosti styk s veřejností, pak po něm může být požadován libovolný úkon a Uk={1,2,3,..., M}. Jinak po něm může být požadován libovolný úkon, který mu přepošle jeden z jeho přímých podřízených. Proto Uk je sjednocením všech množin Vi pro úředníky i, kteří jsou přímí podřízení úředníka k. Množiny Uk a Vk tedy můžeme spočítat jedním průchodem stromu úředníků od listů.
Přímo také můžeme vypisovat úředníky, kteří nic nedělají, tj. takové, že u∉Uk. Množiny Uk a Vk si můžeme reprezentovat například polem, v němž je na i-té pozici true, jestliže i patří do množiny, a jinak false. Pak sjednocení dvou množin zabere čas O(M) a počet provedených sjednocení je úměrný počtu úředníků, tedy celková časová složitost bude O(MN).
Toto řešení se dá urychlit, když si místo množin Uk a Vk budeme pamatovat jejich doplňky Uk a Vk. Pak Vk = Uk ∪ {u} a
Uk = ∩(i je přímý podřízený k) Vi.
Pro zrychlení výpočtu průniku si pro každou množinu budeme pamatovat také seznam jejích prvků. Počítáme-li Uk, pak si nejprve vybereme jeho libovolného podřízeného i, z jeho množiny Vi odstraníme prvky, které nepatří do množin ostatních podřízených, a výsledek prohlásíme za Uk. Časová složitost této operace je O(1), jestliže k má jen jednoho přímého podřízeného, a
∑(i je přímý podřízený k) |Vi|
v ostatních případech.
Situaci nám trochu komplikují úředníci, kteří nemají žádné podřízené. Pro ně bychom potřebovali vytvářet nové množiny, což by mohlo dohromady zabrat čas až O(NM). Jak bychom si mohli množiny reprezentovat jinak, abychom zvládli inicializaci v konstantním čase? Jednou možností je použít uspořádaný seznam prvků. V něm pak ale test přítomnosti prvku zabere logaritmický čas, a proto bychom nedosáhli časové složitosti lepší než O(NlogN).
Složitější, ale rychlejší variantou je reprezentace hešovací tabulkou, jejíž velikost dynamicky přizpůsobujeme velikosti reprezentované množiny (detaily najdete třeba v Kuchařce KSP na http://ksp.mff.cuni.cz/tasks/21/cook4.html). Tím zůstane v průměrném případě čas O(1) na test přítomnosti prvku či jeho přidání a ve stejné časové složitosti zvládneme množinu i inicializovat.
Ukažme si, že toto vylepšené řešení má časovou složitost O(N). Kdykoliv přidáme prvek do množiny Uk, abychom vytvořili Vk, dáme mu jednu korunu. Výpočet množiny Uk pro úředníka s nanejvýš jedním přímým podřízeným zvládneme v konstantním čase. Předpokládejme, že počítáme Uk pro úředníka s t≥2 přímými podřízenými.
Jestliže prvek u patří do všech množin Vi těchto podřízených, pak u patří i do Uk a na ověření této skutečnosti spotřebujeme čas O(t). Nicméně, u v množinách podřízených má dohromady t korun, jednu z nich předá prvku u v množině Uk a zbylých t-1=Ω(t) použije na zaplacení spotřebovaného času.
Jestliže prvek u patří jen do r<t z množin podřízených, pak u nepatří do Uk a na ověření této skutečnosti spotřebujeme čas nejvýše O(r). Tento čas se opět zaplatí r korunami, patřícími výskytům u v množinách podřízených. Pomocí korun přiřazených jednotlivým prvkům jsme tedy ukázali, že čas strávený počítáním průniků je omezený časem stráveným přidáváním prvků do množin V, a je tedy O(N).
Existuje ale i jednodušeji implementovatelné řešení se stejnou časovou složitostí. Pro každého úředníka si budeme pamatovat, zda je prokazatelně užitečný, tj. už jsme pro něj dokázali, že něco dělá. Na začátku není nikdo prokazatelně užitečný, kromě ministra. Nyní budeme procházet strom úředníků do hloubky. Při průchodu si budeme udržovat následující:
Dorazíme-li při průchodu k úředníkovi, starajícímu se o styk s veřejností, všechny úředníky v S prohlásíme za prokazatelně užitečné a položíme S={}. Dorazíme-li k úředníkovi k zpracovávajícímu jiný úkon u, pak úředníka na vrcholu Zu smažeme z S a k přidáme do Zu a S. Vracíme-li se z takového úředníka k, pak odstraníme k z S a z Zu, a jestliže nový úředník na vrcholu Zu není prokazatelně užitečný, přidáme ho do S. Na konci vypíšeme úředníky, kteří nejsou prokazatelně užiteční.
V každém vrcholu strávíme pouze konstantně mnoho času, s výjimkou označování úředníků za prokazatelně užitečné. Každého úředníka ale označíme za prokazatelně užitečného nanejvýš jednou, celková časová složitost označování tedy bude jen O(N). Reprezentujeme-li množinu zásobníků Zu polem, pak bude časová složitost O(N+M), jelikož toto pole musíme zinicializovat. Mohli bychom ho samozřejmě reprezentovat i hešovací tabulkou, čímž by se složitost zlepšila na O(N). Ve vzorovém programu to ale pro přehlednost neděláme.
a) Inspirujeme se klasickým tříděním výběrem minima. To funguje tak, že vybíráme nejmenší číslo a přesouváme ho na výstup. Toto opakujeme tak dlouho, dokud ještě něco ve vstupu zbývá.
Na klasickém počítači je tento algoritmu kvadraticky pomalý, ale na grafovém počítači to půjde lépe. K popisu vstupu si pořídíme graf. Pro každé číslo si založíme dva vrcholy a spojíme je hranou. Hranu ohodnotíme hodnotou čísla, značky vrcholů nám budou říkat, o kolikáté číslo v pořadí se jedná.
K výběru nejkratší hrany budeme používat funkci Find. Pokud totiž budeme požadovat, aby nám našla libovolnou hranu (veq a eeq nastavíme na any), pak nám vybere hranu s nejmenším ohodnocením. Pomocí SumE toto ohodnocení snadno zjistíme, vypíšeme ho do výstupu a jelikož víme, o kolikáté číslo se jedná, můžeme ho z grafu odstranit.
Jinými slovy, využili jsme grafový počítač k tomu, aby nám v konstantním čase nacházel nejmenší ze zbývajících čísel. Jelikož počáteční graf vytvoříme v lineárním čase, celkově stihneme všechna čísla setřídit lineárně. Efektivněji to jistě nepůjde, protože každé číslo musíme zapsat na výstup.
procedure razeni(var a: array of Integer; pocet: Integer);
var Sklad, Hrana, Nalezeno: Graph;
i: integer;
begin
{ vytvoření grafu }
Sklad := EmptyG;
for i := 1 to pocet do begin
AddV(Sklad, 2*i - 1);
AddV(Sklad, 2*i);
AddE(Sklad, 2*i - 1, 2*i, a[i]);
end;
{ graf, který budeme hledat: jedna neohodnocená hrana }
Hrana := EmptyG;
AddV(Hrana, undef);
AddV(Hrana, undef);
AddE(Hrana, 1, 2, undef);
{ samotné řazení }
for i := 1 to pocet do begin
Nalezeno := Find(Sklad, Hrana, Any, Any);
a[i] := SumE(Nalezeno);
DelE(Sklad, GetV(Nalezeno, 1), GetV(Nalezeno, 2));
end;
end;
b) Hledaný podgraf je minimální kostrou zadaného grafu. Pro hledání minimální kostry existuje mnoho standardních algoritmů, my použijeme jednu z variant Jarníkova algoritmu. Ten kostru vytváří postupným rozrůstáním. Začne s jedním libovolným vrcholem. Poté v každém kroku vybere nejkratší hranu vedoucí z již sestrojeného stromu do zbytku grafu a tu přidá ke stromu. Tím strom zvětší o jeden vrchol. Toto se opakuje, dokud strom neobsahuje všechny vrcholy.
Důkaz správnosti tohoto algoritmu odložíme na konec, nejprve popíšeme, jak ho rychle implementovat na grafovém počítači.
Představme si, že máme vstupní graf rozdělený na skupinu už propojených vrcholů a skupinu těch zbývajících. Pro každou skupinu si pořídíme nový vrchol a propojíme ho hranami se všemi vrcholy dané skupiny. Potom nalezneme libovolnou cestu délky 3 mezi oběma přidanými vrcholy. Jak mohou takové cesty vypadat? Obě jejich krajní hrany budou zajisté ty námi přidané a uprostřed může být libovolná z původních hran vedoucích mezi skupinami.
Pokud tedy budou mít všechny přidané hrany stejnou délku, nejkratší cesta tohoto typu bude obsahovat nejkratší z hran mezi skupinami, což je přesně to, co potřebujeme.
Po přidání této hrany do stromu stačí nově připojený vrchol přesunout mezi skupinami, a to zvládneme v konstantním čase – zrušíme jednu falešnou hranu a vytvoříme novou.
Jeden krok Jarníkova algoritmu tedy provedeme v konstantním čase a jelikož kostra grafu o n vrcholech obsahuje n-1 hran, je časová složitost našeho algoritmu lineární s počtem vrcholů, tedy O(n).
Ještě dodejme, že naše řešení zachová i původní ohodnocení hran i vrcholů, což zadání nepožadovalo, ale je to tak hezčí.
function min_kostra(g: Graph): Graph;
var Vystup, Cesta, Nalezeno: Graph;
Propojene, Nepropojene: Integer;
i: Integer;
begin
if CountV(g) < 2 then begin
min_kostra := g; exit; { Malé a nezajímavé }
end;
{ Výstupní graf zatím obsahuje všechny vrcholy a žádné hrany }
Vystup := EmptyG;
for i := 1 to CountV(g) do begin
{ Zkopírovat vrchol a nastavit poznávací značku na náš původní }
AddV(Vystup, GetV(g, i));
SetV(g, i, i);
end;
{ Vytvoření skupinek }
Propojene := AddV(g, CountV(g) + 1);
AddE(g, 1, Propojene, 0);
Nepropojene := AddV(g, CountV(g) + 1);
for i := 2 to CountV(g) - 2 do
AddE(g, i, Nepropojene, 0);
{ Vytvoříme cestičku. Značky na vrcholech zaručí, že se
"přilepí" správným koncem na správnou skupinku. }
Cesta := EmptyG;
AddV(Cesta, Propojene);
for i := 1 to 3 do begin
AddV(Cesta, undef);
AddE(Cesta, i, i + 1, undef);
end;
SetV(Cesta, 4, Nepropojene);
{ Pojďme hledat }
for i := 1 to CountV(g) - 3 do begin
{ Nalezneme správnou hranu }
Nalezeno := Find(g, Cesta, Value, Any);
{ Přesuneme vrchol mezi skupinkami }
DelE(g, Nepropojene, GetV(Nalezeno, 3));
AddE(g, Propojene, GetV(Nalezeno, 3), 0);
{ Přidáme hranu do výstupu }
AddE(Vystup, GetV(Nalezeno, 2), GetV(Nalezeno, 3), GetE(Nalezeno, 2, 3));
end;
min_kostra := Vystup;
end;
Na závěr dodejme slíbený důkaz správnosti. Využijeme toho, že nám zadání slibuje, že délky všech hran jsou navzájem různé. Dokážeme následujicí lemma:
Z tohoto lemmatu ihned plyne správnost Jarníkova algoritmu: množina všech hran vedoucích mezi aktuálním stromem a zbylými vrcholy tvoří řez v grafu, vybraná hrana je nejlehčí v tomto řezu.