8



Tee otsimine labyrindis

Tee otsimise ülesannetes tuleb kuidagi salvestada juba külastatud paigad (et neid mitte uuesti külastada). Vaheandmete salvestamiseks on Prologis kaks võimalust: tema andmebaasi (s.o. Prologi programmi) uute faktide lisamine või nimistute kasutamine; vaatleme siin labürindis tee otsimise näite põhjal esimest.
Programmi lisab uusi lauseid Eesti-Prologi süsteemi- (s.t. sisseehitatud) predikaat assert(Lause); süsteemipredikaat clause(Lause) aga kontrollib, kas lause Lause juba esineb programmis.

Labürindi struktuuri on kõige lihtsam kirjeldada lausetega
uks(Ruum, Ruum1), mis näitavad, kust ruumist kuhu ruumi läheb uks:



uks(a1, b1).

uks(b1, c1).
uks(a1, a2).
uks(a2, a3).
uks(a3, b3).
uks(b1, b2).
uks(b2, c2).
uks(c2, c3).

Ruumist Ruum pääseb ruumi Ruum1 , kui ruumide vahel on mingis suunas uks (uksest pääseb liikuma mõlemas suunas):

paaseb(Ruum, Ruum1):-

uks(Ruum, Ruum1).
paaseb(Ruum, Ruum1):-
uks(Ruum1, Ruum).

Labürindis tee leidmise algoritm on lihtne. Mingis ruumis Ruum olles otsitakse selline naaberruum (st. ruum Ruum1 kuhu ruumist Ruum pääseb) mida ei ole veel külastatud; peetakse meeles, et praeguses ruumis Ruum juba käidi (s.t. vastav lause lisatakse programmi) ja jätkatakse otsimist järgmisest ruumist Ruum1 ; ühtlasi kirjutatakse ekraanile, kuidas parajasti liigutakse:

otsi(Ruum):-

paaseb(Ruum, Ruum1)),
not(clause(kaidud(Ruum1)), true),
assert(kaidud(Ruum)),
kirjuta('Ruumist '),
write(Ruum),
write(' lahen ruumi '),
write(Ruum1),
nl,
otsi(Ruum1).

--konstant nl (new line) väljastab ekraanile reavahetuse

Kui aga kõigis ruumides, kuhu praegusest ruumist Ruum pääseb, on juba käidud (s.t. kõigi naaberruumide Ruum1 kohta on olemas lause kaidud(Ru um1) , märgitakse praegune ruum kui tupik (loomulikult peab selle märkima ka kui juba külastatud ruumi) ja minnakse tagasi mingisse ruumi, milles on küll juba käidud, aga mida ei ole veel märgistatud tupikuna. Kuna see lause on eelneva järel , kasutab Prolog seda vaid siis, kui eelmine lause, s.t. tingimus not(kaidud(Ruum1)) ebaõnnestub, seega siin ei ole vaja seda tingimust üldse enam kontrollida:

otsi(Ruum):-

paaseb(Ruum, Ruum1)),
not(clause(tupik(Ruum1), true)),
assert(kaidud(Ruum)),
assert(tupik(Ruum)),
write('Ruumist '),
write(Ruum),
write(' lahen tagasi ruumi '),
write(Ruum1),
nl,
otsi(Ruum1).

Et näidata, et ruumis c3 on väljapääs, paigutame predikaadi otsi(Ruum) esimeseks lauseks lause

otsi(c3):-

write('Väljas!').

Väljapääsu leidmiseks jääb üle vaid anda päring:

? otsi(a1).

Kui pärast esimest päringut käivitada

? otsi(a1).
uuesti, esitab Prolog juba otsetee (ilma tagurdusteta), sest tal on programmi lisatud kõik laused tupikute kohta, kuid tee väljastatakse vormis, nagu liig uks Prolog kogu aeg tagurpidi. See juhtub sellepärast, et Prologil on märgitud kõik ruumid kui käidud, seega ta peab kogu aeg kasutama predikaadi otsi(Ruum) viimast lauset.
Programmilauseid saab kustutada kas käsitsi või süsteemipredikaadiga retractall(käidud(_)), retractall(tupik(_)), seega ruumist a3 väljapääsu otsimiseks võib uue päringu anda kujul:
? retractall(käidud(_)), retractall(tupik(_)), otsi(a3).

(assert, retract, clause jt süsteemipredikaatide kohta vaata ka AMZI_Prolog-i help-i!)

Eesti-Prologi süsteemipredikaat eemalda_kõik on defineeritud AMZI-Prologi süsteemipredikaadi retractall abil järgmiselt:

eemalda_kõik(X):-

retractall(X)


Ülesanne

Kuidas leida tee kahekorruselises labyrindis (mõnes ruumis on trepid korruste vahel)?








Küsimused, probleemid:

jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde