Tee otsimine labyrindis

Tee otsimine mitmesugustes struktuurides (graafidel) (ka labürint on selline graaf) on üks kõige sagedamini esinevaid tehisintellekti ülesandeid. Selliste ülesannete lahendamiseks on välja töötatud sadu algoritme. Järgnevas vaatleme sellise ülesande vist kõige lihtsamat juhtu - tee otsimist labürindis (ka labürint on graaf!).

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

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

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 ja jätkatakse otsimist järgmisest ruumist Ruum1 ; ühtlasi kirjutatakse ekraanile, kuidas parajasti liigutakse.
Ruumi Ruum meelespidamiseks on kõige lihtsam lisada vastav lause käidud(Ruum) Prologi programmile (teine võimalus oleks nimistute kasutamine).
Programmi uue lause Lause lisamiseks ja eemaldamiskes on Prologi süsteemi- (s.t. sisseehitatud) predikaadid assert(Lause) ja retract(Lause); seega näiteksrida assert(käidud(Ruum)) on meelespidamiseks, et ruumis Ruum on juba käidud.

Uute lausete lisamise-eemaldamise kasutamisel pole alati selge, kas mõne predikaadi jaoks programmis (juba) on lauseid, näiteks tee otsimist alustades pole programmis veel ühtki lauset käidud(Ruum). Kui programmis kasutatakse sellist predikaati, mille kohta pole ühtegi lauset (kui tahetakse predikaadiga käidud(Ruum) kontrollida, kas ruumis Ruum juba on käidud), annab Prolog veateate - ta arvab, et programmeerija on unustanud vastava predikaadi kirjeldamata. Sellepärast tuleb lisatavate-eemaldatavad predikaadid kirjeldada programmi algul lauses dynamic, kus predikaadi nimele järgneva kaldkriipsu taga on märgitud predikaadi argumentide arv (samanimelised, kuid erineva argumentide arvuga predikaadid on Prologis erinevad!), s.t. programm algab lausega

Dünaamilise predikaadi kasutamisel sõnastatakse kontroll süsteemipredikaadi clause(Pea,Keha) abil, mis kontrollib, kas lause Pea:-Keha juba esineb programmis. Faktide (lausete, milles puudub :-) kontrollimisel on Keha asemel Prologi konstant true (alati tõene lause), seega näiteks fakti tupik(c3) olemasolu programmis kontrollib lause clause(tupik(c3),true).

Tee otsimise esimene samm oleks sellise ruumi leidmine, kus veel pole käidud; praegune ruum märgitakse käiduks ja otsimist jätkatakse selles uues (varem külastamata) ruumis:

otsi(Ruum):-
pääseb(Ruum, Ruum1),
not(clause(käidud(Ruum1), true)),
assert(käidud(Ruum)),
write('Ruumist '),
write(Ruum),
write(' lahen ruumi '),
write(Ruum1),
nl, %konstant nl (new line) väljastab ekraanile reavahetuse
otsi(Ruum1).

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 käidud(Ruum1), näiteks kui Prolog liigub algul ruumi a1 -> a2 -> a3 -> b3), märgitakse praegune ruum Ruum (b3) kui tupik (loomulikult peab selle märkima ka külastatud ruumiks) ja minnakse tagasi mingisse ruumi, milles on küll juba käidud, aga mida ei ole veel märgistatud tupikuna (ka ruumidest a3, a2 peab Prolog tagasi liikuma juba külastatud ruumi)..

Kuna see teine tee-otsimise lause on eelneva järel , kasutab Prolog seda vaid siis, kui eelmine lause, s.t. tingimus not(käidud(Ruum1)) ebaõnnestub, seega siin ei ole vaja siin vaja tingimust käidud(Ruum1) üldse kontrollida; loomulikult tuleb kontrollida, et ei mindaks ruumi, mis on kord juba tupikuks kuulutatud:

otsi(Ruum):-
pääseb(Ruum, Ruum1),
not(clause(tupik(Ruum1), true)),
assert(käidud(Ruum)),
assert(tupik(Ruum)),
write('Ruumist '),
write(Ruum),
write(' lähen tagasi ruumi '),
write(Ruum1),
nl,
otsi(Ruum1).

Et näidata, et ruumis c3 on väljapääs, paigutame predikaadi otsi(Ruum) esimeseks lauseks (seda kontrollitakse kõige esimesena) lause

Kui soovitakse programmi lisatud laused käidud(Ruum), tupik(Ruum) eemaldada (näiteks kasutatakse mingi teise labürindi kirjeldust), siis seda saab teha süsteemipredikaadiga retractall(käidud(_)), retractall(tupik(_)) (allkriips _ on nn. anonüümne muutuja - muutuja, mille väärtus ja seega ka nimi pole olulised), seega näiteks ruumist a3 väljapääsu otsimiseks võib uue päringu anda kujul:

(assert, retract,clause jt süsteemipredikaatide kohta vaata ka Prolog-i Help-i, erinevates Prologi realisatsioonides võib olla väikesi erinevusi nende kasutamises!)

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

2. Kõigis otsimisülesannetes peaks algus- ja sihtpunkt olema programmi käivitamisel antavateks parameetriteks, kuid ülalesitatud programmis on väljapääs (s.t. sihtpunkt) programmi "sisse tinutatud" - see on vastuolu elementaarse programmeerimiskultuuriga. Ülalkirjeldatud predikaati otsi on lihtne muuta "kultuursemaks", kui sellele lisada veel üks argument, mis "peab meeles" sihtkoha, s.t. kirjeldada see kujul otsi(Praegune_ruum, Jargmine_ruum, Sihtkoht), kus Praegune_ruum ja Jargmine_ruum on nagu eespool, kuid Sihtkoha väärtus antakse käivitamisel ja predikaadi esimene lause (lõpetamistingimus) tuleks kujul:

otsi(Sihtkoht,_,Sihtkoht).

s.t. kui praegune ruum ongi sihtkoht, siis võib lõpetada. Modifitseeri vastavalt ka predikaadi otsi teist ja kolmandat lauset (ka nendes peab otsi olema nüüd kolme argumendiga - erineva arvu argumentidega predikaate loeb Prolog erinevateks).

Tee otsimine labürindis erineb väga vähe tee otsimisest kaardil - ruume võib samastada linnadega, uksi/treppe - otseteedega (s.t. teelõikudega, mis ei läbi ühtegi vahelinna) linnade vahel. Kirjelda Prologile kõrvalolev kaart ja koosta predikaat, mis kõrvaloleva kaardi sisestamisel leiab tee ükskõik milliseste kahe linna vahel.