Inteligenta Artificiala

Nu esti logat.

(Deadline: 04.06.2017 23:59:59)

Daca nu sunteti logati exercitiile nu se mai afiseaza.

Reprezentarea diverselor structuri de date in prolog

Adesea in cadrul anumitor algoritmi avem nevoie sa reprezentam anumite structuri de date, de exemplu: stive, cozi, grafuri, arbori etc. Dupa cum s-a observat, in Prolog exista o multitudine de moduri in care poate fi reprezentata aceeasi informatie. Mai jos aveti doar niste idei de reprezentare care pot fi folosite intr-o mare parte din cazuri, insa nu e obligatoriu, de fapt nici macar indicat sa folositi mereu aceste moduri de reprezentare, felul in care va definiti structura bazei de cunostinte depinzand foarte mult de problema particulara pe care o rezolvati.

Stive si cozi

Reprezentarea cea mai intuitiva a stivelor si cozilor este prin liste. In cazul stivelor, in mod optim baza stivei e la ultimul element si varful stivei la primul, deoarece stiva se modifica doar de la varf, iar in cazul listelor accesul cel mai usor si rapid se face la primul element. In cazul cozilor deoarece avem de realizat modificari in ambele capete (adaugare respectiv stergere de elemente), se pot alege pentru inceputul si sfarsitul cozii atat inceputul si respectiv sfarsitul listei, cat si invers.

Grafuri

Un graf este definit prin multimea de noduri si cea de muchii (sau arce in cazul grafurilor orientate), deci o metoda de reprezentare este cea in care alegem un predicat pentru noduri si unul pentru muchii(arce). De exemplu pentru graful orientat:

nod(1).
nod(2).
nod(3).
nod(4).
nod(5).
nod(6).
nod(7).

muchie(2,3).
muchie(3,4).
muchie(4,5).
muchie(4,6).
muchie(5,6).
Observati ca daca am fi reprezentat graful doar prin muchii (considerand ca multimea nodurilor o puteam obtine facand reuniunea a ceea ce gaseam in primul respectiv in al doilea parametru al predicatului muchie) nu am fi prins in reprezentare si nodurile izolate. Bineinteles se pot folosi si variatii ale aceste reprezentari, de exemplu nodurile si muchiiile sa fie puse intr-o lista de noduri, respectiv de muchii.
Bineinteles predicatele nod si muchie pot fi modificate dupa situatie in caz ca trebuie sa cuprinda si informatii aditionale, de exemplu o forma de reprezentare ar fi:
nod(identificator_nod, informatie).
muchie(capat1,capat2, informatie).

De asemenea, daca avem mai multe grafuri care trebuie memorate in baza de cunostinte putem considera inca un parametru pentru cele doua predicate, si anume, numele grafului:
nod(nume_graf, identificator_nod, informatie).
muchie(nume_graf, capat1,capat2, informatie).

Raman valabile si celelalte reprezentari clasice ale grafurilor precum matricea de adiacenta, sau listele de adiacenta etc.

Atentie la grafuri orientate si neorientate. In descrierea facuta mai sus se presupune ca daca avem muchie(X,Y) avem un arc care porneste din nodul X si are sageata in nodul Y.

Consideram ca dorim sa reprezentam graful neorientat din imagine (observati ca e graful neorientat obtinut din graful de mai sus prin transfomarea arcelor in muchii):

In acest caz daca avem predicatul muchie(X,Y) valid pentru o pereche de noduri atunci trebuie sa fie adevarat si pentru perechea inversata.
O varianta ar fi sa dublam fiecare muchie, adaugand la baza de cunostinte faptul cu perechea de noduri inversata. O alta varianta mai utila in cazul in care vrem sa scriem mai putin este sa definim o regula pentru muchiile grafului neorientat cu ajutorul predicatului muchie_n:

muchie_n(X,Y):-muchie(X,Y);muchie(Y,X).

