z7z12zc
Acest capitol trateaza metode de rezolvare a problemelor in inteligenta artificiala si strategiile de control posibil de utilizat. Discutia se orienteaza in special spre modul de reprezentare a solutiei problemei si a procesului de rezolvare pe baza unor algoritmi de cautare a solutiei. Metodele prezentate reprezinta modalitati general valabile de rezolvare a problemelor. Aceste metode se aplica pentru orice model particular de reprezentare a cunostintelor, deci pentru orice fel de codificare simbolica a bazei de cunostinte aBarr,s.a.,1982;Nilsson,1980;Pearl,1984i. Reprezentarea cunostintelor si modalitatile specifice de utilizare a metodelor generale in rezolvarea problemelor reprezinta subiectul Partii a II-a a acestui text.
2.1 Reprezentarea solutiei problemei
Orice activitate de rezolvare a problemelor poate fi vazuta ca un proces de identificare sau de construire a unui obiect cu anumite caracteristici, obiect ce reprezinta solutia problemei. Exista trei cerinte minimale ale oricarei activitati de rezolvare a problemelor cu ajutorul calculatorului:
(1) O structura simbolica care sa poata reprezenta descrierea initiala a problemei si fiecare obiect candidat la solutie.
(2) O multime de instrumente computationale capabile sa transforme descrierea unui obiect (structura simbolica) intr-o noua descriere in scopul de a investiga sistematic toti candidatii la solutie.
(3) O metoda de planificare efectiva care sa indice ordinea de aplicare a transformarilor astfel incit solutia problemei sa fie gasita cit mai repede.
In terminologia inteligentei artificiale, aceste trei componente ale unui sistem de rezolvare a problemelor se numesc:
* Baza de date sau baza de cunostinte
* Operatorii de transformare sau regulile de productie
* Strategia de control
2.1.1 Spatii de cautare
Descrierea initiala a problemei si a obiectelor candidate la solutie obtinute pe parcursul rezolvarii, deci structurile simbolice care specifica universul problemei, pot fi asimilate cu o multime de stari. Multimea de operatori (reguli) de transformare indica modul de transformare a universului problemei dintr-o stare initiala intr-o stare finala. Starea initiala descrie conditiile initiale ale problemei iar starea finala reprezinta solutia problemei. Starea finala poate fi definita explicit, prin descrierea solutiei, sau implicit, printr-o multime de conditii pe care o stare trebuie sa le satisfaca pentru a fi stare finala, adica solutie a problemei. Rezolvarea problemei poate cere fie determinarea starii finale, fie stabilirea intregului drum de la starea initiala la starea finala. Multimea starilor investigate pina in momentul ajungerii in starea finala formeaza spatiul de cautare a solutiei problemei.

De exemplu, problema celor 8 regine cere sa se gaseasca o amplasare a opt regine pe o tabla de sah astfel incit nici o regina sa nu poata ataca alta regina. Acest lucru este echivalent cu cerinta ca nici o linie, coloana sau diagonala de pe tabla de sah sa nu contina mai mult de o regina. Starea initiala a problemei este descrisa de configuratia initiala a tablei de sah in care nici o regina nu este plasata pe tabla, obiectele candidate la solutie sint reprezentate prin tabla de sah pe care s-au plasat o parte sau toate reginele, iar starea finala este plasarea tuturor reginelor pe tabla, cu respectarea restrictiilor impuse. In acest caz starea finala este descrisa (implicit) printr-un set de conditii iar solutia problemei consta in determinarea acestei stari finale. Multimea de reguli de transformare este reprezentata de actiunile de plasare a unei regine intr-un patrat al tablei de sah.
Problemele de inteligenta artificiala sint, asa cum s-a mai spus, probleme grele, deci complex computationale. De cele mai multe ori obtinerea solutiei se face printr-un proces de cautare si nu prin aplicarea unei secvente de transformari anterior specificata. Ideea de baza a rezolvarii unor astfel de probleme poate fi descrisa, nedeterminist, prin urmatorul algoritm.
Algoritm: Rezolvarea unei probleme prin cautare
1. Stabileste starea initiala Si
2.
3. repeta
3.1 Selecteaza o regula de transformare T posibil de aplicat starii curente S
3.2 Aplica T asupra starii S si obtine starea S'
3.3 pina S este stare finala sfirsit.
Algoritmul de mai sus este nedeterminist deoarece pasul 3.1 nu specifica cum se selecteaza transformarea T de aplicat. Selectarea transformarilor si memorarea transformarilor efectuate constituie strategia de control. O strategie de control nu este doar o secventa de actiuni, ci o modalitate de descriere a selectiei unei actiuni ca raspuns la un eveniment extern, cum ar fi rezultatul unui test, rezultatul aplicarii unei proceduri complicate de calcul sau actiunea unui adversar. In plus, o strategie de control trebuie sa fie sistematica. Judea Pearl a1984i caracterizeaza plastic cele doua cerinte necesare unei strategii pentru a fi sistematica:
* Nu lasa nici o piatra neintoarsa.
* Nu intoarce nici o piatra de mai multe ori.
Prima cerinta, numita completitudine, garanteaza faptul ca strategia produce solutia, daca aceasta exista. Cea de a doua cerinta protejeaza contra ineficientei prelucrarilor repetate. Cele mai multe probleme de inteligenta artificiala necesita evaluarea unui numar mare de stari intermediare, deci obiecte candidate la solutie, pentru a determina solutia. Informatia disponibila nu permite selectia transformarii corecte in scopul rezolvarii problemei. Tocmai din acest motiv comportarea programelor de inteligenta artificiala poate fi caracterizata ca un proces de cautare in care diverse transformari aplicate universului problemei sint incercate pina se determina solutia problemei.
Informatia euristica joaca un rol foarte important in acest proces de cautare prin reducerea numarului de stari investigate pentru obtinerea solutiei. Se considera, de exemplu, jocul de sah pentru care este imposibila evaluarea tuturor starilor posibile ale spatiului de cautare al unei partide cistigatoare. Un maestru al sahului poate hotari ca o anumita miscare este mai potrivita deoarece aceasta miscare determina o configuratie a tablei de sah care "pare" mai promitatoare pentru cistig. Aceasta hotarire se bazeaza pe cunostintele lui despre jocul de sah si pe experienta, si este informatie euristica.
In cazul programelor de inteligenta artificiala informatiile euristice trebuie inglobate in strategia de control pentru a creste eficienta procesului de rezolvare a problemei. De obicei, acest tip de informatie este reprezentat printr-o functie euristica asociata fiecarei stari, functie care estimeaza cit de promitatoare este acea stare din punct de vedere al avansului spre solutie. Functiile euristice depind si se stabilesc pe baza cunostintelor specifice problemei sau clasei de probleme de rezolvat si au ca scop:
* ghidarea procesului de cautare a solutiei si
* evaluarea calitatii solutiei problemei.
De exemplu, in cazul problemei celor 8 regine, o euristica care poate fi utilizata este aceea de a plasa o regina astfel incit sa lase cel mai mare numar de patrate neatacate pe tabla de sah.
Specificarea unei strategii de cautare si a informatiei euristice utilizate trebuie sa stabileasca criterii pentru demonstrarea validitatii solutiei problemei si pentru evaluarea solutiei din punct de vedere al efortului depus in gasirea solutiei sau din punct de vedere al calitatii solutiei gasite.
2.1.2 Solutia problemei reprezentata prin spatiul starilor
Definitie. O reprezentare a solutiei problemei prin spatiul starilor este formata dintr-un triplet cu urmatoarea semnificatie:
* Si reprezinta multimea starilor initiale,
* O reprezinta multimea de operatori posibil de aplicat asupra starilor universului problemei pentru a ajunge in noi stari; in fiecare stare data, numai o parte din operatori sint legal aplicabili,
* Sf reprezinta multimea starilor finale sau stari scop. Multimea starilor finale poate contine si o singura stare.
In reprezentarea solutiei problemei prin spatiul starilor, spatiul de cautare are forma unui graf orientat in care nodurile sint identificate prin stari, iar arcele reprezinta aplicarea unor operatori pentru a transforma o stare in starea urmatoare. O solutie a problemei este o secventa de operatori care transforma starea initiala in stare finala si reprezinta o cale intre aceste doua stari in graf. Graful spatiului de cautare este specificat implicit de reprezentare prin tripletul . Pe parcursul avansului in cautare o portiune din acest graf devine explicita, portiunea din graful spatiului de cautare astfel construita reprezentind partea explorata a spatiului de cautare.
Fie jocul mozaicului de 8 numere, numit "8-puzzle", in care se cere ca, pornind de la o configuratie initiala specificata de pozitiile a opt numere si a unui patrat liber, sa se ajunga la o configuratie finala data, prin miscarea patratului liber in diverse directii, asa cum se arata in Figura 2.1. In acest caz, starea initiala este configuratia initiala (Figura 2.1(a)), starea finala, specificata explicit, este configuratia finala (Figura 2.1(b)), iar multimea de operatori este formata din urmatoarele reguli: muta patratul liber in sus cu o pozitie, muta patratul liber in jos cu o pozitie, muta patratul la dreapta cu o pozitie si muta patratul la stinga cu o pozitie (Figura 2.1(c)). Dintr-o anumita stare numai o submultime de operatori sint legal aplicabili. De exemplu, din starea initiala Si numai trei operatori pot fi aplicati: STINGA, JOS si DREAPTA, asa cum se arata in Figura 2.1(d); operatorul SUS nu poate fi aplicat in starea Si deoarece patratul liber este la marginea de sus a mozaicului. Prin aplicarea celor trei operatori starii initiale se pot obtine trei stari intermediare posibile: S1, S2, S3.
Pentru mozaicul de 8 numere se pot specifica diverse functii euristice care ghideaza procesul de cautare a solutiei si reduc numarul de stari generate. La un moment dat, se va alege starea care are asociata cea mai mica valoare a functiei euristice definite. Daca functia euristica este corespunzatoare se poate reduce in acest fel portiunea explicitata a grafului spatiului de cautare specificat implicit. Un exemplu de astfel de functie euristica este: unde

