Mihai Sprinceana
Un forum de programare cu de toate. Va astept sa va inscrieti si sa deveniti moderatori. Oricine este binevenit aici sa se inscrie si sa aiba acces la informatie free! Fiecare este liber sa adauge proiecte programe free etc. Ajutati acest forum sa devina o comunitate puternica unde fiecare invata de la fiecare! Tot ce trebuie sa faceti este sa va inregistrati si fiecare contributie se poate dovedi utila in timp! Forumul este free informatia free dk aveti timp liber ajutati si pe ceilalti si invatati si voi in acelasi timp! Haideti sa facem ceva pt.a ne ajuta intre noi!
Cititi regulament postare forum inainte de a posta!
|
Lista Forumurilor Pe Tematici
|
Mihai Sprinceana | Inregistrare | Login
POZE MIHAI SPRINCEANA
Nu sunteti logat.
|
Nou pe simpatie:
Lolo 24 ani
 | Femeie
24 ani
Galati
cauta Barbat
25 - 52 ani |
|
mihaispr
Administrator
 Inregistrat: acum 18 ani
Postari: 2142
|
|
Cuprins
I. Enuntul problemei .......................................................... pag. 3
II. Descrierea problemei ..................................................... pag. 3
III. Descrierea strategiei de cautare aplicata ....................... pag. 5
IV. Starile problemei ............................................................. pag. 6
V. Implementarea algoritmului de cautare in adancime ...... pag. 7
VI. Costul solutiei si solutia gasita ........................................ pag. 8
I. Enuntul problemei
Problema misionarilor şi canibalilor: 3 misionari şi 3 canibali se află pe unul dintre malurile unui râu, împreună cu o barcă ce poate trasporta la un moment dat unul sau doi oameni. Se cere să se găsească o modalitate de a-i transporta pe toţi pe celălalt mal, fără a permite la vreun transport ca numărul de canibali dintr-o locaţie să depăşească numărul de misionari. Problema se va rezolva folosind strategia de căutare în adâncime.
II. Descrierea problemei
Trei misionari si trei canibali se afla de o parte a raului. Ei au o barca ce poate duce cel mult doi oameni. Va trebui sa gasim o posibilitate asa incat sa traverseze toti de cealalta parte a raului cu conditia sa nu existe mai multi canibali decat misionari intr-o parte.
Descrierea starii curente: o secventa de 6 numere, reprezentand numarul misionarilor, al canibalilor si barcilor de pe fiecare mal al raului. Plecand de la premisa ca sunt 3 canibali, 3 misionari si o barca, starea initiala va fi (3,3,1,0,0,0).
Stari: secvente ordonate de 3 numere reprezentand numarul de misionari, canibali si barci de partea in care se aflau initial (3, 3, 1).
Actiuni: mutarea unui misionar sau canibal sau 2 canibali, 2 misionari sau un misionar si un canibal de pe o parte pe alta.
Testarea tintei: starea (0, 0, 0).
Costul drumului: numarul de traversari.
Reprezentare grafica:
Lista transpoartelor ce trebuie efectuate este prezentata mai jos:
Descrierea strategiei de cautare aplicata
Strategia de cautare in adancime limitata
Strategia de căutare în adâncime limitată (depth-first search) este o strategie de căutare neinformată.
Strategia expandează întotdeauna ultimul nod adăugat arborelui (aflat pe nivelul cel mai adânc). Căutarea revine pe nivelele anterioare numai atunci când s-a blocat (a apărut un nod care nu e nodul scop şi care nu poate fi expandat sau s-a ajuns la adâncimea maximă impusă .
Implementarea strategiei de căutare pe nivel se realizează particularizând strategia generală de căutare prin implementarea listei FRONTIERA sub formă de stivă.
Algoritm
1. iniţializează listele FRONTIERA ←{Si} şi TERITORIU ←{}
2. dacă FRONTIERA={} atunci
întoarce INSUCCES /*nu există soluţie*/
3. elimină primul nod S din FRONTIERA şi inserează-l în TERITORIU
4. daca adancime(S) = Hmax atunci repeta de la pasul 2
4. expandează nodul S
4.1. generează toţi succesorii direcţi Sj ai nodului S
4.2. pentru fiecare succesor Sj (1≤j≤n) al lui S execută
4.2.1. stabileşte legătura Sj → S
4.2.2. dacă Sj este stare finală atunci
i. soluţia este (Sj, S, ..., Si)
ii. întoarce SUCCES /* a fost găsită soluţia */
4.2.3. dacă Sj ≠ toate stările anterior generate în
soluţia parţială curentă atunci
inserează Sj în FRONTIERA, la inceput
5. repetă de la pasul 2
Sfârşit
Dezavantajul căutării este posibilitatea blocării într-o cale greşit aleasă.
Caracteristici:
• Complexitatea in spatiu: b*d, unde b=factor de ramificare si d=adancimea cautarii
• Complexitatea in timp: bd.
• Căutarea nu este completă.
• Căutarea nu este optimală.
• Complexitatea timp este exponenţială, iar complexitatea spaţiu este polinomială.
IV. Starile problemei (tratarea in program)
//verifica daca nr misionarilor>=0, nr canibalilor>=0 si misionari>=canibali
bool Stare::EValid()
{ //verifica daca nr misionarilor>=0, nr canibalilor>=0 si misionari>=canibali
if (MisDreapta==0)
{
if ((MisStanga>=CanStanga) && (MisStanga>=0) &&
(CanDreapta>=0) && (CanStanga>=0))
return (true);
else
return (false);
}
else
{
if (MisStanga==0)
{
if ((MisDreapta>=CanDreapta) && (MisDreapta>=0) &&
(CanDreapta>=0) && (CanStanga>=0))
return (true);
else
return (false);
}
else
{
if ((MisDreapta>=CanDreapta) && (MisStanga>=CanStanga) &&
(MisDreapta>=0) && (MisStanga>=0) &&
(CanDreapta>=0) && (CanStanga>=0))
return (true);
else
return (false);
}
}
}
//verifica daca starea gasita coincide cu starea obiectiv, cea cautata, adica starea: ML=3, MR=0, CL=3, CR=0, B=0. (0,0,0)
bool Stare::EScop()
{
if ((MisStanga==3) && (CanStanga==3)
&& (MisDreapta==0) && (CanDreapta==0)
&& (Barca==stanga))
{
return (true);
}
else
return (false);
}
V. Implementarea algoritmului de cautare in adancime
void Stare::CautaAdancime()
{//algoritmul cautarii in adancime
Stare* ChildQueuePtr;
ChildQueuePtr=new Stare;
ChildQueuePtr=NULL;
if (Gasit) //verifica daca trebuie oprita recursivitatea (recursion)
return;
NumStare++;
PrintStare();
if (!EScop()) //daca nu este starea obiectiv
{
ChildQueuePtr=GetChildQueue(); //creeaza coada copil pentru
//aceasta stare
while (!ChildQueuePtr==NULL)
{
ChildQueuePtr->CautaAdancime(); //cautare in adancime
//recursiva la inceputul cozii copil
ChildQueuePtr=ChildQueuePtr->next; //se deplaseaza cu
//coada copil
}
return;
}
else
{
cout<<"Am gasit!!!"<<endl;
cout<<"Am trecut prin "<<NumStare<<" stari"<<endl;
Gasit=true; //seteaza Gasit=true pentru a opri recursivitatea
return;
}
}
VI. Costul solutiei si solutia gasita
Costul drumului, costul solutiei gasite, este reprezentat de numarul de stari ale acesteia. In cazul nostru acesta este 12.
Solutia gasita:
ML:0 MR:3 CL:0 CR:3 B:1
ML:0 MR:3 CL:2 CR:1 B:0 Mutare: 2C
ML:0 MR:3 CL:1 CR:2 B:1 Mutare: 1C
ML:0 MR:3 CL:3 CR:0 B:0 Mutare: 2C
ML:0 MR:3 CL:2 CR:1 B:1 Mutare: 1C
ML:2 MR:1 CL:2 CR:1 B:0 Mutare: 2M
ML:1 MR:2 CL:1 CR:2 B:1 Mutare: 1M,1C
ML:3 MR:0 CL:1 CR:2 B:0 Mutare: 2M
ML:3 MR:0 CL:0 CR:3 B:1 Mutare: 1C
ML:3 MR:0 CL:2 CR:1 B:0 M: 2C
ML:2 MR:1 CL:2 CR:1 B:1 M: 1M
ML:3 MR:0 CL:3 CR:0 B:0 M: 1M,1C
Am gasit!!!
Am trecut prin 12 stari
|
|
| pus acum 17 ani |
|
