80 päevaga ümber maailma (tee otsimine kaardil)
Suhte transitiivse sulundi leidmine (nagu oli näiteks predikaat
järglane predikaadile laps)
esineb praktilistes ülesannetes üllatavalt sageli. Transitiivse
sulundi arvut amisele taanduvad näiteks enamus kaardil tee otsimise
ülesannetest. Koostame järgnevas programmi, mis leiab kaardil
tee antud kahe linna vahel ja arvutab ka kogu matka kestvuse (hinna, kilometraazi
vm); lähteandmetena on kasutatud Phileas Fogg'i poolt ka sutatud andmeid
(J. Verne, "80 päevaga ümber maailma") laeva- ja rongimatkade
kestvuse kohta:
Londonist Suessi 7 päeva
Suessist Bombaysse 13 päeva
Bombayst Calcuttasse 3 päeva
Calcuttast Hongkongi 13 päeva
Hongkongist Yokohamasse 6 päeva
Hongkongist Shanghaisse 3 päeva
Shanghaist Yokohamasse 2 päeva
Yokohamast San Franciscosse 22 päeva
San Franciscost New Yorki 7 päeva
New Yorkist Londoni 9 päeva
Need andmed on loomulik esitada kolmekohalise predikaadiga
kestab(london, suess, 7).
- kestab(suess, bombay, 13).
- kestab(bombay, calcutta, 3).
- kestab(calcutta, hongkong, 13).
- kestab(hongkong, yokohama, 6).
- kestab(hongkong, shanghai, 3).
- kestab(shanghai, yokohama, 2).
- kestab(yokohama, san_francisco, 22).
- kestab(san_francisco, new_york, 7).
- kestab(new_york, london, 9).
Tee suvalisest linnast Linn1 teise
linna Linn2 leiab predikaat matk,
mis on predikaadi kestab transitiivne
sulund; ka selle predikaadi kolmas argument on matka kestvus.
Kui linnade vahel on otsereis, mis on kirjeldatud predikaadiga kestab,
taandub predikaat matk predikaadiks kestab:
matk(Linn1, Linn2, Kestvus):-
- kestab(Linn1, Linn2,Kestvus).
Kui tee on pikem (kasutatakse mitut predikaadiga kestab
kirjeldatud reisi), otsitakse algul mingi linn Linn,
kuhu otse pääseb (s.t. linnade Linn 1
ja Linn vahel on reis, mis on kirjeldatud
predikaadiga kestab), ja jätkatakse siis
rekursiivselt. Kui esimese otsereisi kestvus on Kestvus1
ja lõpposa kestvus Kestvus2, peab kogu
matka kestvus Kestvus olema nende summa, selle
arvutab Prologi süsteemipredikaat is:
matk(Linn1, Linn2, Kestvus):-
- kestab (Linn1, Linn, Kestvus1),
matk(Linn, Linn2, Kestvus2),
Kestvus is Kestvus1 + Kestvus2.
Predikaadi is kasutamisel ei tohi
unustada, et Prologi laused ei ole täidetavad käsklused (nagu
on näiteks Basic'u või Pascal'i omistamislause), vaid nad kirjeldavad
suhteid tegelikkuse faktide või programmi muutujate vahel. Kuigi
lause
Kestvus is Kestvus1 +
Kestvus2.
näeb välja nagu käsukeelte omistamislause, kirjeldab
ta vaid seost muutujate Kestvus, Kestvus1
ja Kestvus2 väärtuste vahel. Sellepärast
ei saa Prologis kunagi kasutada sama muutujat is-lause
mõlemal poolel, st.
X is X + 1.
on Prologis viga!
Kui nüüd küsida
?- matk(london,calcutta,P).
annab Prolog algul õige vastuse:
P = 23
aga siis hakkab andma lisa vastuseid
P = 103
P = 183
jne. Need lisavastused saab ta, tehes vahepeal tiiru ümber
kogu maakera; ka ei oska see programm veel liikuda tagurpidi, s.t. päring
?- matk(calcutta, london, P).
lõpeb väga pika mõtlemisega kuni lõpuks
mälu täitub.
Küsimused, probleemid:
jaak@cc.ttu.ee
Tagasi loengute sisukorra juurde