15

Hunt, kits ja kapsad

Selles vanas nuputamisülesandes peab farmer viima üle jõe hundi, kitse ja kapsad nii, et kõik säiliks tervetena. Farmeril on kasutada paat, kuhu peale tema mahuvad mitte rohkem kui kaks üleviidavat, kuid kui samale kaldale jäävad hunt ja kits või kits ja kapsad, tuleb kohe pahandus.
Kui andmed on kodeeritud sobiva andmestruktuuri abil, on ülesannet Prologi abil lihtne lahendada.
Kogu ülevedamist võib vaadelda kui vahelduvate seisude jada (selliselt kodeerituna on ylesarne sarnane näiteks kaardil tee otsimise ylesandega). Seis on neljaelemendiline nimistu, mille esimene element näitab, kummal kaldal (ida või läänekaldal) on farmer, teine - kummal kaldal on hunt, kolmas - kummal on kits ja neljas - kapsad, seega ülevedu algab seisust seis(ida,ida,ida,ida) ja lõpeb seisus seis(laane,laane,laane,laane).
Ülesande lahendab predikaat mine:

alusta :-
mine(seis(ida,ida,ida,ida), seis(laane,laane,laane,laane)).

mine(Seis, Eesmark) :-

seisujada(Seis, Eesmark, [Seis], Nimistu),
nl,
write('Lahendus on:'),
nl,
naita_lahendus(Nimistu),
uuesti.
mine(_,_).

Lõpprekursiivse predikaadi seisujada esimene ja teine atribuut näitavad üleviimise alg- ja lõppseisu; kolmandaks attribuudiks on seni esinenud seisude jada (selle abil kontrollitakse, et seisud ei hakkaks korduma) ja neljas on vajalik vaid selle seisude jada edasiandmiseks eesmärgi saavutamisel: kui esimene ja teine argument on samad, s.t. eesmärk on saavutatud, saab neljas argument võrdseks kolmandaga (enne seda on ta muutuja).
predikaat member(Liige, List) kontrollib, kas Liige esineb nimistus List ; kuna see predikaat on defineeritud moodulis Util.pro (se ei ole süsteemipredikaat!), tuleb enne selle kasutamist kindlasti laadida kas Util.pro või Util.plm (käsuga consult('Util.pro') või consult('Util.plm') ).

seisujada(Eesmark, Eesmark, Nimistu, Nimistu) :-
!.
seisujada(Seis, Eesmark, Nimistu, L1) :-
ylesoit(Seis, Seis1),
not hadaohtlik(Seis1),
not member(Seis1, Nimistu),
seisujada(Seis1, Eesmark, [Seis1|Nimistu], L1).

Ülesõidu ajal viib farmer ühe (hundi, kitse või kapsad) teisele kaldale; ülejäänud kaks objekti jäävad sinna kus nad olid:

ylesoit(seis(Rand1, Rand1, Kits, Kapsad), seis(Rand2, Rand2, Kits, Kapsad)) :-
vastaspoolne(Rand1, Rand2).
ylesoit(seis(Rand1, Hunt, Rand1, Kapsad), seis(Rand2, Hunt, Rand2, Kapsad)) :-
vastaspoolne(Rand1, Rand2).
ylesoit(seis(Rand1, Hunt, Kits, Rand1), seis(Rand2, Hunt, Kits, Rand2)) :-
vastaspoolne(Rand1, Rand2).
ylesoit(seis(Rand1, Hunt, Kits, Kapsad), seis(Rand2, Hunt, Kits, Kapsad)) :-
vastaspoolne(Rand1, Rand2).

vastaspoolne(ida, laane).
vastaspoolne(laane, ida).

Hädaohtlikud on seisud, kus samal rannal on hunt ja kits või kits ja kapsad, ja farmer on samal ajal jõe vastasrannal:

hadaohtlik(seis(Farmer, Rand1, Rand1,_)) :-
vastaspoolne(Farmer, Rand1).
hadaohtlik(seis(Farmer, _, Rand1, Rand1)) :-
vastaspoolne(Farmer, Rand1).

Predikaat naita_lahendus esitab predikaadi naita_ylesoit abil iga kahe järjestikuse seisu vahel esinenud ülesõidud:

naita_lahendus([T1,T2|T]) :-
!,
naita_ylesoit(T2,T1),
naita_lahendus([T2|T]).
naita_lahendus(_).
naita_ylesoit(seis(Rand1, Hunt, Kits, Kapsad), seis(Rand2, Hunt, Kits, Kapsad)) :-
!,
write('Farmer siirdub jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.
naita_ylesoit(seis(Rand1, Rand1, Kits, Kapsad), seis(Rand2, Rand2, Kits, Kapsad)) :-
!,
write('Farmer saadab hundi jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.
naita_ylesoit(seis(Rand1, Hunt, Rand1, Kapsad), seis(Rand2, Hunt, Rand2, Kapsad)) :-
!,
write('Farmer viib kitse jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.
naita_ylesoit(seis(Rand1, Hunt, Kits, Rand1),seis(Rand2, Hunt, Kits, Rand2)) :-
!,
write('Farmer viib kapsad jõe '),
write(Rand1),
write('rannalt '),
write(Rand2),
write('rannale.'),
nl.

Ülesanne

Hundi, kitse ja kapsaste üle jõe viimise ülesandega on sarnane ülesanne misjonäride ja kannibalide viimisest üle jõe:
Kolm misjonäri ja kolm kannibali peavad kõik pääsema üle jõe. Nende kasutada on paat, kuhu ei mahu rohkem kui kaks isikut; paadimeest ei ole, seega keegi neist endist peab alati paadi teisele kaldale toimetama, kuid kunagi ei või kaldale maha jääda rohkem kannibale kui seal on misjonäre.
Koosta programm probleemi lahendamiseks.


Küsimused, probleemid:
jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde