/* PLAN_F optymalizacja trasy i zliczanie dlugosci  */
/* w petli typu "nawrot - fail"                     */



/* 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).


/***     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):-
     przejazd(Miasto,Kandydat,D),
     not(member(Kandydat,Robocza)),
     NowaDlugosc is Dlugosc + D,
/* */     limit(G),
/* */     NowaDlugosc < G,
     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).


/* poszukiwanie rozwiazania optymalnego metoda ograniczania (B&B) */
/* technika petli z fail */

plan_f(Miasto,Cel,_,_,Ograniczenie):-
     retractall(limit(_)),
     retractall(trasa(_)),
     assert(limit(Ograniczenie)),
     assert(trasa([])),
     plan(Miasto,Cel,Wynik1,Dystans1,Ograniczenie),
     write(Wynik1),nl,write(Dystans1),nl,write('*****'),
     limit(G),
     Dystans1 < G,
     retract(limit(G)),
     asserta(limit(Dystans1)),
     change(Wynik1),
     fail.
plan_f(_,_,Wynik,Dystans,_):-
     retract(limit(Dystans)),
     retract(trasa(Wynik)).     

change(Wynik):- retract(trasa(_)),asserta(trasa(Wynik)),!.


/* 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).