Všechna řešení, stromy, grafy
Všechna řešení: příklady
1. Jaká jsou příjmení všech žen?
2. Kteří lidé mají více než 30 roků? Nalezněte jejich jméno a příjmení.
3. Nalezněte abecedně seřazený seznam všech lidí.
4. Nalezněte příjmení učitelů ze zs_stara.
5. Jsou v databázi dva bratři (mají stejné příjmení a různá jména)?
6. Které firmy v databázi mají více než jednoho zaměstnance?
1. findall(Přijmeni, z(_,Přijmeni,z,_,_,_),L).
2 . f i ndal 1 Omeno-Pri jmeni , (zOmeno, Při jmeni ,_, Vek,_,_) , Vek>30) , L) .
3. setof (P-J , [S,V,Pr,F]AzO ,P,S,V,Pr, F) , L).
4. fi ndal1(Přijmeni,(z(_,PřijmeniP,zs_stara),(P=ucitel;P=ucitelka)),L).
5. findan(b(]l-P,]2-P),( zQl.P,_,_,_,_),z(]2,P,_,_,_,_), J1@<J2, ]1\=]2),L).
6. bagofCP,[J , S, V, Pr]AzO , P, S, V, Pr, F) , L) , length(l_, Počet) , Pocet>l.
Hana Rudová, Logické programování I, 17. května 2007 3 Všechna řešení, stromy, grafy
Všechna řešení
% zOmeno, Při jmeni, Sex, Vek, Prače, Fi rma)
z(petr,novak.m,30, skladni k,škoda).   z(pavel,novy,m,40,mechani k,škoda). z(rostislav,lucensky,m,50,techni k,škoda).   z(alena,veselá,z,25,sekretářka,škoda). zCjana, dankova, z, 35 , asistentka, škoda) .   zOenka.meri nska, z, 35 , ucetni , škoda) . z(roman, maly,m,35.manažer,cs).   z(alena,novotna,z,40,učitelka,zs_stara). z(david,novy,z,30,učitel,zs_stara).   zCpetra,špičková,z,45,ředitelka,zs_stara).
■ Najděte jméno a příjmení všech lidí.
?- findall Omeno-Pri jmeni, z(]meno, Pri jmeni ,_,_,_,_), L) .
?- bagofC Jmeno-Prijmeni, [S,V,Pr,F] a z(]meno,Prijmeni,S,V,Pr,F) ,    L ).
?- bagofC Jmeno-Prijmeni, [V,Pr,F] a z(]meno,Prijmeni,S,V,Pr,F) ,    L ).
■ Najděte jméno a příjmení všech zaměstnanců firmy škoda a cs
?- findallC c(J,P,Firma), ( zQ , P, Fi rma) , ( Firma=skoda ; Fi rma=cs ) ),
?- bagofC >P, [P,S,V,Pr]a(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) , L ). ?- setofC P-J,  [P,S,V,Pr]a(zO,P,S,V,Pr,F),( F=skoda ; F=cs ) ) ,    L ).
Hana Rudová, Logické programování I, 17. května 2007 2 Všechna řešení, stromy, grafy
Stromy
Uzly stromu Tree jsou reprezentovány termy
■ tree(Left,Value,Right): Left a Right jsou opět stromy, Value je ohodnocení uzlu
■ leaf(Value): Value je ohodnoceni uzlu
■ Příklad: 6
/ \
/ \
/ \
2 8 / \ /
14 7 / \
3 5
tree(tree(leaf(1), 2, tree(leaf(3),4,leaf(5)) ), 6, tree(leaf(7),8, []) )
Hana Rudová, Logické programování I, 17. května 2007 4 Všechna řešení, stromy, grafy
Stromy: hledáni prvku i n (X, Tree)
Stromy: přidávání add(Tree,X,TreeWithX)
Prvek X se nachází ve stromě T, jestliže
■ Xje listem stromu T, jinak leaf(X)
■ Xje kořen stromu T, jinak tree(i_eft,x,Right)
■ Xje menší než kořen stromu T, pak se nachází v levém podstromu T, jinak
■ X se nachází v pravém podstromu T
in(X, leaf(X)) :- !.
in(X, tree(_,X,_)) :- !.
in(X, tree(Left, Root, Right) ) :-
X<Root, !,
in(X,l_eft) . in(X, tree(Left, Root, Right) ) :-
in(X.Right) .
Hana Rudová, Logické programování I, 17. května 2007 5 Všechna řešení, stromy, grafy
Prvek X přidej do stromu T jednou z
■ T = [], pak je nový strom leaf(X)
■ T=leaf(V) a X>V, pak má nový strom kořen V a leaf(X) vpravo (vlevo je []) T=leaf(V) a X<V, pak má nový strom kořen V a leaf(X) vlevo (vpravo je [])
■ T=tree(L,_,_) a X>V, pak v novém stromě L ponechej a X přidej doprava T=tree(_,_,R) a X<V, pak v novém stromě R ponechej a X přidej doleva
add([],X,leaf(X)) :- !. addOeaf(V), X, TI) :-
C X>V,  !, Tl=tree([],V,leaf(X))
; X<V, Tl=tree(]eaf(X),V,[])
).
add(tree(L,V,R), X, tree(Ll,V,Rl)) :-C X>V,  !, L1=L, add(R,X,Rl) ; X<V, R1=R, add(L,X,Ll) ).
Hana Rudová, Logické programování I, 17. května 2007 6 Všechna řešení, stromy, grafy
Procházení stromů
?- traverse(tree(treeOeaf(l) , 2 , treeQeaf (3) ,4,leaf(5))) , 6, treeQeaf (7) ,8,leaf(9)
[6,2,1,4,3,5,8,7,9].
traverse(T,Pre):- t_pre(T,Pre,[]).
t_pre(leaf(V),[V|S],S). t_pre(tree(L,V,R),[V|S],S2):-
t_pre(L,S,Sl),
t_pre(R,Sl,S2). Použit princip rozdílových seznamů
6
/ \ / \ / \
2 8 / \         / \
14     7 9 / \
3 5
(preorder)
% v=2, s=[1,4,3,5|s2]
% s=[1|s1]
% s1=[4,3,5|s2]
Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí inorder (nejprve levý
podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9] traverseCT,In):- t_in(T,In, []) .
t_in(leaf(V) , [V|S] ,S).
t_in(tree(L,V,R),S,S2):-t_in(L,S,[VISI]), t_in(R,Sl,S2).
Reprezentace grafu
Reprezentace grafu: pole následníků uzlů
Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term (Orientovaný) neohodnocený graf
graf([2,3],[l,3],[l,2]).
grafC[2,4,6],[1,3],[2],[1,5,6],[4],[1,4]).
?- functorCCraf,graf,PocetUzlu). ?- arg(Uzel,Graf.Sousedi).
(Orientovaný) ohodnocený graf
graf([2-l,3-2],[1-1,3-2],[1-2,2-2]).
grafC[2-1,4-3,6-1],[1-1,3-2],[2-2],[1-3,5-1,6-1],[4-1],[1-1,4-1]).
Hana Rudová, Logické programování I, 17. května 2007
Všechna řešení, stromy, grafy
Hana Rudová, Logické programování I, 17. května 2007
Všechna řešení, stromy, grafy
Procházení grafu do hloubky
DFS: algoritmus
■ Rodiče uzlů:
■ při reprezentaci rodičů lze využít term s aritou odpovídající počtu uzlů
■ iniciálně jsou argumentu termu volné proměnné
■ na závěr je v N-tém argumentu uložen rodič (iniciální uzel označíme empty)
■ Procházení grafu z uzlu U
■ Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné)
■ Uzel U má prázdného rodiče a má sousedy S
■ Procházíme (rekurzivně) všechny sousedy v S
■ Procházení sousedů S uzlu U
■ Uzel Vje první soused
■ Nastavíme rodiče uzlu V na uzel U
■ Pokud jsme V ještě neprošli (nemá rodiče), tak rekurzivně procházej všechny jeho sousedy
■ Procházej zbývající sousedy uzlu U
Hana Rudová, Logické programování I, 17. května 2007 9 Všechna řešení, stromy, grafy
dfs(U,G,P) :-
f unctorCC,graf,Počet), functor(P,rodiče,Počet), arg(U,C,Sousedi), arg(U,P,empty),
prochazej_sousedy(Sousedi,U,C,P).
prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],U,C,P) :-
arg(V,P,Rodič),
( nonvar(Rodic), !
Rodič = U,
arg(V,G,SousediV),
prochazej_sousedy(SousediV,V,C,P)
),
prochazej_sousedy(T,U,C,P).
Hana Rudová, Logické programování I, 17. května 2007 10
Všechna řešení, stromy, grafy