Arbori

In primul rand arborii sunt si ei grafuri, deci se pot reprezenta ca un graf, totusi avand in vedere ca reprezinta structuri cu proprietati speciale putem imbunatati modul de reprezentare.

In cazul arborilor binari, fiecare nod are cel mult doi fii. prin urmare putem considera o structura arb(radacina, fiu_stang, fiu_drept). In cadrul lui fiu_stang si fiu_drept putem pune doar un nume de nod, urmand ca alte doua structuri arb sa descrie si acele noduri cu pricina. O alta varianta e ca fiu_stang si fiu_drept sa reprezinte ele insusi structuri arb. Apare o problema in cazul in care avem noduri cu un singur fiu sau fara niciun fiu, in cazul acestora ne-a trebui un termen care sa denote un fiu nul, sai zicem chiar null (bineinteles in acest caz null nu va avea voie sa reprezinte identificatorul efectiv al vreunui nod din arbore). Sa luam ca exemplu arborele binar:

Daca reprezentam fiii ca nume de noduri atunci avem:

arb(1,2,3).
arb(2,4,null).
arb(3,5,6).
arb(4,null,null).
arb(5,7,8).
arb(6,null,null).
arb(7,null,null).
arb(8,null,null).
Daca reprezentam fiii ca subarbori atunci avem o singura structura arb pentru un arbore.
arb(
  1,
  arb(
    2,
    arb(4,null,null),
    null
  ),
  arb(
    3,
    arb(
      5,
      arb(7,null,null),
      arb(8,null,null)
    ),
    arb(6,null,null)
  )
)

Pentru a evita sa scriem structura arborelui in consola, la interogare, vom folosi in exercitii un predicat binar de forma arbore_bin(+NumeArbore,-Arbore) care salveaza in baza de cunostinte reprezentarea arborelui dorit. Un exemplu aveti in codul de mai jos in care e definit si un predicat care afiseaza arborele binar:

arbore_bin(a1,
    arb(
      1,
      arb(
        2,
        arb(4,null,null),
        null
      ),
      arb(
        3,
        arb(
          5,
          arb(7,null,null),
          arb(8,null,null)
        ),
        arb(6,null,null)
      )
    )
).



%predicatul principal %primeste un nume de arbore salvat in baza de cunostinte in predicatul arbore_bin si il afiseaza indentat pe nivele %afis_arb_bin(+NumeArbore)
afis_arb_bin(NumeArbore):-arbore_bin(NumeArbore,Arbore),afis_arb_bin_aux(0,Arbore).

%afis_arb_bin_aux(+Nivel,+Structura_arb) %afiseaza un subarbore indentat cu un numar de spatii egal cu Nivel afis_arb_bin_aux(_, null).
afis_arb_bin_aux(Niv, arb(R,Fs,Fd)):- tab(Niv), write(R), nl, Niv1 is Niv+1, afis_arb_bin_aux(Niv1, Fs), afis_arb_bin_aux(Niv1, Fd).

%tab(+N)
%afiseaza N spatii
tab(N):-N>0,N1 is N-1, write(' '),tab(N1).
tab(0).
Va afisa: | ?- afis_arb_bin(a1).
1
2
  4
3
  5
   7
   8
  6
yes
| ?-

In cazul arborilor oarecare problema e ca avem mai multi fii si daca i-am pune pe fiecare ca parametru al unei structuri arb pe caz general am avea in cazul fiecarui subarbore o structura cu numar diferit de elemente. Apare problema in program ca nu stim cu cati parametri trebuie sa chemam o structura arb. In acest caz cea mai naturala solutie e sa punem fiii unui nod intr-o lista. Structura arb ar avea acum forma: arb(radacina, lista_fii). Din nou putem avea cazul in care fiii sunt reprezentati ca nume de noduri, caz in care vom avea in baza de cunostinte pentru fiecare fiu in parte o alta structura arb (asemanator cu primul exemplu de la arborele binar). Sau putem reprezenta fiii ca subarbori, avand pentru un arbore o singura structura arb.

