Unificare și Backtracking

Capitolul de faţă cuprinde 4 secţiuni mari. În prima secţiune se prezintă în detaliu ceea ce face Prolog atunci când încearcă să găsească o potrivire pt. un goal (obiectiv) cu o clauză (din secţiunea clauses). Acest proces de căutare poartă denumirea de unificare, ceea ce presupune găsirea unei potriviri între structurile de date utilizate în apelul obiectivului şi cele din clauzele date. În Prolog, unificarea implementează câteva dintre procedeele cunoscute din alte limbaje de programare cum ar fi: atribuirea, transmiterea parametrilor unei proceduri, selecţie case, construcţia unor structuri de date, etc.

În partea a doua se prezintă modul în care Prolog caută soluţiile (prin backtracking).

În partea a treia se va introduce un predicat care poate fi utilizat pentru a optimiza căutarea prin backtracking.

Pentru a clarifica şi mai bine, în cea de-a patra parte în acest capitol se vor relua noţiunile mai importante prezentate dar dintr-o perspectivă procedurală.

Unificare

Se consideră următorul obiectiv:

scrisă_de(X, Y).

Când Visual Prolog încearcă să satisfacă acest obiectiv, trebuie testată fiecare „clauză” „scrisa_de” din program. Programul va căuta o potrivire de la începutul programului şi până la sfârşit. Când o „clauză” se potriveşte cu un obiectiv, Prolog caută să atribuie valori pentru variabilele libere astfel încât clauza şi obiectivul să fie identice. Se spune că obiectivul se „unifică” cu clauza.

Exemplu:

DOMAINS

titlu, autor = symbol

pagini = unsigned

PREDICATES

carte(titlu, pagini)

nondeterm scrisa_de(autor, titlu)

nondeterm roman(titlu)

CLAUSES

scrisă_de(sadoveanu, „Neamul Soimarestilor”).

scrisă_de(creanga, „Amintiri din copilarie”).

carte(„Neamul Soimarestilor”, 300).

carte(„Amintiri din copilarie”, 100).

roman(Titlu):-

scrisa_de(_, Titlu), carte(Titlu, Lungime), Lungime >=250.

În timp ce X şi Y sunt variabile libere în obiectiv, şi o variabilă liberă poate fi unificată cu orice argument (chiar cu alte variabile libere), obiectivul poate fi unificat cu prima regulă „scrisa_de” din program:

scrisa_de( X , Y).

| |

scrisa_de(sadoveanu, „Neamul Soimarestilor”).

Visual Prolog va găsi o potrivire X va fi creanga şi Y va deveni „Neamul Soimarestilor”. În acest moment se vor afisa:

X=sadoveanu, Y=Neamul Soimarestilor

Visual Prolog va căuta în continuare şi alte potriviri, efectuând şi alte unificări dacă sunt posibile, în cazul de faţă va găsi o nouă soluţie:

X=creanga, Y=Amintiri din copilarie

2 Solutions

Dacă, se cere programului soluţionarea următorului obiectiv:

scrisa_de(X, “Amintiri din copilarie”).

Prolog va încerca o potrivire cu prima clauză a predicatului scrisa_de:

scrisa_de( X , “Amintiri din copilarie”).

| |

scrisă_de(sadoveanu, „Neamul Soimarestilor”).

Deoarece “Amintiri din copilarie” şi “Neamul Soimarestilor” nu se pot unifica (nu se potrivesc, nu sunt identice) , procesul de unificare se încheie cu eşec. Visual Prolog va încerca următorul fapt din program:

scrisă_de(creanga, „Amintiri din copilarie”).

Care va conduce la unificarea variabilei X cu creanga, variabila X devenind astfel o variabilă legată.

Vom considera în continuare următorul goal (obiectiv):

roman(X).

Visual Prolog va încerca să îndeplinească un obiectiv, prin investigarea antetului regulii respective.

În acest caz se va găsi următoarea potrivire:

roman(Titlu).

În continuare Prolog va încerca să unifice argumentele clauzei pentru regula roman. Deoarece, în cadul acestui obiectiv, variabila X este o variabilă liberă, ea va putea fi unificată cu orice argument. Argumentul Titlu, de asemenea este o variabilă nelegată în antetul clauzei roman. În continuare Visual Prolog va încerca să satisfacă secvenţial, pe rând subobiectivele acestei reguli.

roman(Titlu):-

scrisa_de(_, Titlu),

carte(Titlu, Lungime),

Lungime >=250.

Primul subobiectiv care va fi încercat este scrisa_de(_, Titlu), în care autorul cărţii nu este important şi s-a utilizat ca prim argument o variabilă anonimă pt. a-l substitui. Prolog va căuta o potrivire de la început către sfârşit prin examinarea tuturor faptelor existente în program. Se va face o unificare cu primul fapt, scrisa_de după cum urmează:

scrisa_de( _ , Titlu),

| |

scrisa_de(sadoveanu,"Neamul Soimarestilor").

Variabila Titlu devine o variabilă legată cu valoarea “Neamul Soimarestilor” şi următorul subobiectiv va fi carte(Titlu, Lungime). Visual Prolog va încerca să caute în continuare o potrivire pentru carte. Deoarece Titlu este o variabilă legată în acest moment datorită primului subobiectiv cu “Neamul Soimarestilor”, se va încerca acum unificarea variabilei Lungime rămasă încă nelegată prin căutare în lista de fapte ale programului de la început spre sfârşit. Prima încercare de potrivire cu clauza carte(“Neamul Soimarestilor”, 300) se va solda cu o potrivire între variabila Lungime şi 300, ea devenind în continuare variabilă legată. Cel de-al treilea subobiectiv care se va testa va fi Lungime>=250, care este de fapt o condiţie. Această condiţie este adevarată, deci întregul obiectiv se va încheia succes.

Prolog va afişa soluţia:

X=Neamul Soimarestilor

1 Solution

Prezentat in cadrul Facultatii de Ingierie Hunedoara - UPT