Figura 2.1 Reprezentare prin spatiul starilor a problemei mozaicului de 8 numere
O problema cunoscuta si dificila, deci NP-completa, este problema comis-voiajorului aNilsson,1980;Pearl,1984;Sedgewick,1990i. Fiind date un numar de orase si distantele de-a lungul unor drumuri care leaga aceste orase, se cere sa se gaseasca drumul de lungime minima pe care il face un comis-voiajor care trebuie sa treaca prin toate orasele pornind dintr-un oras dat si revenind in orasul de plecare. Un posibil exemplu este cel descris in Figura 2.2(a). Starea initiala a problemei este orasul de plecare al comis-voiajorului. Starile intermediare sint orasele prin care a trecut comis-voiajorul, iar solutia problemei este secventa de stari parcurse din starea initiala pina in starea finala, secventa care trebuie sa indeplineasca conditia de cost optim, i.e. drum de lungime minima. O parte din graful spatiului de cautare este prezentat in Figura 2.2(b).

Figura 2.2 Reprezentarea prin spatiul starilor a problemei comis-voiajorului
Enumerarea tuturor traseelor posibile si compararea costurilor asociate pentru a gasi traseul optim este un proces neeficient computational, mai ales in cazul unui numar mare de orase. Pentru a reduce timpul de calcul se poate utiliza o functie euristica de estimare a traseului complet optim. Daca aceasta functie este optimista, adica subestimeaza intotdeauna lungimea reala a unui traseu complet, atunci primul traseu complet gasit in cautare este in acelasi timp traseul optim. O astfel de functie poate fi, de exemplu, costul distantei dintre ultimul oras selectat si orasul de plecare. O functie euristica care estimeaza mai bine traseul de cost minim este costul arborelui de acoperire minim aSedgewick,1990i al nodurilor neparcurse la un moment dat.
2.1.3 Solutia problemei reprezentata prin grafuri SI/SAU
Exista probleme a caror rezolvare poate fi convenabil reprezentata printr-o tehnica numita reducerea problemei la subprobleme. Caracteristica comuna a acestei clase de probleme este aceea ca orice problema pusa de un obiect candidat la solutie poate fi vazuta ca o conjunctie de subprobleme ce pot fi rezolvate independent unele de altele. Rezolvarea problemelor din aceasta clasa poate fi abordata in urmatorul mod: se descompune problema in subproblemele care trebuie rezolvate, subproblemele se descompun la rindul lor in alte subprobleme si asa mai departe, pina cind se obtine o descompunere a problemei initiale in subprobleme elementare, adica banal de rezolvat.
Spatiul de cautare a unei astfel de rezolvari a problemei are forma unui graf SI/SAU. Un graf SI/SAU este un caz particular al unui hipergraf. Un hipergraf este format dintr-o multime de noduri si o multime de hiperarce definite prin perechi ordonate in care primul element este un nod din multimea de noduri a hipergrafului si cel de al doilea element este o submultime de noduri. Un graf obisnuit este un caz particular al unui hipergraf in care cel de al doilea element al hiperarcelor este o multime formata dintr-un singur element.
Definitie. O reprezentare a solutiei problemei prin grafuri SI/SAU este formata dintr-un triplet cu urmatoarea semnificatie:
* Si reprezinta descrierea problemei initiale,
* O reprezinta multimea de operatori de transformare (descompunere) a problemei in subprobleme,
* Pe reprezinta descrierea unei multimi de probleme elementare.
Definitie. Conform unui formalism stabilit, un graf SI/SAU este construit pe baza urmatoarelor reguli:
(1) Fiecare nod reprezinta fie o singura problema fie o multime de probleme ce trebuie rezolvate.
(2) Un nod ce reprezinta o singura problema nu are descendenti. Problema este fie o problema elementara, fie o problema neelementara care nu se mai poate descompune in subprobleme.
(3) Nodurile ce reprezinta multimea de subprobleme in care s-a descompus o problema prin aplicarea unui operator de descompunere se numesc noduri SI.
(4) Nodurile ce reprezinta descompuneri alternative ale unei probleme in subprobleme (prin aplicarea diversilor operatori de descompunere) se numesc noduri SAU. Aceste noduri au ca descendenti noduri SI.
Reprezentarea grafica a unui graf SI/SAU este data in Figura 2.3

Figura 2.3 Graf SI/SAU pentru reprezentarea spatiului de cautare
O problema rezolvata astfel are solutie daca nodul initial, corespunzator descrierii initiale a problemei, este rezolvat.
Definitie. Intr-un graf SI/SAU un nod este rezolvat daca:
(1) este un nod terminal etichetat cu o problema elementara
(2) este un nod SI si toti succesorii lui sint noduri rezolvate
(3) este un nod SAU si cel putin un succesor al acestuia este rezolvat
Definitie. Intr-un graf SI/SAU un nod este nerezolvabil daca:
(1) este un nod terminal etichetat cu o problema neelementara, deci care nu se mai poate descompune in subprobleme
(2) este un nod SI cu cel putin un succesor nerezolvabil
(3) este un nod SAU cu toti succesorii nerezolvabili.
O solutie a problemei este reprezentata prin secventa de operatori de descompunere care determina ca nodul problema initiala sa devina rezolvat. Altfel spus, solutia problemei este subgraful SI/SAU care face ca nodul problema initiala sa devina rezolvat.
Se considera problema turnurilor din Hanoi care cere sa se mute n discuri ( in Figura 2.4) de pe tija A pe tija C, utilizind tija intermediara B si mentinind restrictia ca un disc sa fie asezat fie pe o tija vida, fie peste un disc de o dimensiune mai mare decit el. Starea initiala este specificata in Figura 2.4(a), starea finala in Figura 2.4(b), iar multimea de operatori de descompunere este formata dintr-un singur operator, cu trei componente:
(1) Muta n-1 discuri de pe tija i pe tija j, utilizind tija k.
(2) Muta un disc de pe tija i pe tija k.
(3) Muta n-1 discuri de pe tija j pe tija k, utilizind tija i.
Singura problema elementara in acest caz este aceea de a muta un singur disc de pe o tija pe o tija vida. Descompunerea problemei in subprobleme poate fi reprezentata ca un arbore SI/SAU, prezentat in Figura 2.4(c).
Problema turnurilor din Hanoi are un singur operator de descompunere a problemelor in subprobleme. Din acest motiv spatiul de cautare reprezentat prin graf SI/SAU nu are noduri SAU (descompuneri alternative), ci numai noduri SI si noduri probleme elementare.
PROBLEMA: Muta n=3 discuri de pe tija A pe tija C, utilizind tija B


