UL/FRI/UNI-RI/MOS/Izpiti/2005-10-06-prolog

Načrtujemo potovanje do Tokia. Zbrali smo podatke o nekaj letalskih povezavah. Za vsako povezavo poznamo čas trajanja leta in razdaljo povezava(Zacetek, Konec, Cas, Razdalja). Zaradi različnih postopkov (carina ipd.) je na vsakem letališču drugačen čas čakanja. Podatke o čakanju hranimo v obliki cakanje(Letalisce, CasCakanja). Mednarodne oznake letališč so: Pariz-cdg, Rim-fco, New York-jfk, Los Angeles-lax, Singapur-sin, Ljbljana-lju, Tokio-nrt.

povezava(lju,cdg,2,955).
povezava(lju,fco,1,506).
povezava(cdg,fco,3,1100).
povezava(cdg,jfk,7,5830).
povezava(cdg,lax,10,9096).
povezava(cdg,sin,12,10712).
povezava(jfk,lax,5,3971).
povezava(jfk,nrt,6,5486).
povezava(lax,nrt,7,6230).
povezava(fco,jfk,8,6861).
povezava(fco,sin,11,10039).
povezava(sin,nrt,11,9857).

cakanje(cdg,4).
cakanje(fco,5).
cakanje(jfk,2).
cakanje(lax,2).
cakanje(sin,1).
cakanje(lju,1).
cakanje(nrt,1).

Vprašanje 1

(15%) V prologu definirajte predikat obstajaPot(Zacetek,Konec), ki preveri, če obstaja pot med tema letališčema.

Rešitev

obstajaPot(Zacetek, Konec):-
	povezava(Zacetek, Konec, _, _).
 
 
obstajaPot(Zacetek, Konec):-
	povezava(Zacetek, X, _, _),
	obstajaPot(X, Konec).

Vprašanje 2

(30%) Napiši predikat trajanjePoti(Zacetek,Konec,Cas,Pot). Predikat naj z vračanjem poišče vse poti med letališčema Zacetek in Konec. Vrne naj pot in čas poti. V čas naj bo všteto trajanje vseh povezav in čakanje na vseh letališčih, tudi začetnem in končnem. pimer uporabe:

        ?-trajanjePoti(lju,fco,Cas,Pot).
	Cas = 15, P = [lju,cdg,fco] ?

Rešitev

trajanjePoti(Z,K,C,[Z,K]) :- Z \== K,
        povezava(Z,K,CP,_),
        cakanje(Z,CZ),
        cakanje(K,CK),
        C is CP+CZ+CK.
 
trajanjePoti(Z,K,C,P) :- Z \== K,
         povezava(Z,X,CP,_),
         trajanjePoti(X,K,CS,P1),
         cakanje(Z,CC), P = [Z|P1], 
         C is CS+CP+CC.

Vprašanje 3

(20%) Napisi predikat vseNajkrajsePoti, ki zgradi bazo vseh najkrajsih poti oblike najkrajsaPot(lju,fco,7). Namig: uporabi proceduro trajanjePoti(Z,K,C,P) iz prejšnje naloge.
Rešitev

    vseNajkrajsePoti:-
	    cakanje(X,_),
       	    cakanje(Y,_),
	    X \== Y,
	    setof(C, X^Y^C^P^trajanjePoti(X,Y,C,P), L),
	    sort(L, [M|_]),
	    assert(najkrajsaPot(X,Y,M)),
	    fail.

Vprašanje 4

(35%) Napiši predikat dolzinaPoti(Pot,Dolzina). Predikat naj vrne dolžino podane poti. Primer uporabe:

	?-dolzinaPoti([lju,cdg,fco],Dolzina).
        Dolzina = 2055 ?

Rešitev

    dolzinaPoti([],0).
    dolzinaPoti([_], 0).
    dolzinaPoti([H,T|Rest], Dolzina):-
	    povezava(H,T,_,P),
    	    dolzinaPoti([T|Rest], Dolzina1),
	    Dolzina is Dolzina1 + P.

Poleg tega definiraj še operatorje, ki ti bodo omogaočali poizvedovanje v naravnem jeziku, kot v spodnjih primerih:

        ?-Koliko narazen sta lju in jfk.
        Koliko = 6785 ? ;	Koliko = 8916 ? ; ...
        ?-Koliko narazen sta lju in B.
        Koliko = 2955, B = cdg ? ; ...

% men javi Operator clash
:-op(200, xfx, in).
:-op(150, fx, sta).
:-op(100,xfx, narazen).
 
% tole pa deluje
:-op(120, xfy, in). 
:-op(150, fx, sta). 
:-op(200,xfx, narazen). 
 
 
narazen(K,Z):-
 Z=sta(in(X,Y)),
 trajanjePoti(X,Y,_,Pot),
 dolzinaPoti(Pot,K).