Problema Iesirii dintr-un Labirint

Extras din referat Cum descarc?

1) Enuntul 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 cautare A* este o strategie de cautare informata care incearca reducerea numarului de noduri generate din spatiul de cautare, pe baza unor anumite criterii cum sunt euristicile.
Acest obiectiv include si problema gasirii caii spre solutie care presupune aplicarea unui numar minim de operatori.
Strategia de cautare A* incepe expandarea cu nodul radacina, genereaza toti succesorii acestui nod si calculeaza functia euristica specifica fiecaruia. Apoi expandeaza acel succesor a carei functie euristica are valoarea minima si continua similar expandarea cu toti succesorii acestuia etc.
3) Reprezentarea unei stari a problemei (implementare in limbajul C)
Stari ale problemei:
Starea initiala: 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 finala: 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: miscarile la Est, Vest, Nord si respective Sud prin labirint
4) Descrierea operatorilor de transformare a unei stari a problemei (prototipurile functiilor C si implementarea lor)
Din fiecare stare persoana din labirint se poate deplasa in labirint in Nord, in Sud, in Est sau in 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 completa si optimala daca functia h este euristica admisibila, adica nu supraestimeaza niciodata costul atingerii scopului.
6) Functia euristica utilizata
In stategia de cautare A* functia de evaluare euristica este o functie aditiva:
f(S) = g(S) + h(S),
unde:
g(S) - reprezinta costul solutiei partiale (Si, ..., S)
h(S) - estimata distantei de la starea curenta la starea scop (S,..., Sf)
Si - starea initiala
S - starea curenta
Sf - starea finala (scop)
Functia g(S) reprezinta costul drumului parcurs de la starea initiala pana la starea curenta S.
g(S) = , unde Sn este starea S.
Functia h(S) trebuie definita de catre programator, ea fiind specifica fiecarei probleme in parte. 
Algoritm
1. initializeaza listele FRONTIERA <-{Si} si TERITORIU <-{}
2. calculeaza f(Si) si asociaza aceasta valoare nodului Si
3. daca FRONTIERA={} atunci
intoarce INSUCCES /*nu exista solutie*/
4. selecteaza din FRONTIERA un nod S pentru care f(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(S,..., Si), prin trasarea caii de-a lungul pointer-ilor de la scop inapoi la starea initiala, Si
6.2 intoarce SUCCES /* s-a gasit solutia problemei */
7. expandeaza nodul S


Fisiere in arhiva (3):

  • Problema Iesirii dintr-un Labirint
    • LABIRINT.CPP
    • LABIRINT.TXT
    • Problema Iesirii dintr-un Labirint.doc

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!