minimumPaths/2 — drumuri BFS de lungime minimă
Fie predicatele succesor/2 și objective/1. Adaptați algoritmul BFS astfel încât să păstrăm drumurile cele mai scurte care ajung de la un nod de start la un nod obiectiv.
Dacă rulați solve(1, R), veți găsi R = [[5, 3, 4, 2, 1], [5, 2, 1], [5, 3, 1], [5, 3, 4, 1]]. Vrem să păstrăm doar drumurile de lungime minimă, adică de lungime 3.
Hint: găsește toate drumurile cu
solve/2, mapează fiecare la lungimea lui cufindall+length, ia minimul, filtrează din nou prinfindall.
Te-ai blocat?
editor
soluție
succesor(1, 2).
succesor(1, 3).
succesor(1, 4).
succesor(2, 4).
succesor(2, 5).
succesor(3, 5).
succesor(3, 4).
succesor(4, 3).
objective(5).
extend([Node | Path], NewPath) :-
findall([NewNode, Node | Path],
(succesor(Node, NewNode), not(member(NewNode, [Node | Path]))),
NewPath).
breadthfirst([[Node | Path] | _], [Node | Path]) :- objective(Node).
breadthfirst([Path | PathTail], Solution) :-
extend(Path, ExtendedPath),
append(ExtendedPath, PathTail, NewPath),
breadthfirst(NewPath, Solution).
solve(Start, Solution) :-
findall(S, breadthfirst([[Start]], S), Solution).
min([], 0) :- !.
min([X], X) :- !.
min([H | T], MinTail) :-
min(T, MinTail),
MinTail =< H, !.
min([H | T], H) :-
min(T, MinTail),
H =< MinTail.
minimumPaths(Start, Result) :-
solve(Start, AllPaths),
findall(Length, (member(Path, AllPaths), length(Path, Length)), Lengths),
min(Lengths, MinLength),
findall(Path,
(member(Path, AllPaths), length(Path, Length), Length =:= MinLength),
Result).
?-
Tastează o interogare (ex. father_of(sandra, X).) și apasă Enter — sau apasă pe un caz de test de mai jos.
Cazuri de test (1 — apasă pe unul ca să îl rulezi, sau Verifică pentru toate)
?
minimumPaths(1, R).
așteptat: R = [[5,2,1],[5,3,1]]