/* PLAN - program znajdowania trasy polaczen miedzy miastami */ %%% Przeszukiwanie wgłąb z nawrotami droga(krakow,katowice). droga(katowice,opole). droga(wroclaw,opole). droga(krakow,zakopane). droga(krakow,kielce). droga(krakow,tarnow). droga(kielce,radom). droga(radom,warszawa). droga(warszawa,poznan). droga(warszawa,gdansk). droga(warszawa,lodz). droga(poznan,szczecin). droga(poznan,wroclaw). droga(tarnow,rzeszow). droga(rzeszow,lublin). droga(lublin,bialystok). droga(warszawa,bialystok). droga(szczecin,koszalin). droga(koszalin,gdansk). %%% domknięcie symetryczne relacji droga/2 przejazd(X,Y):- droga(X,Y). przejazd(X,Y):- droga(Y,X). p(X,Y):- przejazd(X,Y). %%% Depth-First Strategy with calculating the depth path(F,F,T,T,D,D). %%% A path from F to F is defined the current working path T path(I,F,Path,T,L,D):- %%% A path from I to F where Path is the current path p(I,N), %write(N), nl, %%% Find a new node N not(member(N,Path)), %%% Check for ne cycle L1 is L+1, path(N,F,[N|Path],T,L1,D). %%% A Path from N to F - the last before F %%% Breadth-First Strategy: %%% Instead of a single path, the solution and the state of the search is represented as a set of paths %%% Technically: this is a list of lists bf(F,[[F|Path]|_],[F|Path]). bf(F,[Path|SetOfPaths],T):- extend(Path,NewPaths), append(SetOfPaths,NewPaths,NewSetOfPaths), bf(F,NewSetOfPaths,T). extend([N|Path],NewPaths):- bagof([NextN,N|Path],(p(N,NextN),not(member(NextN,[N|Path]))),NewPaths),!. extend(_,[]). go(I,F,Path):- bf(F,[[I]],Path). %%% Breadth-First Strategy with depth calculating %%% Instead of a single path, the solution and the state of the search is represented as a set of paths %%% Technically: this is a list of lists godc(I,F,Path,D):- bf(F,[[I]],Path), length(Path,D).