Strategii de cautare in spatiul starilor

Strategii de cautare in spatiul starilor

Unul dintre cele mai utilizate modele de rezolvare a problemelor este prin reprezentarea cautarii sub forma unui graf orientat in care nodurile sunt stari succesive in rezolvare, iar arcele corespund tranzitiilor sau operatorilor legali ce pot fi aplicati pentru trecerea dintr-o stare in alta.

Cautarea solutiilor in spatiul starilor

Pentru a construi descrierea unei probleme rezolvate prin reprezentare in spatiul starilor trebuie parcurse urmatoarele etape:

Se defineste spatiul starilor care contine toate configuratiile posibile ale obiectelor relevante (si poate si unele imposibile). Spatiul se poate defini explicit prin indicarea tuturor starilor (acesta fiind un caz particular si rar intalnit in practica) sau implicit prin indicarea transformarilor care genereaza o noua stare dintr-o stare data.

Se specifica una sau mai multe stari din spatiu care descriu situatii posibile de la care poate porni procesul de rezolvare a problemei (starea initiala).

Se specifica una sau mai multe stari care ar fi acceptabile ca solutii ale problemei. Aceste stari se numesc stari scop (sau stari finale sau scopuri).

Se specifica un set de reguli care descriu actiunile (operatorii) disponibile si care definesc tranzitiile sau transformarile intre stari. In aceasta etapa trebuie analizate urmatoarele probleme:

Ce presupuneri nedeclarate explicit sunt prezente in descrierea informala a problemei?

Cat de generale trebuie sa fie regulile?

Cat de mult din calculul necesar rezolvarii problemei ar trebui facut inainte si reprezentat in reguli?

Problema poate fi rezolvata apoi utilizand o strategie de control adecvata, pentru a parcurge o parte din spatiul starilor (eventual tot) pana cand este gasita o cale de la o stare initiala la o stare finala, in cazul in care problema admite solutie. Cautarea este un mecanism general care poate fi utilizat atunci cand o metoda directa (determinista) de rezolvare a problemei nu este cunoscuta In acelasi timp, ea ofera cadrul in care pot fi incapsulate metode mai directe de rezolvare a anumitor parti ale problemei (subproblemelor).

Cautare prin backtracking

Rezolvarea unei probleme folosind strategia de backtracking a fost expusa in capitolul 6. In continuare se prezinta schema generala a unei astfel de cautari care poate fi aplicata pentru orice descriere a unei subprobleme in termeni de stari initiale, stari finale si operatori sau tranzitii intre stari. Pentru ilustrare, se defineste explicit un spatiu de cautare finit, ipotetic, prin definirea predicatului succesor(stare, stare_urmatoare). O definire a predicatului succesor specifica unei probleme particulare cuplata cu schema generala de rezolvare prin backtracking ce este prezentata in continuare rezolva problema.

% Graful care descrie spatiul de cautare complet.

succesor(a,b).  % a stare initiala

succesor(b,c).

succesor(c,d).

succesor(d,g).

succesor(a,e).

succesor(e,f).

succesor(f,g).

final(g).  % g stare finala

% rez(+Stare, -Sol)

rez(Stare, Sol) :- bkt(Stare, [], Sol).

bkt(Stare, Drum, [Stare | Drum]) :- final(Stare).

bkt(Stare, Drum, Sol) :-

succesor(Stare, N1), not(member(N1, Drum)),

bkt(N1, [Stare | Drum], Sol).

rez(a,Sol).

Sol=[g,d,c,b,a];

Sol=[g,f,e,a];

No

Cautarea prin backtracking poate fi cuplata cu impunerea unei adancimi maxime de cautare, necesara in special in cazul spatiilor de cautare infinite in care solutia poate sa nu se afle pe ramura curenta pe care a inceput cautarea. Stabilirea unei adancimi maxime de cautare se poate face astfel:

% rez1(Stare, Sol) impune adancimea maxima Max = 10

rez1(Stare, Sol) :- bkt1(Stare, Sol, 10).

bkt1(Stare, [Stare], _ ) :- final(Stare).

bkt1(Stare, [Stare | Sol], Max) :-

Max > 0, succesor(Stare, N1),

Max1 is Max-1, bkt1(N1, Sol, Max1).