Figura 2.4 Reprezentarea solutiei problemei turnurilor din Hanoi prin arbore SI/SAU
Un alt exemplu de solutie a problemei prin descompunerea in subprobleme este problema cintaririi monezilor. Fiind date N monezi dintre care una este mai usoara sau mai grea decit celelalte, se cere sa se determine moneda de greutate diferita, utilizind o balanta cu doua talere, printr-un numar minim de cintariri. Problema initiala este cintarirea a N monezi. Operatorii de descompunere a problemei in subprobleme sint de forma: "Cintareste p monezi si rezolva toate problemele pe care aceasta cintarire le poate crea: balanta inclinata la stinga, balanta inclinata la dreapta, balanta echilibrata". Solutia problemei este arborele care include toate iesirile posibile pentru oricare din testele alese. In plus, fiecare cale in arbore trebuie sa reprezinte o secventa de teste si rezultate ale acestor teste care sa identifice neambiguu moneda diferita. Cititorul poate incerca gasirea numarului minim de cintariri pentru .

Modelul de rezolvare a problemelor prin descompunerea problemei in subprobleme poate fi folosit benefic numai in cazul in care rezolvarile subproblemelor sint independente intre ele. Aceasta inseamna ca procesul de cautare a solutiilor subproblemelor poate fi executat in orice ordine, solutia unei subprobleme neinfluentind solutia unei alte subprobleme. In problema cintaririi monezilor, fiecare subproblema se poate rezolva independent, si in orice ordine. Pentru alte probleme, cum ar fi de exemplu problema turnurilor din Hanoi, subproblemele de rezolvat nu sint independente si trebuie sa existe o ordine (liniara) de executie a solutiilor subproblemelor. Cu toate acestea se poate cauta solutia celei de-a treia subprobleme inaintea solutiei primei subprobleme. Aceasta proprietate nu este prezenta in problema mozaicului de 8 numere si din aceasta cauza o astfel de abordare a rezolvarii problemei nu aduce nici un beneficiu.
Rezolvarea problemelor prin descompunerea in subprobleme a stat la baza unuia dintre primele programe de inteligenta artificiala, General Problem Solver aNewell,Simon,1963i si a unor programe de planificare automata liniara cum ar fi STRIPS aFikes,Nilsson,1971i si ABSTRIPS aSacerdoti,1974i. Programul General Problem Solver (GPS) construieste un plan abstract pentru satisfacerea unui scop prin reducerea scopului la subscopuri si utilizeaza o metoda de rezolvare numita analiza bazata pe modalitati.
Se poate arata ca cele doua reprezentari ale solutiei problemei sint echivalente. De exemplu, se poate face transformarea din reprezentarea solutiei prin spatiul starilor in reprezentarea prin grafuri SI/SAU prezentata in Figura 2.5.

Figura 2.5 Echivalenta reprezentarilor prin spatiul starilor si grafuri SI/SAU
Se considera un labirint si problema gasirii iesirii din labirint, fiind data o pozitie initiala in labirint. Descrierea problemei initiale este "Gaseste iesire din pozitia initiala Pi" iar operatorii de descompunere a problemei in subprobleme sint:
O1 Deplasare un pas la Est si gaseste iesire din noua pozitie.
O2 Deplasare un pas la Sud si gaseste iesire din noua pozitie.
O3 Deplasare un pas la Vest si gaseste iesire din noua pozitie.
O4 Deplasare un pas la Nord si gaseste iesire din noua pozitie.
Problemele elementare sint: deplasare un pas la Est, Vest, Nord si respectiv Sud, daca labirintul permite, si iesire din labirint daca pozitia este la iesire. O portiune a grafului SI/SAU care reprezinta spatiul de cautare este prezentata in Figura 2.6.
Pentru aceasta problema se poate defini si o reprezentare prin spatiul starilor. Starea initiala este pozitia initiala in labirint iar starea finala este pozitia la iesirea din labirint. Operatorii de tranzitie dintr-o stare in alta sint miscarile la Est, Vest, Nord si respectiv Sud prin labirint.

