Problema Ieșirii dintr-un Labirint

1) Enunţul temei:

Se da un labirint sub forma de matrice cu m linii si n coloane. Fiecare element al matricei reprezinta o camera a labirintului (1 pentru zid si 0 pentru drum liber). Intr-una din camere, de coordonate xs si ys se afla o persoana. Determinati drumul minim pe care il parcurge persoana pentru a iesi din labirint.

2) Descrierea strategiei aplicate

Strategia de căutare A* este o strategie de căutare informată care încearcă reducerea numărului de noduri generate din spaţiul de căutare, pe baza unor anumite criterii cum sunt euristicile.

Acest obiectiv include şi problema găsirii căii spre soluţie care presupune aplicarea unui număr minim de operatori.

Strategia de căutare A* începe expandarea cu nodul rădăcină, generează toţi succesorii acestui nod şi calculează funcţia euristică specifică fiecăruia. Apoi expandează acel succesor a cărei funcţie euristică are valoarea minimă şi continuă similar expandarea cu toţi succesorii acestuia etc.

3) Reprezentarea unei stări a problemei (implementare în limbajul C)

Stari ale problemei:

Starea iniţiala: avem o matrice de m linii si n coloane reprezentand harta labirintului :

6 10

0 0 1 0 0 1 0 0 1 0

0 1 0 0 1 0 0 1 1 1

0 0 0 1 0 0 1 0 1 0

0 1 0 0 0 0 0 0 1 0

1 1 0 1 0 1 0 1 0 1

0 0 1 0 1 1 0 1 1 1

coordonatele initiale :

xs=

ys=

Starea finală: calculatorul afiseaza solutia corespunzatoare iesirii din labirint :

6 10

0 0 1 0 0 1 0 0 1 0

0 1 0 0 1 0 0 1 1 1

0 0 0 1 0 0 1 0 1 0

0 1 0 0 0 0 0 0 1 0

1 1 0 1 0 1 0 1 0 1

0 0 1 0 1 1 0 1 1 1

coordonatele initiale :

xs=4

ys=6

SUCCES!!!

Pozitie omulet : (6,7)

Pozitie omulet : (5,7)

Pozitie omulet : (4,7)

Pozitie omulet : (4,6)

Operatorii de tranzitie dintr-o stare in alta sunt: mişcările la Est, Vest, Nord şi respective Sud prin labirint

4) Descrierea operatorilor de transformare a unei stări a problemei (prototipurile funcţiilor C şi implementarea lor)

Din fiecare stare persoana din labirint se poate deplasa in labirint în Nord, în Sud, în Est sau în Vest, pentru a se deplasa spre iesirea din labirint.

Urmatoarele instructiuni fac parte din functia parcurgere_a_star() :

if (l>0 && a[l-1][c]==0) //muta sus

{

nr_noduri++;

succesor=adaugare(succesor,l-1,c,nr_noduri,nrcrt,0);

}

if (l<n-1 && a[l+1][c]==0) //muta jos

{

nr_noduri++;

succesor=adaugare(succesor,l+1,c,nr_noduri,nrcrt,0);

}

if (c>0 && a[l][c-1]==0) //muta stanga

{

nr_noduri++;

succesor=adaugare(succesor,l,c-1,nr_noduri,nrcrt,0);

}

if (c<m && a[l][c+1]==0) //muta dreapta

{

nr_noduri++;

succesor=adaugare(succesor,l,c+1,nr_noduri,nrcrt,0);

}

5) Complexitatea strategiei de cautare

Strategia A* este completă şi optimală dacă funcţia h este euristică admisibilă, adică nu supraestimează niciodată costul atingerii scopului.

6) Functia euristica utilizata

În stategia de căutare A* funcţia de evaluare euristică este o funcţie aditivă:

f(S) = g(S) + h(S),

unde:

g(S) – reprezintă costul soluţiei parţiale (Si, ..., S)

h(S) – estimata distanţei de la starea curentă la starea scop (S,..., Sf)

Si – starea iniţială

S – starea curentă

Sf – starea finală (scop)

Funcţia g(S) reprezintă costul drumului parcurs de la starea iniţială până la starea curentă S.

g(S) = , unde Sn este starea S.

Funcţia h(S) trebuie definită de către programator, ea fiind specifică fiecărei probleme în parte.

Algoritm

1. iniţializează listele FRONTIERA ←{Si} şi TERITORIU ←{}

2. calculeaza f(Si) şi asociază această valoare nodului Si

3. dacă FRONTIERA={} atunci

întoarce INSUCCES /*nu există soluţie*/

4. selectează din FRONTIERA un nod S pentru care f(S) este minimă

5. elimină nodul S din FRONTIERA şi inserează-l în TERITORIU

6. dacă S este starea finală atunci

6.1. construieşte soluţia(S,..., Si), prin trasarea căii de-a lungul pointer-ilor de la scop înapoi la starea iniţială, Si

6.2 întoarce SUCCES /* s-a găsit soluţia problemei */

7. expandează nodul S