Prolog - grafy a prohledávání stavového prostoru

Je čas začít v Prologu také dělat něco složitějšího. Uvidíme, že Prolog se dá použít i k prohledávání grafů, hledání cest a podobně.

Jak ale v Prologu graf reprezentovat? Existují asi dva způsoby, které se dají relativně snadno použít. Jeden z nich je seznam následníků, druhý je seznam hran.

Pokud chceme graf reprezentovat jako seznam následníků můžeme si např. vytvořit predikát grafSN([Vrchol1->[Naslednici1],Vrchol2->[Naslednici2], ...]). Když se nám to hodí, můžeme si přidat i samostatný seznam vrcholů např. jako grafSN([Vrcholy], [V1->[N1], V2->[N2], ...]). (Samozřejmě, na operátoru, který použijete pro oddělení vrcholu od seznamu vůbec nezáleží.).

Druhou možností, jak reprezentovat graf je použít seznam hran. V takovém případě si vytvoříme predikát grafSH([Vrcholy], [hrana(V1,V2), hrana(V3,V4), ...]), kde V1, V2, V3, V4 jsou samozřejmě vrcholy ze seznamu [Vrcholy].

Vytvořme si tedy popis malého grafu o 5 vrcholech: grafSN([1,2,3,4,5],[1->[2,3,4],2->[5],3->[1,2,4],4->[1],5->[2,3])

První věc, která se nám hodí jsou procedury na převod mezi oběma reprezentacemi.

% gSNnaSH(+GrafSN,-GrafSH) :- GrafSH je GrafSN prevedeny ze seznamu nasledniku na seznam hran.
gSNnaSH(grafSN(V, N), grafSH(V, Hrany)):-bagof(hrana(V1,V2), E^(member(V1->E,N),member(V2,E)), Hrany).

% sSHnaSN(+GrafSH,-GrafSN) :- GrafSN je GrafSH prevedeny ze seznamu hran na seznam nasledniku
gSHnaSN(grafSH(V, E), grafSN(V, Naslednici)):-setof(V1->N, (member(V1,V),setof(X, member(hrana(V1,X),E),N)),Naslednici).

Používejme teď chvíli grafy reprezentované seznamy hran. Napřed můžeme napsat predikát, který vyjadřuje, že mezi dvěma vrcholy existuje cesta.

% cesta(+GrafSH, +Odkud, +-Kam) :- v grafu GrafSH existuje cesta z Odkud do Kam
cesta(grafSH(_,E), O, K) :- member(hrana(O,K), E).
cesta(grafSH(V,E), O, K) :- member(hrana(O,Z), E), cesta(grafSH(V,E), Z, K). 

Procedura cesta/3 má několik problémů. Jeden z nich je, že nevrací nalezenou cestu, druhý je, že bude vracet úplně všechny cesty, které v grafu existuji včetně těch, které obsahují cykly. Navíc se může i zacyklit (bude procházet ten samý cyklus v grafu stále kolem dokola). Zkusme tedy napsat proceduru, která bude vracet všechny cesty bez cyklů.

cestaBC(grafSH(V,E), O, K, C) :- cestaBC(grafSH(V,E),O,K,[],C).
cestaBC(_, O, O, _, [O]).
cestaBC(grafSH(V,E), O, K, P, [O|C]) :- member(hrana(O,Z), E), \+member(Z, P), cestaBC(grafSH(V,E), Z, K, [O|P], C). 

Hledání cesty v grafu je podobné prohledávání stavového prostoru. Jen při prohledávání stavového prostoru nemáme tento prostor zadaný explicitně seznamy následníků jednotlivých vrcholů, ale jen akcemi, které lze v každém stavu provést. Představme si například známý příklad se dvěma nádobami a přeléváním vody mezi nimi. Máme dvě nádoby, jednu o objemu V1 litrů, druhou o objemu V2 litrů. Navíc máme k dispozici neomezený zdroj vody a vodu můžeme z nádob libovolné vylévat. Cílem je najít takovou posloupnost přelévání, která povede k tomu, že v druhé nádobě je právě daný objem vody.

Stav můžeme v tomto případě reprezentovat jako dvojici s(X, Y), kde X je množství vody v první nádobě a Y je množství vody v druhé nádobě. Máme potom několik akcí, které můžeme v každém stavu provést.

% akce(+Stav, +MaxV1, +MaxV2, -NovyStav):-NovyStav je Stav, ktery vznikne
% aplikaci jedne akce na Stav, kdyz nadoby maji maximalni objemy MaxV1 a MaxV2
akce(s(_, Y), _, _, s(0, Y)). % vyliti prvni nadoby
akce(s(X, _), _, _, s(X, 0)). % vyliti druhe nadoby
akce(s(_, Y), V1, _, s(V1, Y)). % naplneni prvni nadoby
akce(s(X, _), _, V2, s(X, V2)). % naplneni druhe nadoby
akce(s(X, Y), V1, _, s(X1, Y1)):-X + Y > V1, X1 = V1, Y1 is Y - (V1 - X). % preliti druhe nadoby do prvni, nevejde se vse
akce(s(X, Y), V1, _, s(X1, Y1)):-X + Y =< V1, X1 is X + Y, Y1 = 0. % preliti druhe do prvni, vse se vejde 
akce(s(X, Y), _, V2, s(X1, Y1)):-X + Y > V2, Y1 = V2, X1 is X - (V2 - Y). % preliti prvni do druhe, nevejde se vse
akce(s(X, Y), _, V2, s(X1, Y1)):-X + Y =< V2, Y1 is X + Y, X1 = 0. % preliti prvni do druhe, vejde se vse

Teď už tedy umíme ke každému stavu najít všechny sousední stavy. Můžeme se tedy podívat, jak bude stav vypadat po jednom kroku. Akce nám vlastně ukazuje jeden krok, který můžeme provést. Jak bude vypadat stav po provedení N kroků?

% nkroku(+Stav, +MaxV1, +MaxV2, +N, -NovyStav):-NovyStav je stav, ktery vznikne
% aplikovani N kroku na Stav, MaxV1 a MaxV2 jsou maximalni objemy nadob
nkroku(S, _, _, 0, S):-!. % Musime zariznout, jinak budeme zkouset zaporne pocty kroku
nkroku(S, MaxV1, MaxV2, N, S2):-akce(S, MaxV1, MaxV2, S1), 
                                N1 is N - 1, 
                                nkroku(S1, MaxV1, MaxV2, N1, S2).

Predikát nkroku je užitečný a funguje, ale občas zkouší i cesty, na kterých se několikrát opakuje ten samý stav. Když nás bude zajímat nejkratší řešení, tak takové cesty zcela jistě nechceme a můžeme se jich zbavit. Navíc by se nám líbilo získat posloupnost stavů, které vedou k cílovému. K tomu použijeme akumulátor (a navíc jednu výstupní proměnnou, která bude obsahovat posloupnost stavů).

% nkroku(+Stav, +MaxV1, +MaxV2, +N, -Posloupnost, -NovyStav):-NovyStav je stav,
% ktery vznikne aplikovani N kroku na Stav, MaxV1 a MaxV2 jsou maximalni objemy
% nadob, Posloupnost je posloupnost stavu ze Stav do NovyStav, ktera vede k 
% vytvoreni NovyStav, stavy v Posloupnosti se neopakuji
nkroku(S, MaxV1, MaxV2, N, P, S1):-nkroku(S, MaxV1, MaxV2, N, [], P, S1). 
nkroku(S, _, _, 0, A, P, S):-reverse(A, P).
nkroku(S, MaxV1, MaxV2, N, A, P, S2):-N>0, akce(S, MaxV1, MaxV2, S1), 
                                    \+member(S1, A),
                                    N1 is N - 1, 
                                    nkroku(S1, MaxV1, MaxV2, N1, [S1|A], P, S2).

Pomocí predikátu nkroku/6 už můžeme napsat prohledávání, které nám zajistí, že najdeme nejkratší řešení daného problému. Uděláme tzv. iterované prohlubování. Na začátku nastavíme maximální počet kroků na 1, zkusíme tak problém vyřešit, když se to nepovede, zvýšíme počet kroků na 2 a opakujeme. Po každém neúspěchu zvýšíme počet kroků o 1.

% vyresID(+PocatecniStav, +MaxV1, +MaxV2, +KoncovyStav, -P):-P je posloupnost
% kroku, ktera prevadi PocatecniStav na KoncovyStav, MaxVi je objem nadoby i,
% posloupnost se hleda pomoci postupnehoprohlubovani (iterative deepening)
vyresID(PS, MaxV1, MaxV2, KS, P):-vyresID(PS, MaxV1, MaxV2, 1, KS, P).
vyresID(PS, MaxV1, MaxV2, N, KS, P):-nkroku(PS, MaxV1, MaxV2, N, P, KS),!.
vyresID(PS, MaxV1, MaxV2, N, KS, P):-N1 is N + 1, N1 < 50, % max pocet kroku je 50
                                    vyresID(PS, MaxV1, MaxV2, N1, KS, P).

Výhodou iterovaného prohlubování je, že má menší prostorovou složitost než prohledávání do šířky (nemusí si pamatovat všechny navštívené stavy, stačí mu aktuální větev) a navíc zajišťuje nalezení nejkratšího řešení (což DFS se stejnou prostorovou složitostí nezaručuje).

Napsat prosté DFS je v Prologu samozřejmě taky možné a dokonce je to o něco jednodušší než postupné prohlubování.

% vyresDFS(+PocatecniStav, +MaxV1, +MaxV2, +KoncovyStav, -P):-stejne jako 
% predchozi, jen pouziva DFS misto ID
vyresDFS(PS, MaxV1, MaxV2, KS, P):-vyresDFS(PS, MaxV1, MaxV2, KS, [PS], P).
vyresDFS(_, _, _, KS, [KS|A], P):-reverse([KS|A], P), !.
vyresDFS(PS, MaxV1, MaxV2, KS, A, P):-akce(PS, MaxV1, MaxV2, NS), 
                                      \+member(NS, A), % jinak se zacyklime
                                      vyresDFS(NS, MaxV1, MaxV2, KS, [NS|A], P).