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 kasutatud 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).

Predikaat kestab kirjeldab matka graafi kaared, s.t. vaid vahetult ühe sõidukiga (linnast linna - buss, laev) liigeldavad reisid. Pikemad teed suvalisest linnast Linn1 teise linna Linn2 (mis koosnevad mitmest järjestikulisest reisist) 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 lähtekohast Linn1 sihtkohta Linn2 on pikem (kasutatakse mitut predikaadiga kestab kirjeldatud reisi), otsitakse algul mingi linn Linn, kuhu otse pääseb (s.t. linnade Linn1 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 summ. Selle arvutab Prologi süsteemipredikaat is - see on Prolog-i analoog omistamislausele; Swi-Prologis võib (erinevalt standardist) kasutada ka võrdusmärki =.

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 või Prologis kunagi kasutada sama muutujat is-lause mõlemal poolel, st. lause
X is X + 1.
on Prologis viga, sest kui seda vaadeldakse suhtena muutujate vahel, on see võimatu (umbes sama kui 2=2+1)!

Kui nüüd küsida

?- matk(london,calcutta,P).
annab Prolog algul õige vastuse:
P = 23
aga siis hakkab andma lisavastuseid:
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(suess, london, P).
annab vastuseks tee, mis saadakse ümbermaailmareisiga - otseteed see programm veel ei "näe"; selleks tuleks muuta teede graaf sümmeetriliseks ja lisada tingimused minimaalse tee leidmiseks.
Küsimused, probleemid: ©2004 Jaak Henno