Nejdříve krátce zmíníme přímočaré řešení. Vyzkoušíme jednoduše odebrat postupně všechny možné podmnožiny vagónů a vybereme z nich minimální takovou, že zbylé vagóny tvoří palindrom. Toto řešení však vyžaduje vyzkoušení 2N podmnožin, což je neúměrně mnoho.
Zkusme úlohu vyřešit po krocích. Předpokládejme, že umíme vyřešit případ, kdy nám magicky zmizely některé vagóny. Pokud si budeme vlak představovat jako posloupnost V1..N = a1a2a3..aN-1aN, pak Vi..j je vlak tvořený aiai+1..aj-1aj.
Podívejme se, jak lze z řešení pro vlaky kratší délky vytvořit řešení pro celý vlak. Pokud a1 = aN, pak můžeme předpokládat, že se oba vagóny vyskytují v optimálním řešení pro celý vlak. Stačí tedy k řešení pro vlak V2... n-1 přidat vagóny a1 a aN. Pokud a1≠aN, pak se oba vagóny nemohou vyskytovat v řešení pro celý vlak a nejlepším řešením pro celý vlak je lepší z řešení pro vlaky V1...n-1 a V2...n.
Na této myšlence je postavený algoritmus, který běží v čase O(N2). Úlohu vyřešíme dynamickým programováním přes všechny podvlaky. Na začátku víme, že vlak délky 1 je palindromický, a tedy je sám sobě optimálním řešením. Poté určíme řešení pro všechny podvlaky délky 2, pak délky 3 a nakonec nalezneme řešení pro celý vlak.
Kdyby nám stačila jen informace o největší možné délce vlaku, vystačili bychom s lineární pamětí – pamatovali bychom si jen řešení pro vlaky délek o jedna a o dvě menší. Nicméně když potřebujeme vypsat i konkrétní vynechané vagóny, vyroste nám paměť na kvadratickou.
Poznámka: Kvadratické paměti se lze vyhnout i v obecném případě šikovným použitím metody Rozděl a panuj. Všimneme si, že když budeme vytvářet nejdelší palindrom postupným odpojováním vagónů od kraje vlaku (což přesně naše řešení dělá), nutně musíme potkat situaci, v níž bude délka aktuálního vlaku právě ⌊N/2⌋ nebo ⌊N/2⌋+1.
Podobně jako jsme v prostoru O(N) dovedli spočítat, jak dlouhé je optimální řešení, můžeme v tomtéž prostoru zjistit i to, jak bude vypadat tento poloviční podvlak na cestě k optimálnímu řešení. Optimální řešení pro vlak αβγ (kde β je onen poloviční podvlak) se tedy musí skládat s optimálního řešení pro vlak β spojeného s optimálním řešením pro vlak α*γ, kde * je vagón, který není povoleno odebrat.
Jinými slovy, v čase Ω(N2) jsme úlohu převedli na dvě úlohy poloviční velikosti, takže pro časovou složitost celého algoritmu musí platit rovnice T(N) = Ω(N2) + 2T(N/2), která má řešení T(N)=Ω(N2). Časová složitost je tedy stále kvadratická a prostoru jsme spotřebovali pouze lineárně.
Asi nikoho moc nepřekvapí, že hledaným útvarem je konvexní obal množiny bodů v rovině – každý strom s jablky budeme pokládat za bod. Proč tomu tak je? Pokud bychom vzali jakýkoliv nekonvexní útvar, má jeho konvexní obal menší obvod a přitom ho celý obsahuje, a tedy i všechny zadané body. A konvexní obal je naopak podmnožinou všech konvexních útvarů, ve kterých leží zadané body.
Nalézt konvexní obal zadané množiny bodů v rovině je celkem známý problém, pro který existuje algoritmus pracující v čase O(N ·logN).
Zopakujme si tedy některá tvrzení, která pro konvexní obal platí:
Konvexní obal můžeme rozdělit na horní a dolní část, začátkem obou částí bude nejlevější bod, koncem pak nejpravější. Ještě se pozastavme nad případem, že nejlevějších (resp. nejpravějších bodů) je více – příkladem je obdélník rovnoběžný s osami. Zakažme si tedy přítomnost svislých hran v konvexním obalu, protože se vyskytují pouze na levém a pravém okraji.
Za začátek horní resp. dolní části obalu (říkejme jim poloobaly) zvolíme nejhořejší resp. nejspodnější z nejlevějších bodů. Analogicky budeme postupovat pro konce těchto poloobalů. V případě obdélníku bude horním poloobalem pouze jeho horní strana rovnoběžná s osou x, dolním poloobalem pak spodní strana rovnoběžná s osou x. Ptáte se: kam se poděly strany rovnoběžné s osou y? Tyto „opomenuté” svislé hrany jsou vždy spojnicí začátků resp. konců horního a dolního poloobalu. Často se stane, že začátky těchto poloobalů splývají, délka této spojnice je potom nulová.
Kdybychom konvexní obal počítali jen jednou pro pevně zadanou množinu bodů, nejprve bychom si body setřídili zleva doprava a postupně jimi doplňovali horní a dolní poloobal. Fundamentální částí běžného algoritmu je řešení momentu, kdy jsme přidáním nového bodu do poloobalu způsobili, že náš předchůdce svírá vnitřní úhel větší než 180°. Tohoto předchůdce z poloobalu odebereme a tuto kontrolu zopakujeme na svém novém levém předchůdci. Takto můžeme klidně odebrat skoro všechny body, až kromě prvního, nejlevějšího.
My nahlédneme, že z tohoto postupu lze snadno vyjít. Po přidání nového bodu poopravíme daný poloobal jak směrem vlevo tak vpravo.
Zaměřme se na tuto otázku: Máme hotový konvexní obal (tedy oba poloobaly) a snažíme se přidat jeden bod. Pokud je přidaný bod uvnitř obalu, není co řešit. Pokud je vně, budeme muset obal o tento bod doplnit. Dokonce lze s jistotou říci, že bude jedním z vrcholů nového konvexního obalu.
Předpokládejme tedy, že nový bod leží nad horním poloobalem; pro spodní poloobal budeme postupovat symetricky. Protože body na poloobalu jdou za sebou přesně podle pořadí svých x-ových souřadnic, podíváme se nejprve, mezi které dva body poloobalu se nový bod začlení. Zatím předpokládejme, že nový bod není ani nejlevějším ani nejpravějším bodem ze všech, které budou v horním poloobalu. Přidáním nového bodu do posloupnosti bodů na horním poloobalu se mohly stát dvě věci: buď všechny vrcholy svírají vnitřní úhel menší (nebo roven) 180° a všechno je v pořádku, nebo se tento předpoklad u některého bodu porušil. Jediné dva body, u kterých může být nyní úhel větší než 180°, je přímý předchůdce (levý soused) a přímý následník (pravý soused) našeho nového bodu. Co se týká levého předchůdce, nápravu této chyby už známe z předchozího algoritmu – budeme prostě své přímé předchůdce zahazovat tak dlouho, dokud bude jejich vnitřní úhel nepřípustný. Pro pravého souseda budeme postupovat analogicky.
Snadno se dovtípíme, že pokud bude levý i pravý soused po aplikaci tohoto postupu svírat správný úhel, máme poloobal korektně doplněný o nový bod. Nově přidaný bod totiž z principu nemůže svírat nepřípustný úhel a u ostatních bodů se nic nezměnilo. Při každém přidání, resp. odebrání vrcholu si stačí pouze průběžně ukládat, o kolik se změnil obvod konvexního poloobalu.
Pokud byl nově přidaný bod nejlevější resp. nejpravější, můžeme prostě vynechat kontrolu vnitřního úhlu pro odpovídající (neexistující) sousedy. Jenom mějme na paměti, že jsme si zakázali svislé hrany v poloobalu, takže pokud například nový nejlevější bod má stejnou souřadnici x jako levý začátek horního poloobalu a přitom neleží výše, bez obav ho zahodíme.
Nyní se podívejme, jak tento algoritmus implementovat. Předně potřebujeme umět rychle najít své levé a pravé sousedy podle souřadnice x, dále pak chceme umět rychle odebírat a přidávat body. Pole nebo seznam zřejmě nejsou dobrou volbou. Naopak binární vyhledávací strom nám plně vyhovuje. Budeme si tedy každý z poloobalů udržovat v jednom takovém vyhledávacím stromě (můžeme zvolit AVL, Červeno-černý, .. záleží pouze na časové složitosti jeho operací).
Abychom nemuseli pro horní poloobal zkoumat, co leží nad ním, a naopak pro dolní poloobal, co leží pod ním, provedeme jednoduchý trik. Dolní poloobal si otočíme podle osy x a jednoduše s ním budeme pracovat identicky jako s horním.
Ještě jedna technická poznámka: svislé hrany jsme si zakázali právě proto, aby nám nedělaly problémy při uspořádání bodů ve stromě. Všimněme si totiž, že nejlevější body by se musely třídit vzestupně podle y, naopak nejpravější body sestupně.
Celý algoritmus tedy funguje takto:
Na počátku si vezmeme první bod a vytvoříme z něho oba konvexní poloobaly, leč degenerované. (Po přidání druhého bodu budou oba poloobaly totožné úsečky, ale ani to nám nevadí.) Pak pouze přidáváme bod po bodu a doplňujeme tyto poloobaly podle potřeby. Přitom se díváme, jak se mění obvod celého obalu. Je už jen triviálním krokem, že pro body zadané na počátku vypíšeme celkový obvod konvexního obalu a pro následujících M bodů vypisujeme pouze změnu obvodu. Technickou drobností je, že přitom musíme kalkulovat se svislými spojnicemi začátků a konců horního a dolního poloobalu.
Jak efektivní náš algoritmus bude?
Každému z N + M bodů vhodně naúčtujeme kroky výpočtu a uvidíme, že výsledek je překvapivě uspokojivý. Vložení nového bodu naúčtujeme právě jemu, tedy odhadem O(log(N + M)). Kontrolu vnitřního úhlu, která dopadla dobře, a nalezení sousedů těchto sousedů, pro které kontrola dopadla dobře, rovněž napočítáme nově vkládanému bodu – O(log(N + M)). Naopak neúspěšnou kontrolu a následné odebrání odpovídajícího bodu naúčtujeme odebíranému bodu – O(log (N + M)). Každá operace je zaúčtována, zároveň každý bod je přidán a odebrán maximálně jednou. Tedy součtem přes všechny body dostáváme O((N + M) ·log (N + M)). Zajímavé je, že stejnou složitost má i zmíněný standardní algoritmus pro konvexní obal, pokud bychom ho spustili pouze na konci na všechny body dohromady.
Paměťová efektivita je rovněž O(N + M), protože pro každý poloobal si držíme jeden vyhledávací strom, který může v nejhorším případě obsahovat všechny body (přesněji toto může nastat leda pro oba stromy v součtu, ale pro horní odhad nám to stačí).
Vzorové řešení je naprogramováno v jazyce C++, kde jsme si ušetřili implementaci vyhledávacích stromů použitím typu set z STL.
Nechť pořadí mažoretek na vstupu je (a1,...,aN). Pokud a1>...>aN, pak pořadí odpovídá poslednímu dni v roce a následující den budou mažoretky pochodovat v pořadí (1,...,N). Předpokládejme nyní, že pořadí neodpovídá poslednímu dni v roce, a zamysleme se, jak vypadají pořadí v jeho zbylých dnech.
Uvažme nyní dvě pořadí (b1,...,bN) a (b'1,...,b'N), která se v témže roce objeví později. Označme i nejmenší index s ai≠bi a i' nejmenší index s ai≠b'i. Pokud i<i', pak ai=b'i<bi a tedy mažoretky v pořadí (b'1,...,b'N) pochodují dříve, než v pořadí (b1,...,bN). Pro pořadí mažoretek následující hned po (a1,...,aN) proto platí, že mezi všemi pořadími, která následují v aktuálním roce po tomto pořadí, má s pořadím (a1,...,aN) nejdelší počáteční úsek.
Zaměřme se na to, jak takový úsek nalézt. Pokud pro nějaké i platí, že se mezi čísly ai+2,...,aN vyskytuje číslo větší než ai+1, pak existuje pořadí, které následuje po (a1,...,aN) a má s tímto pořadím společný počáteční úsek délky i. Musíme tedy najít nejmenší index i takový, že ai+1>...>aN.
Pokud takový index i nalezneme, pak ai nahradíme nejmenším číslem mezi ai+1,...,aN, které je větší než ai, a následující čísla seřadíme podle velikosti od nejmenšího.
Popsaný algoritmus lze implementovat v lineárním čase, a to následovně. Od konce zadané posloupnosti nalezneme nejmenší index i takový, že ai+1>...>aN. Pokud je i=0, pak a1>...>aN a vypíšeme posloupnost 1,...,N. Předpokládejme tedy, že i není nula. Mezi čísly ai+1,...,aN nalezneme nejmenší číslo větší než ai (takové existuje, neboť ai+1>ai) a prohodíme ho s ai. Povšimněme si, že úsek posloupnosti po ai je stále sestupně seřazen. Stačí ho tedy nyní jen zrcadlově otočit a výsledné pořadí vypsat.
Opět označme (a1,...,aN) pořadí zadané na vstupu. Vyřešme nejdříve úlohu pro sudá N. Počet pořadí se shodným prvním číslem je (N-1)!. Pokud a1≤N/2, pak hledané pořadí začíná číslem b1=a1+N/2; pokud a1>N/2, pak začíná číslem b1=a1-N/2. A pokud je mezi pořadími, která začínají a1, pořadí (a1,...,aN) k-té, pak hledáme k-té pořadí, které začíná b1. Takové ale snadno nalezneme – pokud ai, 2≤i≤N, je l-tý nejmenší prvek mezi {1,...,N}\{a1}, pak bi bude l-tý nejmenší prvek mezi {1,...,N}\{b1}.
Jestliže tedy a1≤N/2, pak pořadí (b1,...,bN) za půl roku bude
bi =
Analogický vzorec platí, jestliže a1>N/2.
Pro lichá N je situace komplikovanější. Potřebujeme určit pořadí za N!/2 dní. Nejdříve určíme pořadí za ⌊N/2⌋(N-1)! dní stejně jako v případě, kdy N bylo sudé (místo N/2 k a1 přičteme ⌊N/2⌋ a případně odečteme N).
Nyní potřebujeme určit pořadí za dalších N!/2-⌊N/2⌋(N-1)!=(N-1)!/2 dní. Tento posun však ovlivňuje posledních N-1 mažoretek a protože N-1 je sudé číslo, můžeme použít postup pro sudé N. Musíme však být opatrní, pokud je hodnota a2 velká – během (N-1)!/2 dní nastane (jedna) změna i na první pozici. Například když N=5 a (a1,...,a5)=(1,4,2,5,3), pak pořadí za ⌊N/2⌋(N-1)! dní je (3,4,1,5,2) a za dalších (N-1)!/2 dní je pak (4,1,2,5,3). Tomuto problému se však můžeme vyhnout tak, že pokud a2 je velké, pak k a1 na začátku přičteme ⌈N/2⌉ a k získanému pořadí budeme hledat to o (N-1)!/2 dní dříve.
Implementace výše uvedeného řešení s lineární časovou a paměťovou složitostí je přímočará a kód programu následuje.
a) Pokusíme se opět o konstrukci zdvojováním grafu. Z úplného grafu (neboli kliky) velikosti n/2 budeme vytvářet kliku velikosti n, takže od triviální kliky dospějeme k té požadované za O(logn) kroků, z nichž každý bude trvat konstantně dlouho.
Nejdříve předpokládejme, že n je mocninou dvojky. Budeme vyrábět kliky speciálního druhu, totiž takové, že n/2 vrcholů bude označeno značkou i a zbylých n/2 značkou j pro nějaké i≠j. Takovým grafům budeme říkat Gn(i,j). Všimněte si, že z Gn(i,j) umíme operací ReplaceV vytvořit Gn(i',j') pro libovolné i',j'. Nyní ukážeme, jak z Gn(1,2) vyrobit G2n(1,2):
To dává přímočarý rekurzivní algoritmus s časovou složitostí O(logn).
Zbývá tento postup upravit, aby fungoval, i když n není mocninou dvojky. Lichá n jsou problematická, protože pro ně nedává smysl ani definice Gn(i,j), a tak je ještě na chvíli odložme. Pro sudá n definice funguje, ale rekurze se bude ptát po grafu na n/2 vrcholech, což už může být liché číslo.
Použijeme proto malý trik: Vždy zaokrouhlíme n na nejbližší vyšší násobek čtyř (říkejme mu n'), sestrojíme Gn'(1,2) a pak smažeme nejvýše 3 přebytečné vrcholy. Tehdy se rekurze bude odvolávat na grafy velikosti n'/2, což je jistě sudé. Konstrukce funguje, zbývá nahlédnout, že jsme nepokazili časovou složitost.
Především: Nemůže se algoritmus zacyklit? Je skutečně pravda, že n'/2 < n? Vždy platí, že n' ≤n+3, takže stačí ukázat, že (n+3)/2 < n. Kdykoliv n>3, tato nerovnost platí; n=3 nás nezajímá, neboť je liché. Rekurzi tedy zastavíme na n=2.
Podobně ukážeme, že pro n≥6 je n'/2 ≤(n+3)/2 ≤3/4 ·n. První rekurzivní volání tedy proběhne pro graf velikosti nejvýše 3/4·n, další pro (3/4)2·n, atd., až po O(logn) krocích graf zmenšíme na méně než 6 vrcholů, pro které už kliku sestrojíme v konstantním čase. Celý algoritmus má tudíž logaritmickou časovou složitost.
Nakonec si všimneme, že spustíme-li algoritmus pro liché n, chová se přesně tak, jako by sestrojil kliku na n+1 vrcholech (což už je sudé) a pak jeden z vrcholů smazal. Tyto případy tedy nemusíme zvlášť ošetřovat.
Následující program pracuje přesně podle uvedeného algoritmu.
function klika(n: Integer): Graph; { Sestrojí graf Gn(1,2) }
var e, f, g, h: Graph;
nn: Integer;
begin
if n=2 then begin { Ošetříme triviální případ }
g := EmptyG;
AddV(g, 1);
AddV(g, 2);
AddE(g, 1, 2, undef);
klika := g;
exit;
end;
nn := n; { Zaokrouhlíme na násobek 4 }
while nn mod 4 <> 0 do inc(nn);
g := klika(nn div 2); { Gn(1,2) }
h := g;
e := g;
ReplaceV(h, 1, 3);
ReplaceV(h, 2, 4); { h = Gn(3,4) }
g := Join(g, h, none, none);
f := e; ReplaceV(f, 2, 3); { f = Gn(1,3) }
g := Join(g, f, value, any);
f := e; ReplaceV(f, 2, 4); { f = Gn(1,4) }
g := Join(g, f, value, any);
f := e; ReplaceV(f, 1, 3); { f = Gn(2,3) }
g := Join(g, f, value, any);
f := e; ReplaceV(f, 1, 4); { f = Gn(2,4) }
g := Join(g, f, value, any);
ReplaceV(g, 3, 1);
ReplaceV(g, 4, 2);
while nn > n do begin { Smažeme přebytečné vrcholy }
DelV(g, nn);
dec(nn);
end;
klika := g;
end;
b) Pro libovolné k umíme ověřit, zda zadaný graf obsahuje kliku na k vrcholech: předchozím algoritmem takovou kliku sestrojíme a použijeme operaci Find. Stačilo by tedy postupně zkoušet k=1,...,n, ale rychleji to půjde binárním vyhledáváním.
Předpokládejme, že se hledaná klikovost nachází v nějakém intervalu < a,b >. (Na začátku zvolíme a=1, b=n.) Ověříme, zda se v grafu nachází klika velikosti „uprostřed intervalu”, tedy o k=⌈(a+b)/2 ⌉ vrcholech. Pokud ne, víme, že hledaná klikovost leží v intervalu < a,k-1 >. Pokud ano, leží v < k,b >. Tím jsme hledání omezili na zhruba poloviční interval, takže po zhruba logaritmickém počtu kroků dospějeme k intervalu jednotkové velikosti a klikovost nalezneme.
Během jednoho kroku přitom strávíme čas O(logn) konstrukcí kliky, takže celková časová složitost algoritmu činí O(log2 n).
Než předvedeme program, měli bychom ještě uvést na pravou míru ono „zhruba poloviční” v odhadu složitosti a spočítat kroky exaktněji. Označme l velikost aktuálního intervalu, tedy l= b-a+1. Každý z podintervalů potom bude mít nejvýše l' = ⌈ l / 2 ⌉ prvků, což můžeme shora odhadnout výrazem (l+3)/2 a použít tytéž nerovnosti jako v podúloze a). Jen musíme rozmyslet případy s l≤3: Pro l=1 se ihned zastavíme. Když je l=2, oba podintervaly mají velikost 1 a také se zastavíme. Při l=3 nás zachrání, že střed intervalu zaokrouhlujeme nahoru, takže oba podintervaly budou mít velikost nejvýše 2.
function klikovost(var g: Graph): Integer;
var a, b, k: Integer;
h, w : Graph;
begin
a := 1; { Počáteční interval }
b := CountV(g);
while a < b do begin { Binárně hledáme }
k := (a+b+1) div 2; { Střed intervalu }
h := klika(k); { Existuje taková klika? }
w := Find(g, h, IM_any, IM_any);
if CountV(w)=0 then { Ne }
b := k-1
else { Ano }
a := k;
end;
klikovost := a;
end;
Toto řešení ovšem není optimální. Ukážeme, že testovanou kliku není potřeba vytvářet pokaždé od základu, takže algoritmus můžeme zrychlit na O(logn).
Nejprve si všimneme, že jednoduchou úpravou funkce klika můžeme v čase O(logn) sestrojit kliky všech velikostí 1, 2, 4, 8, ..., 2k, kde k je nejmenší mocnina dvojky větší než n.
var kliky: array [0..MaxLog] of Graph;
pocet_klik: Integer;
procedure vyrob_kliky(limit: Integer);
var e, f, g, h: Graph;
begin
kliky[0] := EmptyG;
AddV(kliky[0], 1);
kliky[1] := EmptyG;
AddV(kliky[1], 1);
AddV(kliky[1], 2);
AddE(kliky[1], 1, 2, undef);
pocet_klik := 1;
repeat
{ Indukční krok stejný jako v předchozím řešení }
g := kliky[pocet_klik];
h := g;
e := g;
ReplaceV(h, 1, 3);
ReplaceV(h, 2, 4);
g := Join(g, h, none, none);
f := e; ReplaceV(f, 2, 3);
g := Join(g, f, value, any);
f := e; ReplaceV(f, 2, 4);
g := Join(g, f, value, any);
f := e; ReplaceV(f, 1, 3);
g := Join(g, f, value, any);
f := e; ReplaceV(f, 1, 4);
g := Join(g, f, value, any);
ReplaceV(g, 3, 1);
ReplaceV(g, 4, 2);
inc(pocet_klik);
kliky[pocet_klik] := g;
until CountV(g) > limit;
end;
Druhá důležitá ingredience bude „odečtení” dvou klik: pokud máme kliky Kp a Kq velikostí p a q (p≥q), můžeme z nich v konstantním čase vyrobit kliku na p-q vrcholech takto: Všechny vrcholy kliky Kp opatříme značkou 1, všechny vrcholy Kq značkou 2. Nyní provedeme Join(Kq,Kp,any,any) – tím vznikne klika velikosti p, ve které bude mít q vrcholů značku 2 a zbylých p-q vrcholů značku 1. Operací Common pak najdeme největší společný podgraf tohoto grafu s klikou Kp, což je hledaná klika Kp-q.
function odecti_kliky(kp, kq: Graph): Graph; var g: Graph; begin SetAllV(kp, 1); SetAllV(kq, 2); g := Join(kq, kp, any, any); odecti_kliky := Common(g, kp, value, any); end;
Nyní upravíme hledání půlením intervalu tak, aby v každém kroku pracovalo s intervalem velikosti nějaké mocniny dvojky. Začneme intervalem < 0, 2k ), v něm se řešení určitě nachází. V každém dalším kroku pak řešení leží v nějakém intervalu < a, a+2i ). Vždy zjistíme, zda se v grafu nalézá klika velikosti t=a+2i-1. Pokud ano, přesuneme se do intervalu < t, a+2i ) = < t, t+2i-1 ). V opačném případě omezíme hledání na interval < a, t ) = < a, a+2i-1 ).
Budeme-li si průběžně udržovat kliku velikosti a+2i, můžeme z ní vždy odečtením kliky na 2i-1 vrcholech sestrojit kliku velikosti t, takže jeden krok půlení provedeme v konstantním čase. Celkem tedy strávíme čas O(logn) předvýpočtem klik a O(logn) půlícími kroky.
function klikovost(g: Graph): Integer;
var a, k: Integer;
bk, t, w: Graph;
begin
vyrob_kliky(CountV(g)); { Připrav kliky }
{
V každém průchodu cyklem bude platit:
- řesení je v intervalu <a,b), kde b=a+2^k
- bk je klika velikosti b
}
a := 0;
k := pocet_klik;
bk := kliky[k];
while k > 0 do begin
dec(k);
t := odecti_kliky(bk, kliky[k]); { t je klika velikosti a+2^(k-1) }
w := Find(g, t, any, any); { nachází se v grafu g? }
if CountV(w) <> 0 then
a := CountV(t) { ano -> interval <a+2^(k-1),b) }
else
bk := t; { ne -> interval <a,a+2^(k-1)) }
end;
klikovost := a;
end;
Na závěr ještě dodejme, že paměťovou náročnost O(logn) bychom ještě mohli snížit na O(1) tím, že bychom místo mocnin dvojky používali Fibonacciho čísla (F0=1, F1=1, Fn+2=Fn+1+Fn) a pracovali s intervaly tvaru < a, a+Fi >. Jelikož čísla Fn rostou řádově exponenciálně rychle (indukcí snadno dokážeme, že Fn ≥2n/2 pro n≥6), bude kroků vyhledávání nadále O(logn). A jelikož Fn+2 - Fn+1 = Fn, můžeme se po posloupnosti klik velikostí Fibonacciho čísel pohybovat tam i zpět v konstantním čase, aniž bychom si jich museli všech Ω(logn) pamatovat.