%%%%%%%%%%  TRASER  %%%%%%%%%%
%%% Program heurystyczny szuka trasy z ograniczeniem dlugosci
%%% Preferuje misata lezace najblizej celu; strategia zachłanna
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


/* Wypisywanie listy miast */
writelist([]).
writelist([X|XT]):- write(X),nl,writelist(XT).


/* Definiowanie istnienia drogi przjazdu
        jako relacji symetrycznej        */
przejazd(X,Y,D):- droga(X,Y,D).
przejazd(X,Y,D):- droga(Y,X,D).

     
/* Wstawianie miasta do listy miast
   z zachowaniem kolejnosci - miasto
   najblizsze celu jest pierwsze na 
   liscie, najdalsze - ostatnie     */
wstaw(X,[],[X],_).
wstaw(X,[Y|YT],[Y|ZT],Cel):- blizej(Y,X,Cel),!, wstaw(X,YT,ZT,Cel).
wstaw(X,[Y|YT],[X,Y|YT],Cel):- blizej(X,Y,Cel).
     
/* Definicja odleglosci w sensie geometrycznym 
   i porownywanie odleglosci X i Y od Celu    */
blizej(X,Y,Cel):- polozenie(X,Xx,Yx), polozenie(Y,Xy,Yy), 
                  polozenie(Cel,Xc,Yc), 
                  DX is sqrt((Xc-Xx)*(Xc-Xx)+(Yc-Yx)*(Yc-Yx)),
                  DY is sqrt((Xc-Xy)*(Xc-Xy)+(Yc-Yy)*(Yc-Yy)),
                  DX =< DY.    

/* Porzadkowanie listy miast-kandydatow do 
   rozwijania wzgledem odleglosci od Celu  */      
uporzadkuj([X],[X],_):-!.
uporzadkuj([X|XT],LU,Cel):- uporzadkuj(XT,U,Cel), wstaw(X,U,LU,Cel).      
     
     
/* Wyszukiwanie i okreslanie kolejnosci miast
   do dalszego badania; predykat niedeterminist. */
ruch(Miasto,Cel,Kandydat):-
     findall(Xkandydat,przejazd(Miasto,Xkandydat,_),ListaKandydatow),
     uporzadkuj(ListaKandydatow,ListaUporzadkowana,Cel),
     select(Kandydat,ListaUporzadkowana,_).
     
/***     Glowna petla programowa     ***
 * wyszukiwanie trasy i zliczanie odleglosci */     
     
szukaj_trasy(Cel,Cel,Trasa,Dystans,Trasa,Dystans,_). %%% :- !.
szukaj_trasy(Miasto,Cel,Robocza,Dlugosc,Trasa,Dystans,Ograniczenie):-
     ruch(Miasto,Cel,Kandydat),
     not(member(Kandydat,Robocza)),
     przejazd(Miasto,Kandydat,D),
     NowaDlugosc is Dlugosc + D,    
     NowaDlugosc < Ograniczenie,
     szukaj_trasy(Kandydat,Cel,[Kandydat|Robocza],NowaDlugosc,Trasa,
                  Dystans,Ograniczenie).


/*  Inicjacja poszukiwan  */   
plan(Miasto,Cel,Trasa,Dystans,Ograniczenie):-
     szukaj_trasy(Cel,Miasto,[Cel],0,Trasa,Dystans,Ograniczenie).


/* Baza danych programu */
     droga(krakow,rzeszow,162).
     droga(krakow,lublin,273).
     droga(krakow,kielce,117).
     droga(krakow,lodz,241).
     droga(krakow,katowice,81).
     droga(rzeszow,lublin,168).
     droga(rzeszow,kielce,168).
     droga(lublin,kielce,179).
     droga(lublin,lodz,252).
     droga(lublin,warszawa,161).
     droga(lublin,bialystok,254).
     droga(kielce,lodz,147).
     droga(kielce,warszawa,177).
     droga(kielce,katowice,161).
     droga(kielce,opole,223).
     droga(katowice,opole,100).
     droga(katowice,lodz,193).
     droga(opole,wroclaw,84).
     droga(opole,lodz,184).
     droga(opole,poznan,255).
     droga(wroclaw,lodz,215).
     droga(wroclaw,poznan,171).
     droga(wroclaw,zielona_gora,153).
     droga(zielona_gora,poznan,132).
     droga(zielona_gora,szczecin,217).
     droga(szczecin,poznan,238).
     droga(szczecin,bydgoszcz,258).
     droga(szczecin,koszalin,156).
     droga(koszalin,poznan,242).
     droga(koszalin,bydgoszcz,195).
     droga(koszalin,gdansk,184).
     droga(gdansk,bydgoszcz,174).
     droga(gdansk,warszawa,343).
     droga(gdansk,olsztyn,157).
     droga(olsztyn,bydgoszcz,206).
     droga(olsztyn,lodz,284).
     droga(olsztyn,warszawa,214).
     droga(olsztyn,bialystok,224).
     droga(bialystok,warszawa,194).
     droga(bydgoszcz,poznan,129).
     droga(bydgoszcz,lodz,202).
     droga(bydgoszcz,warszawa,258).
     droga(bydgoszcz,opole,325).
     droga(poznan,lodz,201).
     droga(poznan,warszawa,303).
     droga(lodz,warszawa,133).
     
     polozenie(szczecin,0,11.3).
     polozenie(zielona_gora,1.5,6.2).
     polozenie(koszalin,3,13.7).
     polozenie(poznan,4.3,7.8).
     polozenie(wroclaw,4.4,3.6).
     polozenie(opole,6.3,2).
     polozenie(bydgoszcz,6.5,10.1).
     polozenie(gdansk,7.8,14.2).
     polozenie(katowice,8.4,0.7).
     polozenie(lodz,9.4,5.6).
     polozenie(krakow,10.5,0).
     polozenie(olsztyn,11.4,12.2).
     polozenie(kielce,11.8,2.8).
     polozenie(warszawa,12.5,7.2).
     polozenie(rzeszow,14.8,0.2).
     polozenie(lublin,15.7,4).
     polozenie(bialystok,16.5,10.4).