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
CODE>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
FONT>; ü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