path/2 — drum pe un graf orientat — Programare Logică și Funcțională

Exerciții › Laboratorul 4, Exercițiul 3

path/2 — drum pe un graf orientat

Laboratorul 4, Exercițiul 3 medium Relații recursive pe baze de cunoștințe Căutare și drumuri (BFS, puzzle-uri)Negația ca eșec (not/1, \+)

Fie următoarea bază de cunoștințe, formată prin intermediul predicatului connected/2 (vezi baza din editor).

Scrieți un predicat path/2 care indică dacă dintr-un punct puteți să ajungeți într-un alt punct (în mai mulți pași), legând conexiunile din baza de cunoștințe. Drumurile se consideră unidirecționale (relația nu este simetrică).

Întrebări pentru verificare:
- Puteți ajunge din punctul 5 în punctul 10?
- În ce puncte puteți să ajungeți plecând din 1?
- Din ce puncte puteți să ajungeți în punctul 13?
Testați programul pentru baza de cunoștințe:
```
connected(1, 2).
connected(2, 1).
connected(1, 3).
connected(3, 4).
```
cu întrebarea ?- path(1, 4).

Observație: dacă graful conține cicluri, este posibil ca programul să nu își termine execuția.
Scrieți un predicat care determină dacă există drumuri, evitând ciclurile din graf.

Hint: utilizați un predicat auxiliar care reține într-o listă punctele vizitate până în momentul curent.

Te-ai blocat?

editor soluție

connected(1,2).
connected(3,4).
connected(5,6).
connected(7,8).
connected(9,10).
connected(12,13).
connected(13,14).
connected(15,16).
connected(17,18).
connected(19,20).
connected(4,1).
connected(6,3).
connected(4,7).
connected(6,11).
connected(14,9).
connected(11,15).
connected(16,12).
connected(14,17).
connected(16,19).

% (1) varianta naivă — se poate bucla pe grafuri cu cicluri
path(X, Y) :- connected(X, Y).
path(X, Y) :-
    path(X, Z),
    connected(Z, Y).

% (2) varianta cu listă de vizitați — sigură la cicluri
path_safe(X, Y) :-
    path_safe(X, Y, [X]).

path_safe(X, Y, _) :- connected(X, Y).
path_safe(X, Y, Visited) :-
    connected(X, Z),
    not(member(Z, Visited)),
    path_safe(Z, Y, [Z | Visited]).

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

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

path(5, 10). așteptat: true

path(1, 2). așteptat: true

path(2, 1). așteptat: false