Obtinerea solutiei optime pentru reprezentarea prin descompunerea problemei in subprobleme se poate realiza cu un algoritm similar ca idee cu algoritmul A*. Diferenta intre cei doi algoritmi consta in natura solutiei problemei, respectiv prezenta nodurilor ŞI care indica o multime de subprobleme ce trebuie rezolvate. Aspectele specifice care trebuie considerate in cazul unei solutii arbore SI/SAU sunt:
- Cum poate fi utilizata informatia euristica in cautarea solutiei optime
- Cum se defineste o solutie optima
La executia unui algoritm de cautare de tip "best-first" in spatiul starilor exista o corespondenta de unu la unu intre nodurile candidate la expandare si solutiile partiale construite. La un moment dat, toate solutiile partiale potentiale sunt reprezentate prin caile descoperite de la starea initiala la starile din FRONTIERA, fiecare dintre aceste cai fiind reprezentate printr-un nod unic in FRONTIERA. in cazul cautarii solutiei intr-un graf ŞI/SAU aceasta corespondenta de unu la unu intre nodul ales spre expandare si solutia potentiala de extins nu se mai pastreaza. Fiecare solutie partiala poate contine mai multe noduri candidate la expansiune si un nod dat poate face parte din mai multi arbori solutie potentiali. De exemplu, expandarea nodului ŞI S din Figura 2.12(a) inseamna generarea a doi arbori solutie potentiali, cel din Figura 2.12(b), respectiv cel din Figura 2.12(c).
Figura 2.12 Extinderea solutiei potentiale intr-un arbore ŞI/SAU
In aceste conditii, informatia euristica poate fi utilizata in doua etape ale cautarii. in primul rand se identifica solutia cea mai promitatoare prin utilizarea unei functii de evaluare a grafului f. in al doilea rand se selecteaza din aceasta solutie partiala nodul urmator de expandat pe baza unei functii de evaluare a nodurilor fn. Aceste doua functii, cu doua roluri diferite, ofera doua tipuri de estimari: f estimeaza proprietatile arborilor solutie care pot fi generati dintr-un arbore candidat curent, in timp ce fn estimeaza cantitatea de informatie pe care o poate oferi expandarea unui nod cu privire la superioritatea grafului ce contine acel nod. Functia f este cea care stabileste optimalitatea solutiei pe baza unor costuri asociate procesului de descompunere a problemei in subprobleme.
