breadthfirst/2, solve/2 — BFS pe graf — Programare Logică și Funcțională

Exerciții › Laboratorul 5, Exercițiul 2

breadthfirst/2, solve/2 — BFS pe graf

Laboratorul 5, Exercițiul 2 advanced Căutare și drumuri (BFS, puzzle-uri)findall / bagof / setof (generate-and-test)Negația ca eșec (not/1, \+)

În cadrul acestui exercițiu, ne dorim să implementăm un algoritm breadth-first search (căutarea în lățimea arborelui). Pentru a face acest lucru:

Definiți o bază de cunoștințe cu două predicate, succesor/2 și objective/1, pentru a defini funcția succesor (muchia dintre două noduri) și pentru a defini nodurile-obiectiv.
Ne dorim un predicat extend/2, care primește ca intrare un drum parțial și returnează toate drumurile care se pot forma. Important! Drumurile se vor obține în ordine inversă, astfel că Head-ul listei va fi mereu nodul curent. Utilizați findall/3.
```
?- extend([3, 1], L).
L = [[5, 3, 1], [4, 3, 1]]
```
Scrieți un predicat breadthfirst/2 care primește o listă de drumuri și: (a) dacă un drum a ajuns la nodul obiectiv, îl returnează, altfel extinde drumul, îl concatenează la celelalte deja existente și reapelează recursiv.
Scrieți un predicat solve/2 care primește un nod de start și returnează toate drumurile (în ordine inversă) până la nodul obiectiv.
```
?- solve(1, R).
R = [[5, 2, 1], [5, 3, 1]]
```

Te-ai blocat?

editor soluție

succesor(1, 2).
succesor(1, 3).
succesor(2, 4).
succesor(2, 5).
succesor(3, 5).
succesor(3, 4).
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).

Tastează o interogare (ex. father_of(sandra, X).) și apasă Enter — sau apasă pe un caz de test de mai jos.

Cazuri de test (2 — apasă pe unul ca să îl rulezi, sau Verifică pentru toate)

extend([3, 1], L). așteptat: L = [[5,3,1],[4,3,1]]

solve(1, R). așteptat: R = [[5,2,1],[5,3,1]]