6


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