Všetky odpovede

Pomocou mechanizmu spätného chodu môžeme po jednom generovať všetky objekty, ktoré spĺňajú určitý ciel. Vždy, keď sa generuje nové riešenie, predchádzajúce sa stratí a nie je už prístupné. Niekedy je však užitočné mat všetky vygenerované objekty prístupné spolu - napr. zozbierané do zoznamu. Na tieto účely sú definované štandardné predikáty bagof, setof a findall. Findall je najvýkonnejší a aj sa najčastejšie používa.

bagof(+Term, +Goal, -Bag)

predikát zozbiera do zoznamu bez vyradenia duplicitných prvkov všetky inštancie termu Term také, že špecifikovaný ciel Goal možno splniť. Term musí obsahovať neviazané premenné, ktoré sa vyskytujú v cieli Goal. Ostatné neviazané premenné v cieli Goal možno existenčne kvantifikovať operátorom ^ (P^Goal pre jednu premennú a (P1,P2,..,Pn) ^ Goal pre viac premenných).

setof(+Term, +Goal, -Set)

to isté ako predikát bagof, ale setof vracia usporiadaný zoznam, ktorý neobsahuje duplikáty

findall(+Term, +Goal, -List)

podobá sa predikátu bagof. Rozdiel je v tom, že ľubovoľná voľná premenná sa považuje za existenčne kvantifikovanú.

Uvažujme takýto program:

trieda(a, samohlaska).
trieda(b, spoluhlaska).
trieda(c, spoluhlaska).
trieda(d, spoluhlaska).
trieda(e, samohlaska).
trieda(f, spoluhlaska).

A teraz dopyty:

?- bagof(Pismeno, trieda(Pismeno, spoluhlaska), Pismena).
Pismena = [b,c,d,f]
yes

?- bagof(Pismeno, trieda(Pismeno, Trieda), Pismena).
Trieda = samohlaska
Pismena = [a,e] ;
Trieda = spoluhlaska
Pismena = [b,c,d,f] ;
no

?- findall(Pismeno, trieda(Pismeno, Trieda), Pismena).
Pismena = [a,b,c,d,e,f]
yes

Predikát findall môžeme jednoducho naprogramovať takýmto spôsobom: všetky riešenia ciela Goal vygenerujeme použitím spätného chodu. Keď sa nejaké riešenie vygeneruje, hneď sa uloží do databázy, takže ho nemôžeme stratiť. Keď nájdeme všetky riešenia treba ich zozbierať do zoznamu a zrušiť z databázy. Celý proces si môžeme predstaviť tak, že všetky riešenia tvoria zásobník. Každé novo vygenerované riešenie sa umiestni na vrch zásobníka.

Riešenie:

findall(X, Goal, XList) :-
      call(Goal),             % nájdi riešenie
      assertz(stack(X) ),     % ulož riešenie
      fail                    % skús nájsť ďalšie riešenie
      ;
      collect(XList).         % zozbieraj riešenia
collect([X|Rest]) :-
      retract(stack(X)), !,   % vyber ďalšie riešenie
      collect(Rest).          % zozbieraj zvyšok
collect([]).                  % koniec riešení

to Homepage to Teaching to FLP to the Top

Home
Research
Projects
Publications
Books
SCM
Teaching
Links
Last updated:
Mária Bieliková bielik [zavináč] fiit-dot-stuba-dot-sk
Design © 2oo1 KoXo