In acest caz, s-a eliminat testul de stari anterior parcurse deoarece, existand o adancime maxima de cautare se elimina buclele, dar cu penalizarea eventuala a reparcurgerii unor stari. Exercitiul propus 1 al acestui capitol va cere o combinare a acestor doua solutii.

3 Cautare pe nivel si in adancime

Pentru implementarea acestor doua strategii de cautare de baza se folosesc doua liste: lista OPEN a nodurilor explorate in cautare (sau FRONTIERA portiunii cunoscute a spatiului de cautare la un moment dat cu partea necunoscuta inca a acestui spatiu) si lista CLOSED a nodurilor expandate (sau TERITORIUL portiunii cunoscute din spatiul de cautare). Pentru a putea obtine calea de la starea initiala la starea finala, odata ce s-a gasit starea finala, ambele liste vor contine perechi [Stare, Predecesor], unde Predecesor este starea predecesoare a starii Stare. Pentru starea initiala se va introduce in OPEN perechea [StareInitiala, nil], cu nil o constanta arbitrar fixata.

Implementarea foloseste doua tipuri de date, stiva si coada, pentru exploatarea listei OPEN, respectiv stiva in cazul cautarii in adancime si coada in cazul cautarii pe nivel. Definirea operatiilor tipice asociate acestor structuri de date abstracte in Prolog este pusa in evidenta de implementarea ce urmeaza.

% Cautare pe nivel si in adancime

% Se folosesc tipurile de date abstracte Stack and Queue.

% TDA Stack

% emptys(+S) - testeaza daca stiva este vida

% emptys(-S) - initializeaza stiva

emptyst([]).

% stack(-Top, -SNou, +S) - are efect de pop

% stack(+Top, +S, -SNoua) - are efect de push

% stack(-Top, _, +S) - are efect de top

stack(Top, Stack, [Top | Stack]).

% TDA Queue

% empty(+Q) - testeaza daca coada este vida

% empty(-Q) - initializeaza coada

emptyq([]).

% enqueue(+El, +Q, -QNoua) introduce un element in coada

enqueue(El, [], [El]).

enqueue(El, [X | Rest], [X | R1]) :- enqueue(El, Rest, R1).

% dequeue(-El, +Q, -QNoua) elimina un element din coada

dequeue(El, [El | R], R).

% Spatiul de cautare

succesor(a, b). succesor(b, c). succesor(c, d). succesor(d, g).

succesor(a, e). succesor(e, f). succesor(f, g).

final(g).

% Rezolvare cu parcurgere pe nivel

% rezbreadth(+StareInitiala)

rezbreadth(Si) :-

emptyq(Open), emptyq(Closed), enqueue([Si, nil], Open, Open1),

breadth(Open1, Closed).

breadth(Open, _) :- emptyq(Open), !, write('Nu exista solutie'), nl.

breadth(Open, Closed) :-

dequeue([Stare | Predec], Open, _), final(Stare),

write('S-a gasit o solutie'), nl, scriecale([Stare | Predec], Closed).

breadth(Open, Closed) :-

dequeue([Stare, Pred], Open, RestOpen),

enqueue([Stare, Pred], Closed, Closed1),

listsucc(Stare, RestOpen, Closed1, LSucc),

append(RestOpen, LSucc, Open1),

breadth(Open1, Closed1).

listsucc(Stare, RestOpen, Closed, LSucc) :-

bagof([S, Stare], (succesor(Stare, S), not (member([S,_], RestOpen)),

not(member([S, _], Closed) ) ), LSucc).

listsucc(Stare, RestOpen, Closed, []).

% Rezolvare cu parcurgere in adancime

% rezdepth(+StareInitiala)

rezdepth(Si) :-

emptyst(Open), emptyst(Closed), stack([Si, nil], Open, Open1),

depth(Open1, Closed).

depth(Open, _) :- emptyst(Open), write('Nu exista solutie'), nl.

depth(Open, Closed) :-

stack([Stare | Predec], RestOpen, Open), final(Stare),

write('S-a gasit o solutie'), nl, scriecale([Stare | Predec], Closed).

depth(Open, Closed) :-

stack([Stare, Pred], RestOpen, Open),

stack([Stare, Pred], Closed, Closed1),

listsucc(Stare, RestOpen, Closed1, LSucc),

