12

Tee otsimine kaardil (II)

Loengus 6 esitatud kaardil tee otsimise programm oli väga algeline (tee võis läbida sama linna mitu korda, läbitud marsruuti ei salvestatud, suurema linnade arvu korral läheb sealesitatud programm kergesti "umbe", s.t. tuleb Prologi veateade "Fatal Error : Control stack full"). Kuna mitmesugused otsimisülesanded esinevad praktikas väga sageli, on siin toodud veidi efektiivsem kaardil tee otsimise meetod (seegi ei ole veel parim!). Olgu algandmeteks mõnede Eesti linnade vahelised Teepikkused.

tee(tallinn, rakvere,97).
tee(rakvere, kohtla_järve,73).
tee(kohtla_järve, narva,50).
tee(tallinn, paide, 97).
tee(paide, tapa, 49).
tee(tapa, rakvere, 28).
tee(rakvere, jogeva, 72).
tee(paide, poltsamaa, 39).
tee(poltsamaa, tartu, 60).
tee(poltsamaa, jogeva, 27).
tee(jogeva, mustvee, 40).
tee(kohtla_järve, mustvee, 76).
tee(jogeva, mustvee, 40).

Predikaat pääseb on eelmise sümmeetriline sulund:

pääseb(Linn1,Linn2,Teepikkus):-
tee(Linn1, Linn2, Teepikkus).
pääseb(Linn1,Linn2,Teepikkus):-
tee(Linn2, Linn1, Teepikkus).

Predikaadi matk esimene argument Linn1 näitab, millises linnas parajasti ollakse; see muutub matka edenedes, kuni saab samaks kui teine argument Linn2, mis näitab matka sihtkohta. Kolmas argument Kestvus on matka senine kestvus (matka alustades, s.t. päringut andes on see 0) ja neljas argument Linnad on seni läbitud linnade nimistu; selle abil kontrollitakse, et ei tuleks silmuseid (juba külastatud linna ei minna uuesti).
Kui on jõutud eesmärgile (esimene ja teine argument samad), lõpetab Prologi primitiiv ! (cut, lõige) töö ja kasutajale esitatakse matka kogupikkus ja selle ajal läbitud linnade nimistu:

matk(Linn, Linn, Teepikkus, Läbitud):-
!,
esita_tee(Teepikkus, Läbitud).

Olles linnas Linn1 otsitakse järgmine linn Linn, millesse linnast Linn1 otse pääseb, lisatakse linnade L inn1 ja Linn vaheline Teepikkus Teepikkus1 senise matka pikkusele Teepikkus ja jätkatakse sihtpunkti Linn2 viiva tee otsimist linnast Linn, lisades linna Linn1 juba külastatud linnade nimistusse:

matk(Linn1, Linn2, Teepikkus, Läbitud):-
pääseb(Linn1, Linn, Teepikkus1),
ei esineb(Linn, Läbitud),
Teepikkus2 oleks Teepikkus + Teepikkus1,
matk(Linn, Linn2, Teepikkus2, [Linn|Linnad]).

Linnade Linn1 ja Linn2 vaheliste kõigi teede leidmiseks käivitatakse predikaat matk (matka alustades on läbitud 0 kilomeetrit ja kü lastatud ainult linna Linn1); pärast tee esitamist ekraanil oodatakse, kuni kasutaja vajutab ükskõik millisele klaviatuuriklahvile (loe(_)) ja sunnitakse süsteemipredikaadiga uuesti (LPA-Prologis: fail Prolog otsima järgmise reisi. Kui kõik reisid on leitud, lõpetab predikaadi otsi teine lause töö (ilma teise lauseta lõpetaks Prolog töö ebaõnnestumisega, s.t. teatega no):

otsi(Linn1, Linn2):-
matk(Linn1, Linn2, 0, [Linn1]),
loe(_), -- et anda kasutajale aega väljastatud tee lugemiseks
uuesti.
otsi(_,_).

Predikaat esita_tee kirjeldatud reisi: :

esita_tee(Teepikkus, Läbitud):-
kirjuta('Tee pikkus on '),
kirjuta(Teepikkus),
rv,
kirjuta('Läbiti linnad: '),
esita_linnad(Läbitud).
esita_linnad([]).
esita_linnad([Linn | Linnad]):-
esita_linnad(Linnad),
rv,
kirjuta(Linn),
rv.

Kahe linna vahel tee otsimise predikaati matk(Linn1, Linn2, Teepikkus, Linnad) võib kasutada ka kahe linna vahelise lühima tee pikkuse leidmiseks.
Selleks muudame predikaadi matk esimest lauset, asendades seal matka esitamise ekraanil uue lause reis(Linn1, Linn2, Teepikkus) lisamisega programmi:

matk(Linn, Linn, Teepikkus, Läbitud):-
!,
lisa(reis(Linn1, Linn2, Teepikkus)).

Kahe linna vahelise lühima tee pikkuse leidmiseks kogume kõigi erinevate reiside pikkused üheks nimistuks ja kasutame siis loengus 11 vaadeldud predikaati min kõigi teepikkust e seas minimaalse leidmiseks:
lyhim(Linn1, Linn2, Lyhim_tee):-
otsi(Linn1, Linn2),
lahendid(Teepikkus, reis(Linn1, Linn2, Teepikkus), Teepikkused),
min(Teepikkused, Lyhim_tee).

Ülesandeid

1. Lühimat teed arvutav predikaat ei näita, kus reis kulges (millised linnad läbiti). Koosta predikaat linnadevahelise lühima tee esitamiseks. Selleks on mitu võimalust:
  • lauses otsi meeles pidada ka läbitud linnade nimistu lausega lisa(reis(Linn1, Linn2, Teepikkus, Linnad)), koguda siis lausega lahendid([Teepikkus, Linnad], reis(Linn1, Linn2, Teepikkus, Linnad), Teepikkused) üheks nimistuks kõik paarid (kaheelemendilised alamnimistud) [Teepikkus, Linnad] ja täiendada predikaati min nii, et see leiaks kõigi selliste kaheelemendiliste nimistute nimistus selle, mille esimene element on minimaalne;
  • lisada fakt reis(Linn1, Linn2, Teepikkus, Linnad) ainult sel juhul, kui kas ühtegi sellist fakti veel ei ole (see on esimene) või äsjaarvutaud reisi pikkus on väiksem kui salvestatud faktis reis(Linn1, Linn2, Teepikkus, Linnad) esinev; sellisel juhul kustutatakse enne salvestatud fakt reis(Linn1, Linn2, Teepikkus, Linnad) ja salvestatakse siis uus, kus on praegu leitud reisi andmed (siis on salvestatud faktis alati kirjeldatud seni leitud reisidest lühim) ja kui predikaat otsi lõpetab töö (predikaadi teises lauses) väljastatakse selle lühima reisi teepikkus ja marsruut.

2. Koosta programm, mis etteantud sisend- ja väljundruudu ja tee pikkuse põhjal leiab arvlabürindis kõik selle pikkusega teed.



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

Tagasi loengute sisukorra juurde