Figura 2.6 Parte a grafului de cautare SI/SAU pentru problema labirintului
Observatii:
* Orice problema poate fi solutionata prin ambele metode de reprezentare prezentate, dar pentru o anumita problema este mai usor de utilizat o reprezentare sau alta.
* Anumite probleme conduc in mod natural la o reprezentare a solutiei prin spatiul starilor, asa cum au fost, de exemplu, problema mozaicului de 8 numere, problema celor 8 regine si jocul "Tic-Tac-Toe" (Capitolul 1). O astfel de rezolvare corespunde unui rationament direct pentru a solutiona problema sau unui control condus de date.
* Alte probleme, cum ar fi problema turnurilor din Hanoi si problema cintaririi monezilor, conduc in mod natural la o rezolvare prin descompunerea problemei in subprobleme. O astfel de rezolvare corespunde unui rationament invers pentru rezolvarea problemei sau unui control condus de scopuri.
2.2 Strategii de cautare de baza
In aceasta sectiune se prezinta strategiile de cautare de baza, numite si strategii neinformate, care reprezinta un mod sistematic de investigare a spatiului de cautare a solutiei problemei. Aceste strategii stau la baza tuturor metodelor de rezolvare a problemelor in inteligenta artificiala. Ele constituie, de asemenea, suportul pentru dezvoltarea strategiilor de cautare euristica.
2.2.1 Caracterizarea strategiilor de cautare
In momentul alegerii unei strategii de cautare trebuie sa se tina cont de urmatoarele trei elemente:
* Completitudinea strategiei care stabileste daca strategia asigura sau nu gasirea solutiei in cazul in care problema are solutie.
* Optimalitatea solutiei gasite care este data de capacitatea strategiei de a obtine o solutie optimala, suboptimala sau pur si simplu o solutie.
* Complexitatea strategiei care se refera la complexitatea timp si spatiu a algoritmului utilizat.
Completitudinea strategiei va fi discutata in raport cu fiecare strategie in parte, atit in acest capitol cit si in capitolele urmatoare. De exemplu, in Capitolul 3 se vor pune in evidenta strategii rezolutive complete si strategii incomplete, dar utilizate datorita eficientei de calcul. Optimalitatea solutiei va fi discutata in sectiunea urmatoare, iar complexitatea strategiilor de cautare va fi prezentata pe scurt in Sectiunea 2.4.
Caracterizarea unei strategii de cautare se poate face dupa urmatoarele doua criterii aNilsson,1980i:
(1) Capacitatea mecanismului de rezolvare de a reveni intr-o stare intermediara anterioara.
In functie de acest criteriu, strategiile de cautare se impart in:
* Strategii de cautare irevocabile. Un operator aplicabil este selectat, acest operator se aplica unei stari pentru a obtine o noua stare, iar starea anterioara este uitata (nu este memorata).
* Strategii de cautare tentative. La aplicarea unui operator intr-o stare curenta se memoreaza aceasta stare astfel incit procesul de cautare sa poata ulterior reveni in starile anterioare aplicarii operatorilor.
O strategie irevocabila este strategia de cautare a alpinistului, bazata pe criterii de optim local. Aceasta strategie se numeste a alpinistului deoarece, la fel ca un alpinist care doreste sa ajunga repede pe virful unui munte, alege starea urmatoare de nivel maxim pe baza unei functii de evaluare a starilor. Strategia este irevocabila deoarece pentru o stare curenta, se genereaza starile urmatoare, se alege starea de nivel maxim ca stare urmatoare si atit starea curenta cit si celelalte stari de pe nivelul starii urmatoare sint uitate. Selectia se face irevocabil, deci nu se mai poate reveni intr-una din starile anterioare starii curente sau intr-una din alternativele starii curente. Strategia alpinistului, desi simpla si putin consumatoare de memorie, prezinta o serie de limitari. De exemplu, daca problema cere determinarea starii cu o valoare maxima a functiei de evaluare, maximul global poate sa nu fie niciodata atins, cautarea blocindu-se intr-un maxim local.
Daca starea anterioara la care se poate reveni in timpul cautarii se afla numai pe calea curenta intre starea initiala si starea finala, strategia de cautare este o strategie tentativa de tip "backtracking". Aceasta este, de exemplu, strategia utilizata de limbajul Prolog. Daca starea anterioara in care se poate reveni se afla pe orice cale deja parcursa in expandarea spatiului de cautare, strategia este de cautare tentativa generala pe grafuri. In sectiunea urmatoare se va discuta acest tip de strategii, ca avind cel mai mare grad de generalitate.
(2) Cantitatea de informatie folosita la gasirea solutiei
In functie de acest criteriu, strategiile de cautare se impart in:
* Strategii de cautare neinformate. Considerarea starilor urmatoare de inspectat se face dupa o ordine arbitrara, anterior stabilita.
* Strategii de cautare informate. Considerarea starilor urmatoare de inspectat se face dupa criterii euristice. Strategia foloseste o functie de evaluare a situatiei globale sau locale care indica starea urmatoare cea mai promitatoare din punct de vedere al avansului spre solutie.
Strategiile de cautare neinformata (de baza) inspecteaza sistematic toate starile spatiului de cautare pina in momentul gasirii starii finale. Cele mai importante strategii de acest fel sint cautarea pe nivel si cautarea in adincime. Strategiile de cautare euristice incearca reducerea numarului de stari din spatiul de cautare inspectate pina la atingerea starii finale, pe baza diverselor criterii, cum ar fi functiile euristice. Strategia alpinistului descrisa anterior este un exemplu de cautare informata. Alte exemple sint strategia de cautare "best-first", algoritmul A* si algoritmul AO*. Algoritmii A* si AO* urmaresc in principal, pe linga reducerea numarului de stari inspectate, gasirea solutiei optime, asa cum se va vedea in Sectiunile 2.3.2 si 2.3.4.
Costul computational total al unui program de rezolvare a problemelor de inteligenta artificiala depinde de locul unde se situeaza strategia de control in spectrul neinformat/informat. Costul computational poate fi impartit in doua costuri: costul aplicarii operatorilor, sau costul parcurgerii spatiului de cautare intre starea initiala si starea finala, si costul controlului, sau costul evaluarii si selectiei celei mai promitatoare stari urmatoare. O strategie de cautare complet neinformata implica un cost redus al controlului datorita selectiei arbitrare a starilor urmatoare. O astfel de strategie determina insa un cost ridicat al parcurgerii spatiului de cautare deoarece, in general, necesita aplicarea unui numar mare de operatori inaintea gasirii unei solutii. O strategie de control complet informata despre domeniul problemei implica un cost al controlului ridicat atit din punct de vedere al timpului cit si al spatiului deoarece poate necesita calcule complicate pentru evaluarea meritului starilor si memorarea tuturor starilor parcurse. In schimb, o astfel de strategie determina un cost minim de parcurgere a spatiului de cautare datorita numarului redus de operatori aplicati pina la gasirea solutiei.
Costul computational total rezulta din combinarea celor doua costuri, asa cum se vede in Figura 2.7. In functie de aplicatie, proiectantul programului trebuie sa incerce determinarea celei mai bune variante de pondere a costurilor. Obtinerea unui cost computational optim este un aspect esential deoarece problemele de cautare sint probleme de complexitate timp exponentiala, asa cum se prezinta in Sectiunea 2.4.

