Sumar
Un tipar des întâlnit: avem un predicat succesor/2 (sau s/2, connected/2) care descrie muchiile, un predicat objective/1 care marchează nodurile-obiectiv, și vrem toate drumurile de la un start la un obiectiv.
BFS-ul din breviar folosește o coadă de drumuri parțiale. La fiecare pas: ia primul drum, dacă ajunge la obiectiv îl returnează, altfel îl extinde cu toți succesorii neexplorați și concatenează la restul cozii.
Sintaxă completă (din breviar)
% baza de cunoștințe — exemplu
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).
% extinde un drum parțial cu toți succesorii neexplorați
extend([Node | Path], NewPath) :-
findall([NewNode, Node | Path],
(succesor(Node, NewNode), not(member(NewNode, [Node | Path]))),
NewPath).
% BFS — lista argumentelor reprezintă coada de drumuri parțiale
breadthfirst([[Node | Path] | _], [Node | Path]) :- objective(Node).
breadthfirst([Path | PathTail], Solution) :-
extend(Path, ExtendedPath),
append(ExtendedPath, PathTail, NewPath),
breadthfirst(NewPath, Solution).
% colectează toate soluțiile
solve(Start, Solution) :-
findall(S, breadthfirst([[Start]], S), Solution).
Comportament
Important — drumurile se construiesc în ordine inversă: Head-ul listei este mereu nodul curent. [5, 3, 1] reprezintă drumul 1 -> 3 -> 5.
?- solve(1, R).
R = [[5, 2, 1], [5, 3, 1]]
Adică două drumuri de la 1 la 5: 1 -> 2 -> 5 și 1 -> 3 -> 5.
Idiomuri
Drumuri minime — filtrează pe lungime după ce ai generat toate:
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).
Puzzle-uri (Zebra, word puzzle) — nu e BFS pur, e member/2 + constrângeri. Folosim structura Prolog-ului de backtracking ca „solver”:
solution(Street, ZebraOwner) :-
Street = [house(1,_,_,_,_,_), house(2,_,_,_,_,_), ...],
member(house(_, english, red, _, _, _), Street),
...,
member(house(_, ZebraOwner, _, zebra, _, _), Street).
De ce not(member(...))?
Fără el, BFS-ul revizitează nodurile și intră în buclă infinită pe grafuri cu cicluri. Păstrăm în Path toate nodurile vizitate pe drumul curent.
Reverse-path vs forward-path
Păstrăm drumurile inversate pentru că adăugarea la cap e O(1) în Prolog ([NewNode | Path]), pe când la coadă e O(n) (append). La afișare, dacă vrem ordinea firească: reverse(Path, ForwardPath).