Vyhledávací stromy
Binární stromy můžeme používat jako stromy vyhledávací. Každý vrchol bude obsahovat porovnatelný klíč a budeme udržovat invariant, že levý podstrom obsahuje menší a pravý podstrom větší vrcholy.
Můžeme taktéž uvažovat variantu vyhledávacích stromů, které kromě klíče mají
též uloženou hodnotu. Takový vrchol pak třeba reprezentujeme termem t(Levy,
Klic, Hodnota, Pravy). Pro teď však budeme uvažovat původní reprezentaci bez
hodnoty.
Poznat, že binární strom je vyhledávací, zvládneme jednoduchým prohledáním do
hloubky. Externí vrcholy nil jsou vždy v pořádku.
% cmp_v(?U, ?V) :- klíč U je nejvýše klíč V nebo jeden z vrhcolů je externí. cmp_v(nil, _). cmp_v(_, nil). cmp_v(t(_,K1,_), t(_,K2,_)) :- K1 @< K2. % bst(+T) :- T je binární vyhledávací strom. bst(T) :- bst(nil, T, nil). % na začátku je minimum a maximum externí. bst(_, nil, _). bst(A, T, B) :- T = t(L, _, R), % Rozepsaní vrcholu cmp_v(A, T), cmp_v(T, B), % T je mezi vrcholy A a B bst(A, L, T), bst(T, R, B). % Zmenšíme interval podle T
V případě, že bychom povolili mít ve stromu duplicitní klíče, můžeme prohodit
@< za @=<.
Cvičení: Upravte kontrolu BST, aby kontrolovala i stromy, které si ke klíči udržují hodnotu.
Cvičení: Upravte kontrolu BST tak, aby porovnávání klíčů proběhlo
metapredikátem :Cmp(X, Y) splnitelným, když X < Y pro naši definici
porovnávání.
Když máme k dispozici binární vyhledávací strom, můžeme v něm snadno vyhledávat. Budeme vyhledávat podle klíče a pokud nalezneme vrchol s daným klíčem, vrátíme jej. Jinak vrátíme externí vrchol.
% find(+K, +T, ?V) :- T je BVS, K je hledaný klíč a V je vrchol stromu T, jehož klíč je K. find(_, nil, nil). find(K, T, T) :- T = t(_, K, _). % Nalezení vrcholu find(K, t(L, X, _), V) :- K @< X, find(K, L, V). find(K, t(_, X, R), V) :- K @> X, find(K, R, V). ?- find(3, t(t(nil, 1, nil), 2, t(nil, 3, nil)), V). V = t(nil, 3, nil) ; false. ?- find(4, t(t(nil, 1, nil), 2, t(nil, 3, nil)), nil). true ; false. ?- find(2, t(t(nil, 1, nil), 2, t(nil, 3, nil)), t(L, 2, _)). L = t(nil, 1, nil) ; false.
Cvičení: Naprogramujte predikát succ(K, T, V) splnitelný, jestliže V je
vrchol stromu T obsahující následníka klíče K. Jestliže K se ve stromě
nenachází, V bude mít klíč nejmenší ze všech klíčů ostře větších K v T.
Persistence datových struktur
Datové struktury v Prologu jsou neměnné. Jediný způsob, jak je zdánlivě měnit, je tvoření nových struktur, které budou využívat části původní struktury. Taková struktura je pak persistentní – máme možnost si pamatovat celou její historii úprav. Navíc, tato persistence je úplná, můžeme kdykoliv z libovolného historického stavu struktury začít tvořít novou.
Všimněte si, že přesně takto jsme k seznamům přistupovali. Přidávání něco na hlavu seznamu bylo ve skutečnosti vytvoření nového seznamu, který jako zbytek využíval již dříve vytvořený seznam. Naopak, přidání na konec seznamu znamená kompletní vytvoření nového seznamu, který má ale původní prvky.
Unifikace proměnných tuto persistenci zdánlivě porušuje. Z tohoto důvodu můžeme rozdílové seznamy spojovat v konstantním čase. Je si však důležité uvědomit, že jakmile jednou za proměnnou dosadíme, už tak vždy zůstane. Proměnné si tak z pohledu historie datové struktury můžeme představit jako "něco z budoucnosti".
Vkládání vrcholu do vyhledávacího stromu tudíž bude dělat to, že při vložení vrcholu postupně aktualizuje celou cestu až do kořene. Narozdíl od běžných jazyků si tím zvětšíme paměťovou složitost právě o délku této cesty, pokud budeme mít někde proměnnou, ve které je původní strom.
% insert(+K, +T, -NT) :- NT je BVS T, který navíc obsahuje klíč K, % pokud jej předtím neobsahoval. insert(K, nil, t(nil, K, nil)). insert(K, T, T) :- T = t(_, K, _). insert(K, t(L, X, R), t(NL, X, R)) :- K @< X, insert(K, L, NL). insert(K, t(L, X, R), t(L, X, NR)) :- K @> X, insert(K, R, NR).
Cvičení: Naprogramujte predikát delete(+K, +T, -NT) splnitelný, jestliže
NT je strom T neobsahující K, jestliže ho před tím obsahoval. Může se vám
hodit succ/3.
Cvičení: Upravte find, succ, insert a delete tak, aby fungovaly se
stromy udržujícími hodnotu. V případě insert se při nalezení vrcholu s daným
klíčem původní hodnota přepíše na novou.
Jelikož máme k dispozici přidávání klíčů do vyhledávacího stromu, můžeme jednoduše napsat predikát, který převede libovolný seznam na vyhledávací strom. K tomu se nám bude hodit akumulátor, kterým si budeme udržovat částečně sestavený strom.
bst_from_list(L, T) :- bst_from_list(L, nil, T). bst_from_list([], T, T). bst_from_list([K|L], T, NT) :- insert(K, T, KT), bst_from_list(L, KT, NT).
Cvičení: Ukažte, jak pomocí binárního vyhledávacího stromu třídit.
Cvičení: Zkuste vyhledávací stromy udržovat vyvažené, například užitím AVL stromů.
Grafy
Od stromů se postupně přesuneme k orientovaným grafům. Grafy můžeme reprezentovat mnoha různými způsoby. My si ukážeme tři.
První způsob je mít dva seznamy. První seznam obsahuje identifikátory vrcholů a
druhý pak obsahuje dvojice vrcholů, například U-V, reprezentující hrany.
Druhá možnost je mít jeden seznam dvojic V->N, kde V je identifikátor
vrcholu a N je seznam jeho sousedů.
Ukažme si příklady obou datových struktur pro malý graf o pěti vrcholech:
% Seznam hran jako dvojic grafE([a, b, c, d, e], [a-b, a-c, a-d, b-e, c-a, c-b, c-d, d-a, e-b, e-c]) % Seznam sousedů grafN([a->[b, c, d], b->[e], c->[a, b, d], d->[a], e->[b, c])
Třetí způsob, který se často bude hodit, je reprezentovat vrcholy a hrany nějakým predikátem. Tento způsob je často nejobecnější, jelikož se pak dá snadno použít při metaprogramování a nemusíme si pak explicitně udržovat seznam vrcholů a hran. Taktéž nám tento způsob umožní reprezentovat nekonečné grafy.
Ukažme si, jak bude takový predikát vypadat pro naše dvě předchozí reprezentace.
% vrchol(+G, ?V) :- V je vrchol grafu G. vrchol(grafE(Vs, _), V) :- member(V, Vs). vrchol(grafN(G), V) :- member(V->_, G). % hrana(+G, ?U, ?V) :- V grafu G je hrana z vrholu U do vrcholu V. % Hledání hrany v grafu reprezentovaném seznamem hran hrana(grafE(Vs, Es), U, V) :- member(U-V, Es). % Hledání hrany v grafu reprezentovaném seznamem sousedů hrana(grafN(G), U, V) :- member(U->N, G), member(V, N). % Když už máme seznam sousedů v ruce hrana(U->N, U, V) :- member(V, N).
Cvičení: Zkuste naprogramovat predikát preved(?GE, ?GN) splnitelný,
jestliže GE a GN jsou reprezentace přes seznam hran a přes seznam sousedů
toho samého grafu. Můžete použít různé implementace podle toho, který graf je
vstupní.
Pojďme teď předpokládat, že máme predikát Hrana(U, V) splnitelný, když
(U,V) je hrana (nějakého) grafu. Nezapomeňme, že díky call si můžeme
konkrétní graf předem doplnit do našeho predikátu hrana/3.
Budeme se teď zabývat velmi běžným grafovým problémem, a to dosažitelností dvou vrcholů a případným nalezením (nejkratší) cesty. Nejprve začneme jednoduše. Dva vrcholy jsou dosažitelné, jestliže mezi nimi existuje nějaký sled, tedy posloupnost vrcholů, které jsou navzájem propojené hranami. Tím dostaneme triviální řešení:
% dosazitelne(:Hrana, ?S, ?T) :- Pomocí metapredikátu Hrana je T dosažitelné z S ≠ T. dosazitelne(H, S, T) :- call(H, S, T). % S, T jsou propojeny hranou dosazitelne(H, S, T) :- call(H, S, V), dosazitelne(H, V, T). % S, T jsou dosažitelné přes V
Zkusme nyní položit nějaké dotazy na dosažitelnost.
?- dosazitelne(hrana(grafN([a->[b], b->[c]])), a, c). true ; false. ?- dosazitelne(hrana(grafN([a->[b], b->[c]])), S, T). S = a, T = b ; S = b, T = c ; S = a, T = c ; false. ?- dosazitelne(hrana(grafN([a->[b], b->[c]])), c, a). false. ?- dosazitelne(hrana(grafE(_, [a-b, b-c, c-a, d-a])), d, c). true ; true ; true ; true ; true . ?- dosazitelne(hrana(grafE(_, [a-b, b-c, c-a, d-a])), a, d). % Zacyklení...
Jak vidíme, tento predikát má hned dvě velké slabiny. Ta první je, že nám vůbec
neřekne sled, kterým můžeme z S dosáhnout do T. Ta druhá mnohem závažnější
je, že prohledáváme přes všechny sledy do hloubky. Jakmile se dostaneme do
cyklu, zacyklíme se i my. Pokud se na tom cyklu nachází T, dostaneme
nekonečně mnoho řešení. Jinak nikdy nedostaneme odpověď. To není hezké.
Místo sledů tedy budeme hledat cesty. Při prohledávání grafu si budeme pamatovat, které vrcholy jsme již navštívili. Pak povolíme přejít hranou pouze, když cílový vrchol ještě nebyl navštíven. Pokud navíc si uložíme navštívené vrcholy ve správném pořadí, dostaneme zdarma i kýženou cestu.
% cesta(:Hrana, ?S, ?T, ?P) :- Pomocí metapredikátu Hrana vede cesta P z S do T. cesta(H, S, T, P) :- cesta(H, S, T, [S], P). cesta(_, S, S, _, [S]). cesta(H, S, T, A, [S|P]) :- call(H, S, V), \+member(V, A), cesta(H, V, T, [V|A], P).
Zkusme nyní položit stejné dotazy, jako u dosažitelnosti a ještě nějaké navíc.
?- cesta(hrana(grafN([a->[b], b->[c]])), a, c, P). P = [a, b, c] ; false. ?- cesta(hrana(grafN([a->[b], b->[c]])), S, T, P). S = T, P = [T] ; S = a, T = b, P = [a, b] ; S = a, T = c, P = [a, b, c] ; S = b, T = c, P = [b, c] ; false. ?- cesta(hrana(grafE(_, [a-b, b-c, c-a, d-a])), d, c, P). P = [d, a, b, c] ; false. ?- cesta(hrana(grafE(_, [a-b, b-c, c-a, d-a])), a, d, P). false. ?- cesta(hrana(grafE(_, [a-b, b-c, c-a, d-a])), S, T, P), member(b, P). S = T, T = b, P = [b] ; S = a, T = b, P = [a, b] ; S = a, T = c, P = [a, b, c] . % Existují další řešení, zastavujeme předčasně
Přidání podmínky \+member má kvůli nepřímému řezu jeden vedlejší efekt.
Představme si, že predikát hrana(S, V) vrátí V s volnými proměnnými. Tím
riskujeme, že někdy půjde tyto volné proměnné (později) nějak zunifkovat a
nesprávně cestu zahodíme. Tudíž od této chvíle musí platit ground(V).
Zkusme si nyní vyřešit jednoduchou úložku užívající nekonečný graf, jehož hrany jsou definované predikátem. Vrcholy budou kladná přirozená čísla a hrany budou vést následovně:
- Pokud je N sudé, vede hrana z N do N/2.
- Pokud je N liché, vede hrana z N do 3N+1.
Naším cílem pak bude dosáhnout čísla 1. Této úloze se říká Collatzova.
ciselna_uloha(N, M) :- N mod 2 =:= 0, M is N/2. ciselna_uloha(N, M) :- N mod 2 =:= 1, M is 3*N+1. ?- between(2, 5, N), cesta(ciselna_uloha, N, 1, P). N = 2, P = [2, 1] ; N = 3, P = [3, 10, 5, 16, 8, 4, 2, 1] ; N = 4, P = [4, 2, 1] ; N = 5, P = [5, 16, 8, 4, 2, 1] ; false.
Cvičení: Mějme nekonečnou mřížku, tedy graf, kde vrcholy jsou (X, Y) pro celá čísla X, Y a hrany vedou mezi těmi dvojicemi, kde se právě jedno číslo liší o jedničku. Naprogramujte predikát tvořící hrany pro tuto mřížku a zkuste hledat cesty na ní.
Náš predikát na vyhledávání cesty pracuje pomocí prohledávání do hloubky. To má dvě zásadní nevýhody. Cesty, které najdeme, nebudou vždy nejkratší. To bychom často chtěli mít. Dále pak se velmi snadno může stát, že se v nekonečném grafu dostaneme do nekonečné větve a pak nikdy nenajdeme cestu, přestože existuje v jiné větvi.
Prohledávání budeme tudíž dělat tak, že omezíme hloubku, nejprve na nulovou. Pokud nic nenajdeme, omezení hloubky zmírníme o 1 a zkusíme znovu. Pak, pokud nějakou cestu najdeme, zaručíme, že bude nejkratší. Navíc můžeme dát horní limit pro celkovou hloubku, takže se i na nekonečných grafech zastavíme vždy. Tomuto principu se říká iterativní prohlubování.
Tady můžeme využít vlastnosti predikátu length(-L, -N). Ten bude postupně
generovat seznamy, jejichž délky jsou postupně delší a delší počínaje nulou.
Pro omezení hloubky pak musíme postupovat opatrně, přidání kontroly velikosti
N by selhalo, program by se zacyklil po přesáhnutí N. Místo toho můžeme
použít between.
% cesta_iter(N, :H, ?S, ?T, ?P) :- cesta P hledaná iterativním prohlubováním délky ≤ N. cesta_iter(N, H, S, T, P) :- between(1, N, K), length(P, K), cesta(H, S, T, P). ?- between(2, 10, N), cesta_iter(5, ciselna_uloha, N, 1, P). N = 2, P = [2, 1] ; N = 4, P = [4, 2, 1] ; N = 8, P = [8, 4, 2, 1] ; false.
Nyní, když máme iterativní prohlubování, můžeme zkusit prohledávat stavový prostor, který může mít exponenciálně mnoho nekonečně mnoha větví.
Uvažme problém přelévání dvou nádob. Máme dvě nádoby, každá má každá omezený objem. Navíc máme neomezený zdroj a stok vody. Chceme zjistit, jestli existuje posloupnost přelévání, kterou dostaneme určitý objem v každé láhvi. Při přelití musíme vždy vyprázdnit nebo naplnit jednu láhev.
Vrcholy stavového prostoru budou v tomto případě tvořit dvojice n(X, Y)
a hrany budou vést mezi těmi vrcholy, které lze na sebe převést právě jedním
přelitím. Hrany budeme reprezentovat predikátem preliti/4, který v prvních
dvou parametrech bude držet objemy obou nádob.
% preliti(+V1, +V2, +U, -V) :- ze stavu nadob U se dostaneme do stavu % nádob V přelitím, kde nádoby mají objem V1 a V2. preliti(V1, V2, U, V) :- preliti_(V1, V2, U, V), U \= V. % Něco udělat chceme preliti_(_, _, n(_, Y), n(0, Y)). % Vylijeme první nádobu preliti_(_, _, n(X, _), n(X, 0)). % Vylijeme druhou nádobu preliti_(V1, _, n(_, Y), n(V1, Y)). % Naplníme první nádobu preliti_(_, V2, n(X, _), n(X, V2)). % Naplníme druhou nádobu preliti_(V1, _, n(X, Y), n(X1, Y1)) :- X + Y > V1, X1 = V1, Y1 is Y - (V1 - X). % Z druhé do první, nevejde se preliti_(V1, _, n(X, Y), n(X1, Y1)) :- X + Y =< V1, X1 is X + Y, Y1 = 0. % Z druhé do první, vejde se preliti_(_, V2, n(X, Y), n(X1, Y1)) :- X + Y > V2, Y1 = V2, X1 is X - (V2 - Y). % Z první do druhé, nevejde se preliti_(_, V2, n(X, Y), n(X1, Y1)) :- X + Y =< V2, Y1 is X + Y, X1 = 0. % Z druhé do první, vejde se ?- cesta_iter(50, preliti(7, 5), n(0, 0), n(4, 0), P). P = [n(0,0), n(7,0), n(2,5), n(2,0), n(0,2), n(7,2), n(4,5), n(4,0)] ; P = [n(0,0), n(0,5), n(7,5), n(7,0), n(2,5), n(2,0), n(0,2), n(7,2), n(4,5), n(4,0)] ; P = [n(0,0), n(0,5), n(5,0), n(7,0), n(2,5), n(2,0), n(0,2), n(7,2), n(4,5), n(4,0)] ; P = [n(0,0), n(0,5), n(5,0), n(5,5), n(7,5), n(7,0), n(2,5), n(2,0), n(0,2), n(7,2), n(4,5), n(4,0)] .
Cvičení: Upravte iterativní prohlubování tak, aby fungovalo s predikátem
Hrana(U, V, E) splnitelným, jestliže U, V jsou spojeny hranou s popiskem
E. Pak vrácená cesta nebude obsahovat sousední vrcholy, ale právě tyto
popisky hran. Popisek hrany může být například konkrétní akce nebo směr
přesunu.
Cvičení: Upravte iterativní prohlubování tak, aby cílový vrchol nebyl pevně
daný vrchol T, ale aby pro cílový vrchol platil metapredikát Cilovy(V). Pak
můžeme hledat cesty do množiny cílových vrcholů, například východů v bludišti.
Cvičení: Jak se změní správnost a efektivita iterativního prohlubování,
jestliže v něm nahradíme predikát cesta predikátem sled (tedy nebudeme
kontrolovat navštívené vrcholy)?
Cvičení: Naprogramujte predikát editacni_vzdalenost(+Abeceda, +X, +Y, -E)
splnitelný, jestliže E je posloupnost příkazů taková, že z X udělá Y.
Příkazy jsou add(P, L), tedy přidání písmene z abecedy L na pozici P
(číslované od nuly), a del(P), tedy odstranění písmene na pozici P. Šlo by
vypustit dodání abecedy?