Figura 2.7 Costul total al rezolvarii unei probleme prin cautare
In continuare se va utiliza urmatoarea terminologie. In parcurgerea spatiului de cautare un nod poate fi:
* necunoscut - nodul apartine partii neexplorate a spatiului de cautare,
* evaluat - nodul este cunoscut dar fie nu se cunoaste nici un succesor al lui, fie se cunosc numai o parte din succesorii lui,
* expandat - nodul este cunoscut si, in plus, se cunosc toti succesorii lui.
Prin expandarea unui nod se intelege generarea tuturor succesorilor acelui nod. Aceasta inseamna obtinerea tuturor starilor urmatoare starii curente S, prin aplicarea tuturor operatorilor legali in starea S.
In procesul de cautare se vor folosi doua liste:
* FRONTIERA - lista nodurilor evaluate
* TERITORIU - lista nodurilor expandate
Lista FRONTIERA reprezinta frontiera spatiului de cautare parcurs (explicitat) spre partea necunoscuta a spatiului de cautare. Lista TERITORIU reprezinta partea cunoscuta a spatiului de cautare.
2.2.2 Cautari neinformate in spatiul starilor
In continuare se prezinta doua strategii de cautare neinformate: cautarea pe nivel si cautarea in adincime, strategii care difera prin ordinea de considerare, arbitrar fixata, a starilor urmatoare. Algoritmii prezentati presupun existenta a doua conditii. In primul rind, spatiul de cautare este arbore, deci exista o cale unica intre starea initiala si starea finala. Rezulta ca toate starile generate pe parcursul cautarii sint unice, deci nu au mai fost anterior generate. Extinderea si modificarile necesare pentru a generaliza algoritmii la spatii de cautare de tip graf vor fi prezentate in final. In al doilea rind, la fiecare expandare a unui nod, prin crearea tuturor nodurilor corespunzatoare starilor urmatoare, se stabileste o legatura de la fiecare nod succesor la nodul expandat. In momentul descoperirii nodului stare finala aceste legaturi permit reconstruirea caii spre solutie.
Definitie. Intr-o reprezentare a solutiei problemei prin spatiul starilor adincimea unui nod se defineste astfel:
(1) , unde Si este nodul stare initiala,
(2) , unde Sp este nodul predecesor nodului S.
Cautarea pe nivel
Cautarea pe nivel, numita si cautare in latime, este o strategie care expandeaza starile urmatoare in ordinea apropierii fata de nodul stare initiala. Cu alte cuvinte, aceasta strategie considera intii toate secventele posibile de n operatori inaintea secventelor de n+1 operatori.
Algoritm: Strategia cautarii pe nivel in spatiul starilor
1. Creeaza listele si
2. daca atunci intoarce INSUCCES /* nu exista solutie */
3. Elimina primul nod S din FRONTIERA si insereaza-l in TERITORIU
4. Expandeaza nodul S
4.1. Genereaza toti succesorii directi ai nodului S
4.2. pentru fiecare succesor al lui S executa
4.2.1. Stabileste legatura
4.2.2. daca este stare finala atunci i. Solutia este ii. intoarce SUCCES /* s-a gasit solutie */
4.2.3. Insereaza in FRONTIERA, la sfirsit
5. repeta de la 2 sfirsit.
Cautarea poate fi uneori lunga si complex computationala din punct de vedere al spatiului utilizat deoarece pentru fiecare nivel sint generate toate starile succesoare posibile. Cu toate acestea, strategia de cautare pe nivel garanteaza gasirea solutiei, in cazul in care aceasta exista si, in plus, gaseste cel mai scurt drum spre solutie in termenii numarului de tranzitii de stari executate.
Cautarea in adincime
Cautarea in adincime este o strategie care expandeaza starile cel mai recent generate, cu alte cuvinte nodurile cu adincimea cea mai mare din lista FRONTIERA. In consecinta, aceasta strategie parcurge o cale de la starea initiala pina la o stare ce poate fi stare finala sau care nu mai are nici un succesor. In acest ultim caz strategia revine pe nivelele anterioare si incearca explorarea altor cai posibile.
Strategia cautarii in adincime nu garanteaza obtinerea unei solutii a problemei, chiar in cazul in care solutia exista. O astfel de situatie poate apare, de exemplu, in cazul unui spatiu de cautare infinit in care ramura pe care s-a plecat in cautare nu contine solutia. Din acest motiv se introduce de obicei o limita a adincimii maxime de cautare, AdMax. Daca s-a atins aceasta limita fara a se gasi solutia, strategia revine si inspecteaza stari de pe nivele inferioare lui AdMax dar aflate pe cai diferite. Solutia care s-ar gasi la o adincime de AdMax+p, de exemplu, ar fi pierduta. Daca strategia de cautare gaseste solutia, aceasta nu este neaparat calea cea mai scurta intre starea initiala si starea finala.
Algoritm: Strategia cautarii in adincime in spatiul starilor
1. Creeaza listele si
2. daca atunci intoarce INSUCCES /* nu exista solutie sau solutia nu poate fi gasita pina la nivelul AdMax */
3. Elimina primul nod S din FRONTIERA si insereaza-l in TERITORIU
3'. daca atunci repeta de la 2
4. Expandeaza nodul S
4.1. Genereaza toti succesorii directi ai nodului S
4.2. pentru fiecare succesor al lui S executa
4.2.1. Stabileste legatura
4.2.2. daca este stare finala atunci i. Solutia este ii. intoarce SUCCES /* s-a gasit solutie */
4.2.3. Insereaza in FRONTIERA, la inceput
5. repeta de la 2 sfirsit.
Algoritmul cautarii in adincime prezinta avantajul generarii unui numar de stari mult mai mic decit in cazul algoritmului de cautare pe nivel, deci consumul de spatiu este mult redus. Evident, algoritmul plateste pretul limitarilor indicate anterior.
Aceste observatii au dus la crearea algoritmului de cautare in adincime cu nivel iterativ aKorf,1987i. Algoritmul lui Korf elimina multe din dezavantajele cautarii pe nivel si a cautarii in adincime. Algoritmul de cautare in adincime cu nivel iterativ realizeaza la inceput o cautare in adincime in spatiul starilor cu o adincime maxima de cautare . Daca starea finala nu a fost gasita, se reia cautarea in adincime cu si se continua in acest fel, crescind adincimea de cautare la fiecare iteratie. La fiecare iteratie algoritmul realizeaza o cautare in adincime completa cu adincimea de cautare egala cu valoarea curenta AdMax. Intre doua iteratii succesive nu se retine nici o informatie despre spatiul de cautare. Deoarece algoritmul de cautare in adincime cu nivel iterativ realizeaza de fapt o cautare pe nivel, el este garantat sa gaseasca solutia, daca aceasta exista, si, in plus, determina drumul cel mai scurt la solutie. Deoarece strategia este de adincime, numarul de stari generate la fiecare iteratie este mai mic decit cel in cazul cautarii pe nivel.
Extinderea celor doi algoritmi de cautare, pe nivel si in adincime, la cazul in care spatiul de cautare este graf se poate face tinind cont de faptul ca, in acest caz, un nod care se expandeaza poate avea ca succesor o stare ce a mai fost deja evaluata sau expandata. Pentru a evita reconsiderarea unei stari intilnite anterior, pasul de inserare a starii Sj in lista FRONTIERA (pasul 4.2.3) se modifica astfel:
4.2.3' daca nu apartine atunci insereaza in FRONTIERA, la sfirsit /* nivel */
4.2.3' daca nu apartine atunci insereaza in FRONTIERA, la inceput /* adincime */
In cazul algoritmului strategiei de cautare in adincime, existenta limitei de cautare AdMax protejeaza contra buclelor care s-ar putea crea prin generarea repetata a aceleiasi stari. In aceste conditii pasul 4.2.3' nu mai este absolut necesar, dar neintroducerea lui intr-un astfel de algoritm poate duce la evaluarea repetata a unor stari pina la atingerea adincimii AdMax, in cazul spatiului de cautare graf.
In cazul introducerii pasului 4.2.3', portiunea expandata a spatiului de cautare va fi intotdeauna un arbore si nu un graf, deoarece acest pas evita regenerarea unor stari anterior expandate.
Observatii:
* Cautarea pe nivel corespunde unei politici de tip FIFO de exploatare a listei FRONTIERA, in timp ce cautarea in adincime corespunde unei politici de tip LIFO.
* Ambele tipuri de cautari realizeaza un rationament direct, pornind in rezolvarea problemei de la starea initiala si generind arborele de cautare a starii finale. In anumite cazuri se poate aplica un rationament invers, executind strategiile incepind din starea finala si cautind starea initiala, cu conditia existentei unor operatori "inversi" de trecere dintr-o stare curenta in starea anterioara. Un astfel de exemplu poate fi jocul mozaicului de 8 numere, in care starea finala poate fi descrisa iar operatorii "inversi" sint usor de definit.
* In anumite probleme se poate utiliza o combinatie intre rationamentul direct si invers, adica un rationament bidirectional in care se cauta solutia atit din starea initiala cit si din starea finala prin construirea in paralel a doi arbori de cautare. Daca o astfel de abordare pleaca de la cautarea in adincime, exista pericolul ca sa se genereze doi arbori paraleli, unul pe calea directa si altul pe calea inversa, arbori care nu vor avea noduri intermediare comune. In acest caz avantajele cautarii bidirectionale sint pierdute.
2.2.3 Cautari neinformate in grafuri SI/SAU
Strategiile de cautare pe nivel si in adincime pot fi usor adaptate la cautarea solutiei problemei in reprezentarea cu grafuri SI/SAU. Principala diferenta consta in criteriul de determinare a conditiei de oprire. In reprezentarea prin spatiul starilor, conditia de oprire a algoritmilor este data de testarea proprietatii unui singur nod, nodul stare finala, in timp ce pentru reprezentarea prin descompunerea problemei in subprobleme trebuie sa se testeze daca o multime de noduri formeaza un arbore solutie. In consecinta, impactul fiecarui nod nou generat trebuie propagat in arborele partial construit pentru a determina daca nodul problema initiala a devenit rezolvat. Algoritmii de cautare in grafuri SI/SAU trebuie sa gestioneze, pe linga listele FRONTIERA si TERITORIU, si o structura de date care reprezinta arborele SI/SAU construit prin explicitarea spatiului de cautare definit implicit de reprezentare.
O alta diferenta a algoritmilor de cautare in grafuri SI/SAU fata de cei in spatiul starilor consta in nodurile introduse in listele FRONTIERA si TERITORIU. Nodurile SI nu se introduc in aceste liste deoarece ele nu corespund efectiv unor subprobleme, ci indica numai o multime de subprobleme care trebuie rezolvate. Aceste noduri sint insa construite si fac parte din portiunea explicitata a spatiului de cautare. Pe baza starii de rezolvat sau nerezolvabil a acestor noduri se poate decide cind s-a obtinut arborele solutie.
De exemplu, fie o problema P1 care poate fi redusa, alternativ, la o singura subproblema (echivalenta) P2 prin aplicarea operatorului de descompunere O1 si la subproblemele P5, P6, P7 prin aplicarea operatorului O2, asa cum se arata in Figura 2.8. In acest caz expandarea nodului N1 va genera nodurile N2, N3, N5, N6 si N7, fiecarui nod nou generat i se va atasa o legatura spre predecesor, dar numai nodurile N2, N5, N6 si N7 vor fi introduse in lista nodurilor explorate FRONTIERA.

