/* PLAN_D zliczanie dlugosci trasy */

%%% Wyznaczanie trasy metodą przeszykiwania wgłąb 
%%% ze zliczaniem długości trasy i ograniczeniem dlugosci maksymalnej




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

%%% domkniecie symetryczne droga/2

przejazd(X,Y,D):- droga(X,Y,D).
przejazd(X,Y,D):- droga(Y,X,D).


%%% główna pętla szukania trasy

%%% szukaj_trasy(Start,Cel,Robocza,Trasa,DlugoscRoboczej,DlugoscTrasy,Ograniczenie).

szukaj_trasy(Cel,Cel,Trasa,Trasa,Dystans,Dystans,_).   %%% !.
szukaj_trasy(Miasto,Cel,Robocza,Trasa,Dlugosc,Dystans,Ograniczenie):-
     przejazd(Miasto,Kandydat,D), write(Kandydat), write(' || '),
     not(member(Kandydat,Robocza)),
     NowaDlugosc is Dlugosc + D,
     NowaDlugosc < Ograniczenie,
     szukaj_trasy(Kandydat,Cel,[Kandydat|Robocza],Trasa,
                  NowaDlugosc,Dystans,Ograniczenie).

%%% Inicjacja poszukiwan plan/5

plan(Miasto,Cel,Trasa,Dystans,Ograniczenie):-
     szukaj_trasy(Cel,Miasto,[Cel],Trasa,0,Dystans,Ograniczenie),
     nl, nl, write('plan: '),write('+++'),write(Trasa), write(': '),write(Dystans),write('+++'),nl,nl,nl. %%% !

%%% Inicjacja poszukiwań planu optymalnego plan_opt/5

plan_opt(Miasto,Cel,Trasa,Dystans,Ograniczenie):-
     minimal(Miasto,Cel,[],Ograniczenie,Trasa,Dystans).

%%% minimal(<start>,<cel>,<trasa_tymczasowa>,<dlugosc_trasy_tymczasowej>,<trasa_optymalna>,<dlugosc_trasy_optymalnej>)     

minimal(Miasto,Cel,_,Dystans1,Trasa,Dystans):-
     plan(Miasto,Cel,W,D,Dystans1),!,
%%%   nl,nl,nl, write('Plan aktualny: '),nl,write(W),nl,write(D),nl,write('*********************'),nl,
     minimal(Miasto,Cel,W,D,Trasa,Dystans).
minimal(_,_,Wynik,Dystans,Wynik,Dystans).          
     


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% Database  (Factbase) %%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     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).