Fig. 3.1. Vizitarea nodurilor arborelui cu ajutorul algoritmului greedy
În fig. 3.1. este prezentat un eventual spațiu de stări cu anumite aprecieri euristice pentru unele stări. Stările, în baza cărora a avut loc căutarea euristică, sînt marcate cu săgețile neîntrerupte puțin îngroșate. De menționat că căutarea nu a fost realizată în tot spațiul de stări. În acest sens scopul algoritmului GREEDY de căutare constă în găsirea stării necesare folosind cea mai scurtă cale. Cu cît este mai explicită euristica cu atît mai puține stări trebuie verificate în procesul de căutare.
În cazul fig. 3.1. căutarea a avut loc astfel pentru a găsi starea P:
Inițial a fost luat nodul a-5
Pentru nodul A-5 calculăm nodurile în care se poate căuta în continuare. Acestea sînt nodurile: B-4, C-4 și D-6.
Din cele în care am putea căuta alegem cel cu valoarea euristică cea mai mică. În cazul nostru avem 2 noduri: B-4 și C-4. Continuăm în ordinea apariției în listă, deci B-4.
Calculăm acum în care noduri putem continua căutarea. La cele existente pînă la moment: C-4 și D-6, mai adăugăm stările nodului B-4, și anume E-5 și F-5. În final am obținut stările: C-4, E-5, F-5 și D-6. Nodul cu care va continua căutare este C-4, așa cum are costul euristic cel mai potrivit.
Continuînd cu C-4, obținem următoarele stări la care putem ajunge: H-3, G-4, E-5, F-5, D-6. Analog procedînd continuăm cu nodul H-3.
Nodul H-3 ne dă următoare mulțime de noduri în care putem ajunge: O-2, P-3, G-4, E-5, F-5, D-6. Următoarea stare analizată va fi O-2.
Așa cum din O-2 nu mai putem ajunge, continuăm cu mulțimea din pasul anterior, în care se găsește starea P-3.
În acest fel am parcurs stările în următoarea consecutivitate: A-5, B-4, C-4, H-3, O-2 și P-3. De menționat că ordinea nodurilor parcurse nu corespunde cu calea. Dar calea poate fi reconstituită din noduri parcurse.
Algoritmul a*
Fig. 3.2. Găsirea soluției cu ajutorul algoritmului a*
Algoritmul GREEDY a fost îmbunătățit prin faptul că costul nodului f(n) a fost luată suma g(h)+h(n), unde g(n) este costul de la vîrful inițial la nodul n, plus costul euristic h(n) de la n la scop. Toate valorile funcțiilor g și h trebuie să fie pozitive. Evident că precizia funcției euristice reflectă cantitatea de informație pe care ea o incorporează relativ la domeniul problemei. O funcție h identic nulă reflectă lipsă totală de informație asupra problemei (cazul în care nu se poate face nici o estimare asupra aproprierii de soluție a unei stări).
Pentru exemplul jocului Perspico/8-puzzle, f(n) va fi egală cu numărul de plăcuțe care nu se află pe locul său plus numărul de fișe pînă la poziția finală. Rezultatele aplicării funcției de evaluare la fiecare etapă a căutării sînt alăturate schemei din fig. 3.2. într-un cerc. Se observă că în cazul algoritmului A* este necesar un număr semnificativ mai mic în găsirea stării căutate.
Caracteristicile algoritmului A* sînt:
A* se termină întotdeauna în grafuri finite;
dacă o cale există de la nodul start la o soluție, atunci A* se termină (chiar dacă graful e infinit);
A* e admisibil (adică, dacă există o cale de la nodul de start la un nod soluție, A* găseste o cale optimă).
Spunem că un algoritm A2 e mai informat decît A1, dacă, pentru toate nodurile n diferite de soluție, h2(n) > h1(n).
Dacă A1 și A2 sunt două versiuni ale lui A*, astfel încît A2 e mai informat decît A1, atunci la terminarea căutărilor lor pe orice graf în care există o cale de la nodul start la un nod soluție, orice nod expandat de A2 este de asemenea expandat și de A1. Urmează că A1 expandează cel puțin tot atîtea noduri ca și A2.