Figura 2.8 Expandarea nodurilor in grafuri SI/SAU
In aceste conditii, la calculul adincimii unui nod intr-un arbore SI/SAU nu se considera nodurile SI. Daca se considera ca nodul problema initiala are adincimea 0, adincimea oricarui nod subproblema va fi lungimea secventei de operatori care trebuie aplicati pentru a ajunge din nodul initial in acel nod.
Definitie. Intr-o reprezentare a solutiei problemei prin grafuri SI/SAU adincimea unui nod se defineste astfel:
(1) , unde Si este nodul problema initiala,
(2) , daca Sp este nod SAU predecesor al nodului S,
(3) , daca Sp este nod SI predecesor al nodului S.
Cautarea pe nivel
In reprezentarea prin descompunerea problemei in subprobleme strategia cautarii pe nivel foloseste aceeasi ordine de expandare a nodurilor ca in cazul reprezentarii prin spatiul starilor. Algoritmul care urmeaza presupune ca spatiul de cautare este un arbore SI/SAU si nu un graf general, deci o aceeasi stare nu poate fi generata de mai multe ori. De asemenea, se presupune ca problemele generate prin reducerea unei probleme in subprobleme pot fi rezolvate in orice ordine, deci sint independente. Nodul Si este nodul corespunzator descrierii initiale a problemei.
Algoritm: Strategia cautarii pe nivel in arbori SI/SAU.
1. Creaza listele si
2. Elimina primul nod S din FRONTIERA si insereaza-l in TERITORIU
3. Expandeaza nodul S
3.1. Genereaza toti succesorii directi ai nodului S
3.2. pentru fiecare succesor al lui S executa
3.2.1. Stabileste legatura
3.2.2. daca reprezinta o multime de cel putin 2 subprobleme atunci /* este nod SI */ i. Genereaza toti succesorii subprobleme ai lui ii. Stabileste legaturile intre nodurile iii. Insereaza nodurile in FRONTIERA, la sfirsit
3.2.3. altfel insereaza in FRONTIERA, la sfirsit
4. daca nu s-a generat nici un succesor al lui S in pasul precedent atunci
4.1. daca S este nod terminal etichetat cu o problema neelementara atunci
4.1.1. Eticheteaza S nerezolvabil
4.1.2. Eticheteaza cu nerezolvabil toate nodurile predecesoare lui S care devin nerezolvabile datorita lui S /* toate nodurile care il au pe S descendent in arborele SI/SAU construit */
4.1.3. daca nodul este nerezolvabil atunci intoarce INSUCCES /* problema nu are solutie */
4.1.4. Elimina din FRONTIERA toate nodurile care au predecesori nerezolvabili
4.2. altfel /* S este nod terminal etichetat cu o problema elementara */
4.2.1. Eticheteaza S rezolvat
4.2.2. Eticheteaza cu rezolvat toate nodurile predecesoare lui S care devin rezolvate datorita lui S
4.2.3. daca nodul este rezolvat atunci i. Construieste arborele solutie urmarind legaturile ii. intoarce SUCCES /* s-a gasit solutia */
4.2.4. Elimina din FRONTIERA toate nodurile rezolvate si toate nodurile care au predecesori rezolvati
5. repeta de la 2 sfirsit.
Observatii:
* Conditia din pasul 4 al algoritmului specifica faptul ca problema asociata nodului S nu mai poate fi descompusa in subprobleme. Acest lucru se intimpla fie in cazul in care problema este neelementara si ireductibila (pasul 4.1), caz in care S devine nerezolvabil, fie in cazul in care S este problema elementara, deci banal de rezolvat (pasul 4.2), caz in care S devine rezolvat.
* Legaturile care se stabilesc de la fiecare nod nou generat la predecesorul lui definesc arborele SI/SAU construit pe parcursul cautarii. Spre deosebire de reprezentarea prin spatiul starilor in care solutia problemei este calea parcursa intre nodul stare initiala si nodul stare finala, cale formata numai din noduri ce exista in lista TERITORIU, in cazul descompunerii problemei in subprobleme solutia problemei este tot arborele SI/SAU, care contine si noduri ce nu apar in TERITORIU sau FRONTIERA.
Cautarea pe nivel garanteaza gasirea solutiei, daca problema are solutie. In plus, arborele solutie construit este arborele de inaltime minima, deci cel care contine numarul minim de operatori necesari pentru a rezolva problema.
Cautarea in adincime
La fel ca in cazul cautarii in adincime in spatiul starilor, cautarea in adincime in grafuri SI/SAU considera mai intii nodurile cu cea mai mare adincime din lista FRONTIERA. Algoritmul cautarii in adincime se poate obtine din cel al cautarii pe nivel in arbori SI/SAU prin adaugarea unui pas suplimentar 2' dupa pasul 2 care limiteaza adincimea de cautare la un nivel maxim AdMax si prin inlocuirea pasilor iii si 3.2.3 cu pasii iii' si 3.2.3'.
2'. daca atunci repeta de la 2 iii'. Insereaza nodurile in FRONTIERA, la inceput
3.2.3'. altfel insereaza in FRONTIERA, la inceput
Algoritmul cautarii in adincime nu garanteaza gasirea solutiei si nici construirea arborelui solutie minim, dar genereaza un numar de noduri mult mai mic decit cel din algoritmul cautarii pe nivel.
Ambii algoritmi se pot extinde pentru cazul in care spatiul de cautare este graf, printr-o tehnica similara cu cea prezentata in sectiunea anterioara, deci cu verificarea prezentei unei subprobleme nou generate in listele FRONTIERA si TERITORIU. Aceasta generalizare este inclusa in algoritmul de cautare informata in grafuri SI/SAU din sectiunea urmatoare.
2.3 Strategii de cautare euristica
In rezolvarea problemelor utilizind strategii de cautare neinformata numarul de stari investigate inainte de a gasi o solutie poate ajunge prohibitiv de mare, chiar si pentru probleme relativ simple, aparind deci explozia combinationala. Spatiul de cautare explorat poate fi redus prin aplicarea cunostintelor euristice despre problema. Acest capitol discuta modul in care informatia euristica poate fi utilizata in cautare pornind de la strategiile de baza si obtinind strategii de cautare euristica.
Cunostintele euristice pot fi folosite pentru a creste eficienta cautarii in trei moduri:
(1) Selectarea nodului urmator de expandat in cursul cautarii
(2) In cursul expandarii unui nod al spatiului de cautare se poate decide pe baza informatiilor euristice care dintre succesorii lui vor fi generati si care nu.
(3) Eliminarea din spatiul de cautare a anumitor noduri generate.
Aceasta sectiune se ocupa de prima modalitate de utilizare a cunostintelor euristice pentru a alege nodul "cel mai promitator" pentru obtinerea solutiei. Al doilea mod de utilizare a euristicilor revine de fapt la expandarea partiala a unui nod prin aplicarea numai a unui subset de operatori dintre cei posibil de aplicat. O varianta a acestei tehnici este analiza bazata pe modalitati utilizata in programul General Problem Solver care alege operatorul cel mai potrivit pentru a avansa spre solutie, chiar daca nu este imediat aplicabil. Ulterior, se incearca atingerea unei stari in care operatorul poate fi aplicat, deci se incearca satisfacerea unui subscop. Al treilea mod de utilizare a euristicilor incearca eliminarea anumitor noduri pe baza deciziei daca aceste noduri pot face parte din solutie sau nu. Aceasta tehnica se numeste taierea arborelui de cautare.
2.3.1 Cautare informata de tip "best-first"
Ideea strategiei de cautare "best-first" este aceea de a selecta spre expandare cel mai bun nod din spatiul de cautare generat pe baza cunostintelor euristice, deci pe baza unei estimari. Calitatea unui nod, din punct de vedere al gasirii solutiei, poate fi estimata in diverse moduri. Se poate atribui nodului gradul de dificultate in solutionarea problemei reprezentata de acel nod. Se poate estima calitatea unei multimi de solutii candidate care contin acel nod, deci solutii partiale care contin o cale ce duce la acel nod. O a treia alternativa este aceea de a evalua cantitatea de informatie care poate fi obtinuta prin expandarea acelui nod si importanta acestei informatii in ghidarea procesului de cautare. In toate aceste cazuri calitatea unui nod este estimata de functia de evaluare euristica, notata w(n) pentru nodul n, care poate depinde de descrierea lui n, de descrierea scopului si de cunostinte suplimentare despre problema.
Una dintre cele mai simple strategii informate pentru modelul reprezentarii prin spatiul starilor, bazata pe un criteriu de optim local, este strategia de cautare a alpinistului, amintita anterior. Ideea acestei strategii este expandarea unui nod, inspectarea succesorilor acestuia si calculul valorilor functiei euristice pentru acesti succesori, apoi alegerea celui mai bun nod in functie de aceste valori. Toate celelalte noduri sint uitate, inclusiv nodul stare curenta, deci strategia este irevocabila. Simplitatea acestei strategii este platita de dezavantajele strategiei: posibilitatea de a pierde solutia, blocarea in maxime locale si inspectarea repetata a aceleiasi stari. Strategia este evident incompleta.
In cazul strategiilor tentative informate generale, selectia nodului cel mai promitator se face evaluind toate nodurile generate pina la un moment dat, indiferent de calea in arborele de cautare pe care se afla un nod. In continuare se prezinta un algoritm de cautare de tip "best-first" pentru reprezentarea solutiei problemei prin spatiul starilor. Se presupune ca spatiul de cautare este un graf si ca nodul selectat pentru expandare este cel care are cea mai mica valoare a functiei euristice w(n); Si este starea initiala.
Algoritm: Strategia de cautare "best-first" in spatiul starilor
1. Creaza listele si
2. Calculeaza si asociaza aceasta valoare nodului
3. daca atunci intoarce INSUCCES /* nu exista solutie */
4. Alege din FRONTIERA un nod S pentru care w(S) este minima
5. Elimina nodul S din FRONTIERA si insereaza-l in TERITORIU
6. daca S este starea finala atunci
6.1. Construieste solutia prin urmarirea legaturilor
6.2. intoarce SUCCES /* s-a gasit solutia */
7. Expandeaza nodul S
7.1. Genereaza toti succesorii directi ai nodului S
7.2. pentru fiecare succesor al lui S executa
7.2.1. Calculeaza si asociaza valoarea lui
7.2.2. Stabileste legatura
7.2.3. daca atunci introduce in FRONTIERA
7.2.4. altfel i. Fie copia lui din FRONTIERA sau TERITORIU ii. daca atunci
- Modifica legatura in legatura
- Inlocuieste asociata lui cu
- daca atunci elimina din TERITORIU si insereaza-l in FRONTIERA iii. Ignora nodul
8. repeta de la 3 sfirsit.
Observatii:
* Pasii 7.2.3 si 7.2.4 sint necesari pentru a trata cazul in care spatiul de cautare este graf. In timpul cautarii se genereaza graful spatiului de cautare si, in acelasi timp, arborele de cautare definit de legaturile intre noduri stabilite la pasul 7.2.2.
* Daca pe parcursul cautarii o stare a fost redescoperita iar drumul pina la noua aparitie a starii este mai scurt, algoritmul trebuie sa considere noul drum gasit. Nodul pina la care s-a descoperit un drum mai scurt devine din nod expandat nod explorat prin reintroducerea lui in FRONTIERA, cu noua valoare mai mica a functiei w gasita (pasul ii). Acest proces este prezentat intuitiv in Figura 2.9.

