Bazele inteligenței artificiale

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.

In acest curs se prezinta 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.

3.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