append(LSucc, RestOpen, Open1),

depth(Open1, Closed1).

% Afiseaza calea de la Si la Sf

% scriecale(+Cale, +Closed)

scriecale([S, nil], _) :- scrie(S), nl.

scriecale([S, Predec], Closed) :-

member([Predec, P], Closed), scriecale([Predec, P], Closed),

scrie(S), nl.

scrie(S) :- write(S).

rezbreadth(a).

a

e

f

g

rezdepth(a).

a

b

c

d

g

Strategia de cautare pe nivel este o strategie completa care, in plus, gaseste calea de la starea initiala la starea finala cu numarul minim de tranzitii de stari. Strategia de cautare in adancime nu este completa pentru orice spatii de cautare, dar consuma mai putina memorie decat cea de cautare pe nivel.

Pentru a pune in evidenta diferenta dintre strategia de cautare in adancime si cea de backtracking, se va rescrie schema generala de backtracking din sectiunea precedenta pe acelasi sablon cu cel de la strategiile precedente.

rezbkt(Si) :- emptyst(Open), stack(Si, Open, NewOpen), bkt(NewOpen).

bkt(Open) :-

stack(S, _, Open), final(S), write('S-a gasit o solutie'), afis(Open).

bkt(Open) :-

stack(S, _, Open), succesor(S, S1), not(member(S1, Open) ),

stack(S1, Open, NewOpen), bkt(NewOpen).

afis([]) :- nl.

afis([S | Rest]) :- afis(Rest), scrie(S).

Se observa ca, deoarece strategia de backtracking pastreaza numai starile de pe calea curenta de cautare si face testul pentru stari anterior parcurse numai pe aceasta cale, este suficienta mentinerea numai a listei OPEN. In plus, aceasta lista nu mai trebuie sa fie o lista de perechi [Stare, Predecesor] ci numai o lista de stari parcurse, la detectia starii finale continutul lui OPEN fiind chiar calea spre solutie. Implementarea de mai sus este echivalenta cu cea din sectiunea precedenta. Predicatul afis permite afisarea starilor parcurse in ordinea de la starea initiala la cea finala.

Algoritmul A*

A* este un algoritm de cautare in spatiul starilor a solutiei de cost minim (solutia optima) ce utilizeaza o functie euristica de estimare a distantei starii curent parcurse fata de starea finala. Pe parcursul cautarii, starile sunt considerate in ordinea crescatoare a valorii functiei f(S)=g(S)+h(S), unde g(S) este functia de cost a portiunii parcurse pana in starea S, iar h(S) este functia euristica de estimare a distantei din S la starea finala. Functia euristica trebuie sa fie admisibila (mai mica sau cel mult egala cu distanta reala) pentru a garanta optimalitatea solutiei. Desi are o complexitate timp tot exponentiala, ca orice procedura de cautare, algoritmul este mai eficient, in general, decat stategiile neinformate datorita componentei euristice care ghideaza cautarea.

Trebuie observat ca algoritmul A* poate fi aplicat si in cazul in care intr-o problema nu exista costuri, considerand implicit toate costurile tranzitiilor de stari egale cu 1. In acest caz, rezultatele algoritmului sunt similare cu cele ale parcurgerii pe nivel, in sensul gasirii drumului de la starea initiala la starea finala cu un numar minim de tranzitii de stari, dar cautarea este, in general, mai rapida. Programul Prolog ce urmeaza presupune, implicit, costurile tranzitiilor de stari egale cu 1.

Implementarea algoritmului A* se va face pe baza schemelor anterioare de cautare, cu urmatoarele modificari. In loc de a exploata lista OPEN ca o stiva sau ca o coada, aceasta lista va fi tratata ca o lista de prioritati in functie de f(S). Fiecarei tranzitii de stari i se va asocia un cost, in functie de problema, si fiecarei stari i se va asocia o valoare pentru functia euristica h(S). Lista OPEN va fi o lista de liste de patru elemente de forma [Stare, Predecesor, G, H, F].

% Spatiul de cautare

succesor(a, b). succesor(b, c). succesor(c, d). succesor(d, g).

succesor(a, e). succesor(e, f). succesor(f, g).

final(g).

% Valorile functiei euristice folosite in algoritmul A*

euristic(a, g, 3).