Figura 2.9 Reexplorarea unui nod la gasirea unei valori euristice inferioare.
Strategia de cautare "best-first" este o generalizare a strategiilor de cautare neinformate prezentate anterior. Prin particularizarea functiei w se pot obtine ambele strategii de baza astfel:
* , conduce la strategia de cautare pe nivel
* , conduce la strategia de cautare in adincime
Criteriul nodului celui mai promitator si stabilirea functiei de evaluare euristica depinde de problema si de proprietatile solutiei cautate.
Daca spatiul de cautare contine mai multe cai spre solutie si se asociaza un cost fiecarui arc intre doua noduri Sk si Sk+1, cost determinat de costul aplicarii operatorului pentru a trece din starea Sk in starea Sk+1, atunci fiecare cale spre starea finala are asociat un cost. Daca se doreste gasirea caii de cost minim se stabileste urmatoarea formula pentru calculul functiei de evaluare: , unde i este indicele starii initiale.
In acest caz se obtine o strategie de cautare de cost uniform, numita si strategie de tip "branch and bound". Aceasta strategie garanteaza gasirea solutiei optime, daca exista solutie. Daca nu intereseaza optimalitatea solutiei si se urmareste numai minimizarea efortului de cautare, atunci se alege o functie euristica w care estimeaza, pentru fiecare nod, cit de aproape sau cit de departe este acel nod fata de nodul stare finala. Daca intereseaza ambele aspecte, deci atit calitatea solutiei cit si minimizarea efortului de cautare, se utilizeaza strategia de cautare A* care va fi prezentata in sectiunea urmatoare.
Principiul strategiei de cautare "best-first" poate fi aplicat si pentru cazul reprezentarii solutiei problemei prin descompunerea in subprobleme. De aceasta data insa functia de evaluare trebuie sa se refere la un arbore solutie partial si nu la un singur nod, asa cum se face pentru reprezentarea prin spatiul starilor. Varianta AO* a strategiei "best-first" pentru grafuri SI/SAU care clarifica aceste aspecte va fi discutata in Sectiunea 2.3.4.
Observatie. Algoritmul de cautare "best-first" este o strategie completa daca reuseste sa elimine intotdeauna caile ciclice. Acest lucru este evident realizat daca costul unei cai fara cicluri este intotdeauna egal sau mai mic decit costul unei cai care contine cicluri.
2.3.2 Cautarea solutiei optime in spatiul starilor. Algoritmul A*
Algoritmul A* urmareste determinarea caii de cost minim intre nodul asociat starii initiale si nodul asociat unei stari finale. Acest obiectiv include si problema gasirii caii spre solutie care contine un numar minim de arce, i.e. calea care implica aplicarea unui numar minim de operatori. Problema gasirii celei mai scurte cai este o particularizare a cazului general, particularizare in care costul arcelor este considerat unitar.
Algoritmul A* este o strategie de cautare informata de tip "best-first" pentru reprezentarea solutiei folosind spatiul starilor. Caracteristica distinctiva a algoritmului consta in modul de definire a functiei de evaluare w(S) care este notata in acest caz cu f(S). Nodul ales pentru expandare este nodul cu valoarea minima a functiei f aNilsson,1980;Pearl,1984i. Deoarece f evalueaza nodurile din punct de vedere al gasirii solutiei de cost minim, f(S) include doua componente:
* g(S), o functie care estimeaza costul real g*(S) al caii de cautare intre starea initiala Si si starea S,
* h(S), o functie care estimeaza costul real h*(S) al caii de cautare intre starea curenta S si starea finala Sf.
In aceste conditii functia de evaluare se defineste astfel: si reprezinta o estimare a costului real al unei solutii a problemei care trece prin starea S (Figura 2.10).