Putem considera drept exemplu urmatorul arbore:

In cazul in care fiii sunt reprezentati doar prin numele nodurilor, definirea arborelui va arata in felul urmator:

arb(1, [2, 3, 4, 5]).
arb(2, [6, 7, 8]).
arb(3, [9]).
arb(4, []).
arb(5, [10, 11]).
arb(6, []).
arb(7, []).
arb(8, []).
arb(9, []).
arb(10, []).
arb(11, []).
Observati ca in cazul frunzelor, lista de fii este bineinteles o lista vida.

Daca reprezentam fiii drept subarbori:

arb(1, [
  arb(2, [
    arb(6, []),
    arb(7, []),
    arb(8, [])
  ]),
  arb(3, [
    arb(9, [])
  ]),
  arb(4, []),
  arb(5, [
    arb(10, []),
    arb(11, [])
  ])
]).

Observatie: In cazul in care avem mai multi arbori si dorim sa le dam un nume, ca si in cazul general al grafurilor, putem sa mai adaugam un parametru la structura arb care sa contina numele arborelui.

Observatie: Putem opta pentru variatii ale modului de reprezentare de mai sus, in functie de problema de rezolvat, de exemplu:

Nu avem neaparat o forma optima pentru orice problema.

Observatie: Metoda de reprezentare in care tot arborele este continut de o singura structura (cea in care fiii sunt reprezentati ca subarbori) are avantajul ca putem sa o trimitem ca parametru unui predicat, avand astfel in acel parametru intreg arborele. Aceasta metoda de reprezentare e recomandata cand arborele e un parametru auxiliar, construit in cadrul vreunui algoritm si nu o data de intrare ori de iesire in sine, fiindca astfel nu mai trebuie neaparat memorat in baza de cunostinte. In cazul in care e desfasurat pe mai multe structuri arb acestea trebuie memorate in baza de cunostinte printr-un predicat (adesea dinamic, ca sa permita modificarea arborelui), ori, daca nu, macar grupate in vreo lista transmisa ca parametru in predicatele programului.

Mai jos avem un exemplu de predicat de afisare a arborilor oarecare, asemanator cu cel de la arborii binari:

arbore_oarecare(a1,
    arb(1, [
      arb(2, [
        arb(6, []),
        arb(7, []),
        arb(8, [])
      ]),
      arb(3, [
        arb(9, [])
      ]),
      arb(4, []),
      arb(5, [
        arb(10, []),
        arb(11, [])
      ])
    ])
).


%predicatul principal
%primeste un nume de arbore salvat in baza de cunostinte in predicatul arbore_oarecare si il afiseaza indentat pe nivele
%afis_arb_oarecare(+NumeArbore)
afis_arb_oarecare(NumeArbore):-arbore_oarecare(NumeArbore,Arbore),afis_arb_o_aux(0,Arbore).

%afis_arb_o_aux(+Nivel,+Structura_arb)
%afiseaza un subarbore indentat cu un numar de spatii egal cu Nivel
afis_arb_o_aux(Niv, arb(R,[])):-tab(Niv), write(R), nl.
afis_arb_o_aux(Niv, arb(R,Fii)):- tab(Niv), write(R), nl, Niv1 is Niv+1, afis_arb_frati(Niv1, Fii).
afis_arb_frati(Niv, [Fiu|T]):-  afis_arb_o_aux(Niv, Fiu), afis_arb_frati(Niv, T).
afis_arb_frati(_,[]).

%tab(+N)
%afiseaza N spatii
tab(N):-N>0,N1 is N-1, write(' '),tab(N1).
tab(0).

Cu outputul:

| ?- afis_arb_oarecare(a1).
1
 2
  6
  7
  8
3
  9
4
5
  10
  11
yes
| ?-