euristic(b, g, 3).

euristic(c, g, 2).

euristic(d, g, 1).

euristic(g, g, 0).

euristic(e, g, 2).

euristic(f, g, 1).

euristic(_, _, 0).

% Coada de prioritati (coada este sortata crescator in functie de cheia F1)

inspq(El, [], [El]).

inspq(El, [X | Rest], [El, X | Rest]) :- precedes(El, X), !.

inspq(El, [X | Rest], [X | R1]) :- inspq(El, Rest, R1).

precedes([_, _, _, _, F1], [_, _, _, _, F2]) :- F1<F2.

rezastar(Si, Scop) :-

emptyq(Open), emptyq(Closed),

euristic(Si, Scop, H),

inspq([Si, nil, 0, H, H], Open, Open1),

astar(Open1, Closed, Scop).

astar(Open, _, _) :- emptyq(Open), !, write('Nu exista solutie'), nl.

astar(Open, Closed, Scop) :-

dequeue([S, Pred, _, _, _], Open, _),

S=Scop,

write('S-a gasit o solutie'), nl,

scriecale1([S, Pred, _, _, _], Closed).

astar(Open, Closed, Scop) :-

dequeue([S, Pred, G, H, F], Open, RestOpen),

inspq([S, Pred, G, H, F], Closed, Closed1),

(bagof([Urmator, H1], (succesor(S, Urmator),

euristic(Urmator, Scop, H1)), LSucc),!, G1 is G+1,

actual_toti(S, G1, LSucc, RestOpen, Closed1, OpenR, ClosedR);

OpenR=RestOpen, ClosedR=Closed1),

astar(OpenR, ClosedR, Scop).

actual_toti(_, _, [], Open, Closed, Open, Closed) :- !.

actual_toti(Stare, G, [[S, H] | Rest], Open, Closed, OpenR, ClosedR) :-

actual(Stare, G, [S, H], Open, Closed, Open1, Closed1),

actual_toti(Stare, G, Rest, Open1, Closed1, OpenR, ClosedR).

actual(Stare, G, [S, H], Open, Closed, OpenR, Closed) :-

member([S, Pred, G1, _, _], Open), !,

(G1=<G, OpenR=Open, !;

F is G+H,

elim([S, Pred, G1, _, _], Open, Open1),

inspq([S, Stare, G, H, F], Open1, OpenR)).

actual(Stare, G, [S, H], Open, Closed, OpenR, ClosedR) :-

member([S, Pred, G1, _, _], Closed), !,

(G1=<G, ClosedR=Closed, OpenR=Open, !;

F is G+H,

elim([S, Pred, G1, _, _], Closed, ClosedR),

inspq([S, Stare, G, H, F], Open, OpenR)).

actual(Stare, G, [S, H], Open, Closed, OpenR, Closed) :-

F is G+H,

inspq([S, Stare, G, H, F], Open, OpenR).

scriecale1([S, nil, _, _, _], _) :- scrie(S), nl.

scriecale1([S, Pred, _, _, _], Closed) :-

member([Pred, P, _, _, _], Closed),

scriecale1([Pred, P, _, _, _], Closed), scrie(S), nl.

scrie(S) :- write(S).

elim(_, [], []).

elim(X, [X | Rest], Rest) :- !

elim(X, [Y | Rest], [Y | Rest1]) :- elim(X, Rest, Rest1).

rezastar(a, g).

a

e

f

g

Exercitii propuse

EP1. Sa se rescrie schema de cautare cu backtracking combinand varianta care memoreaza lista starilor parcurse cu cea care impune o adancime maxima de cautare.

EP2. Adancimea maxima de cautare trebuie impusa, in anumite cazuri (spatii de cautare infinite) si pentru cautarea in adancime. Sa se modifice schema cautarii in adancime prin includerea unei adancimi maxime de cautare.

EP3. Strategiile de cautare backtracking, in adancime si pe nivel prezentate determina prima solutie, in cazul in care problema admite solutie. Sa se modifice programele corespunzatoare acestor strategii astfel incat sa determine si sa afiseze toate solutiile problemei, daca problema admite mai multe solutii.

EP4. Sa se modifice algoritmul A* din sectiunea 4 prin adaugarea unui cost explicit, diferit de 1, tranzitiilor de stari.