Figura 2.10 Componentele functiei euristice a algoritmului A*
Functia g(S) este calculata ca fiind costul actual al drumului parcurs in cautare intre starea initiala Si si starea S, deci , cu si Si starea initiala
Daca spatiul starilor este un arbore, g(S) este o estimare perfecta a costului real g*(S). Daca spatiul de cautare este graf, g(S) poate numai sa supraestimeze costul real g*(S). In consecinta pentru orice stare S. Algoritmul A* se obtine din algoritmul "best-first" prin utilizarea functiei f(S) in locul lui w(S) si inlocuirea conditiei din pasul 7.2.4. ii cu conditia .
Functia h(S) este functia purtatoare de informatie euristica si trebuie definita in raport cu caracteristicile problemei particulare de rezolvat. Pentru ca algoritmul A* sa gaseasca solutia optima, functia h trebuie sa fie nenegativa si sa subestimeze intotdeauna costul real h*(S) al caii care a mai ramas de parcurs pina in starea finala.
Definitie. O functie euristica h se numeste admisibila daca pentru orice stare S. Definitia stabileste conditia de admisibilitate a functiei h si este folosita pentru a defini proprietatea de admisibilitate a unui algoritm A*.
Teorema. Fie un algoritm A* care utilizeaza cele doua componente g si h ale functiei de evaluare f. Daca
(1) functia h satisface conditia de admisibilitate
(2) , pentru orice doua stari S, S', unde este o constanta si costul c este finit atunci algoritmul A* este admisibil, adica este garantat sa gaseasca calea de cost minim spre solutie.
Observatie. Se poate demonstra ca algoritmul A* este o strategie completa, chiar si pentru spatii de cautare grafuri infinite aPearl,1984i.
2.3.3 Caracteristicile euristicii algoritmului A*
Conditia de admisibilitate a functiei euristice indica faptul ca h(S) trebuie sa fie o subestimare a costului real h*(S), adica sa fie optimista, pentru ca algoritmul A* sa gaseasca intotdeauna solutia optima. Daca h(S) este cu mult mai mic decit h*(S) atunci algoritmul A* isi pierde din performantele timpului de cautare. Pentru ca numarul de stari inspectate in cautare sa fie cit mai mic, este de dorit ca h(S) sa fie cit mai apropiat de h*(S). Ideal, daca h(S) ar fi egal cu h*(S) pentru orice stare S parcursa in cautare, atunci algoritmul A* gaseste drumul optim spre starea finala fara a expanda niciodata vreun nod care nu se afla pe calea optima spre solutie. Daca atunci algoritmul A* se reduce la o strategie de cautare de cost uniform. Deci algoritmul A* este cu atit mai informat cu cit h(S) este mai apropiat de h*(S).
Gradul de informare al unui algoritm A*
Definitie. Fie doi algoritmi A*, A1 si A2, cu functiile de evaluare


Se spune ca algoritmul A2 este mai informat decit algoritmul A1 daca pentru orice stare S, , starea finala.
Se poate demonstra ca daca A2 este mai informat decit A1 atunci A2 nu expandeaza niciodata mai multe stari decit A2. Se poate demonstra de asemenea ca daca componenta h a functiei f a unui algoritm A* are propietatea de a fi monoton crescatoare, i.e. pentru orice doua stari S, S' cu atunci un nod, odata introdus in lista TERITORIU, nu va mai fi niciodata eliminat din TERITORIU si reinserat in FRONTIERA.
Determinarea functiei de evaluare f
Pentru stabilirea functiei f trebuie definite functiile g si h. De obicei, componenta g(S) poate fi calculata ca suma costurilor arcelor parcurse din starea initiala Si pina in starea S sau, daca costurile arcelor sint unitare sau problema nu are definite costuri pentru operatori, ca numarul de arce parcurse din Si pina in S.
Determinarea functiei h(S), purtatoarea informatiei euristice, este mai dificila deoarece functia h depinde de problema specifica de rezolvat. Este sarcina celui care construieste algoritmul A* sa descopere o functie euristica adecvata.
Fie problema mozaicului de 8 numere definita in Sectiunea 2.1.2. Un algoritm A* de rezolvare a acestei probleme ar putea utiliza o definitie a functiei h(S) cum este cea care a fost indicata la specificarea problemei: unde
Functia de evaluare este , unde g(S) este numarul de miscari parcurse din starea initiala Si pina in starea S. Se poate defini insa o functie euristica mai buna decit h1, adica mai informata, unde este distanta (pe orizontala si verticala) a patratului nevid ti in starea S fata de pozitia lui in starea finala Sf. Aceasta distanta se mai numeste si "distanta Manhattan". Pentru exemplul din Figura 2.1 se obtin urmatoarele valori ale functiilor euristice h1 si h2:


Se poate arata ca un algoritm A* care utilizeaza functia are un grad de informare mai mare decit un algoritm A* care utilizeaza functia f1(S) definita mai sus. Acest lucru se poate justifica informal prin faptul ca h1(S) nu ofera o estimare foarte buna a dificultatii unei configuratii. Functia h2(S) ofera o mai buna estimare din punct de vedere al numarului de pasi necesari pina la atingerea starii finale. Atit h1 cit si h2 sint functii admisibile.
Tot in Sectiunea 2.1.2 s-a prezentat problema comis-voiajorului. Un algoritm A* care rezolva aceasta problema poate utiliza o functie de evaluare , unde g(S) reprezinta lungimea drumului (suma distantelor) parcurs de comis-voiajor din orasul de plecare pina in orasul asociat starii S, iar h1 este definita astfel , unde Si este starea initiala asociata orasului de plecare iar S este starea orasului in care se afla comis-voiajorul. Se reaminteste ca in problema comis-voiajorului oricare doua orase sint legate intre ele printr-un drum. Se poate folosi si functia euristica h2(S) egala cu costul arborelui de acoperire minim al oraselor neparcurse pina in starea S. Atit h1 cit si h2 sint functii admisibile. Se poate demonstra ca un algoritm A* care foloseste functia este mai informat decit un algoritm care foloseste f1(S).
O problema asemanatoare ca natura cu problema comis-voiajorului este problema gasirii drumului minim intre doua orase pe o harta. Harta este definita printr-un numar de orase si prin legaturile dintre aceste orase, cu distantele asociate. Un algoritm A* pentru aflarea drumului minim intre doua orase poate utiliza o functie euristica , cu g(S) definita ca lungimea drumului deja parcurs intre orasul de plecare si starea S si h(S) definita ca distanta directa pe harta (zbor de pasare) intre orasul asociat starii S si orasul de destinatie. Functia h astfel definita este admisibila.
In final se considera problema misionarilor si canibalilor. Trei misionari si trei canibali ajung la un riu. Exista o barca de doua locuri cu care se poate traversa riul. Daca numarul canibalilor este mai mare decit numarul misionarilor pe unul din malurile riului, misionarii vor fi mincati de canibali. Cum pot trece toti riul fara ca misionarii sa fie mincati? Starea initiala si starea finala a acestei probleme sint descrise in Figura 2.11.

Figura 2.11 Problema misionarilor si canibalilor
Incercind rezolvarea aceste probleme cu ajutorul unui algoritm A* se propun urmatoarele trei functii de evaluare (Giumale,1989):



Functia g(S) este definita ca fiind egala cu numarul de tranzitii de stari efectuate din starea initiala pina in starea curenta S. Pentru definitia functiilor h1, h2, si h3 se fac urmatoarele conventii:
- numar de misionari pe malul de EST in starea S
- numar de misionari pe malul de VEST in starea S
- numar de canibali pe malul de EST in starea S
- numar de canibali pe malul de VEST in starea S
- numar de persoane pe malul de EST in starea S
- numar de persoane pe malul de VEST in starea S si se definesc cele trei functii euristice propuse astfel:
*
*
*
Functia h1 nu este admisibila deoarece pentru starea Sk definita prin: 1 misionar si 1 canibal pe malul de EST si 2 misionari si doi canibali pe malul de VEST, cele doua persoane de pe malul estic pot fi transportate imediat pe malul vestic, deci cu un cost unitar. In consecinta este mai mare decit costul real , deci h1 nu este admisibila. Functiile h2 si h3 sint admisibile si, in plus, sint monotone. Se poate demonstra ca functia h3 este mai informata decit h2, deci un algoritm A* care utilizeaza h3 va face mai putine treceri ale riului decit un algoritm A* care utilizeaza h2.
Relaxare