mihaispr
Administrator
 Inregistrat: acum 18 ani
Postari: 2142
|
|
Cuprins:
1. Enuntul problemei misionarilor si canibalilor……… .pag 3
2. Descrierea succinta a strategiei de cautare pe nivel…………………………………………………..pag 3-5
3. Reprezentarea unei stari a problemei implementate in limbajul C………………………………………………………pag 6
4. Descrierea operatorilor de transformare a starilor problemei………………………………………………pag 6-7
5. Complexitatea strategiei de cautare……………………………………………… …pag 7-8
6. Rezolvarea problemei misionarilor si canibalilor din punct de vedere practic…………………………………………………..pag 8-9
1. Enuntul problemei misionarilor si canibalilor
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. Nu mai mult de doi oameni pot încăpea în barcă şi trebuie să aibă cel puţin o persoană în cursul oricarui transport.
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 pe nivel.
2. Descrierea succinta a strategiei de cautare pe nivel
Strategia de căutare pe nivel (în lăţime, breadth-first search) este o strategie de căutare
neinformată.
Strategia de căutare pe nivel începe expandarea cu nodul rădăcină, apoi expandează toate
nodurile generate de rădăcină şi continuă similar expandarea cu toţi succesorii acestora etc.
Implementarea strategiei de căutare pe nivel se realizează particularizând strategia generală
de căutare prin implementarea listei FRONTIERA sub formă de coadă.
La strategia de cautare pe nivel, fiecare stare de pe un anumit nivel este expandata inainte de a trece pe urmatorul nivel de stari. În diagrama de mai sus se poate observa că nodul radacina numit Root a fost extins pentru a gasi succesorii A1, A2 şi A3.
La acest nivel nu mai exista stari prin urmare A1 este ales si expandat .
Nu au existat mai multe stari, la acest nivel, asa ca A1 a fost preluat şi expandat, rezultand succesorii A1.1 ,A1.2 si A1.3. In continuare, A2 şi A3 trebuie, de asemenea, să fie expandate, înainte de a trece la noile stari A1.1 ,A1.2 si A1.3, deci A2 şi A3 va fi extins în continuare.
Dacă nu există mai multe stari, la nivelul actual de extindere, primul nod de pe nivelul următor este expandat, aceast lucru se intampla pana cand o solutie sau mai multe solutii sunt gasite.
Aceasta reprezinta strategia de cautare pe nivel.
Sinteza pentru strategia de cautare pe nivel
Strategia de căutare pe nivel (în lăţime, breadth-first search) este o strategie de căutare neinformată.Strategia de căutare pe nivel începe expandarea cu nodul rădăcină, apoi expandează toate nodurile generate de rădăcină şi continuă expandarea cu toţi succesorii acestora etc.
Implementarea strategiei de căutare pe nivel se realizează particularizând strategia generală de căutare prin implementarea listei FRONTIERA sub formă de coadă.
Algoritm
1. iniţializează listele FRONTIERA ←{} ş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. 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 FRONTIERA TERITORIU atunci
/*evită reconsiderarea unei stări anterior generate*/
inserează Sj în FRONTIERA, la sfârşit
5. repetă de la pasul 2
Sfârşit
În cazul în care soluţia există, algoritmul întoarce soluţia cale de lungime minimă.
Caracteristici
Căutarea pe nivel este completă.
Căutarea pe nivel este optimală.
Complexitatea strategiei este exponenţială.
3. Reprezentarea unei stari a problemei implementate in limbajul C
Stările problemei
Starea iniţială
Luam ca sistem de referinta malul stang.
(3,3,1) – se afla initial 3 misionari, 3canibali si 1 barca pe malul stang
Starea finală
Este data de ceea ce ramane pe malul stang in urma transpoartelor efectuata pe malul drept. In cazul acestei probleme este (0,0,0) (0misionari, 0 canibali si 0 notatie atunci cand barca se afla pe malul drept)
Spatiul starilor
Este aratat in figura de mai jos:
4. Descrierea operatorilor de transformare a starilor problemei
Operator
Este dat de modul de ocupare al barcii.
Un operator in C este definit mai jos:
typedef int Operator[3];
//operator dat de perechea (M,C,B) unde M-nr.misionari,C-nr.canibali,B-directia barcii
Obs. Consideram ca sistem de referinta malul stang.
//notam cu 1 directia barcii(cand se deplaseaza de pe malul stang pe malul drept)
//notam cu -1 directia barcii(cand se deplaseaza de pe malul drept pe malul stang)
typedef Operator multime[11]
Operator OcupareBarca={ {0,2,1},{0,1,-1},{0,2,1},{0,1,-1},{2,0,1},{1,1,-1},{2,0,1},
{0,1,-1},{0,2,1},{0,1,-1},(0,2,1) }
5. Complexitatea strategiei de cautare
Strategii de cautare de baza
Criterii de caracterizare:
- Completitudine
- Optimalitate
- Complexitate
A. Completitudinea
- daca garanteaza o solutie in cazul in care aceasta exista
B. Optimalitatea
- daca gaseste o solutie optima
C. Complexitatea
- este de doua categorii : spatiu si timp
Complexitatea în spaţiu se referă la volumul de memorie necesar calculelor, iar cea în timp se referă la timpul necesar efectuării calculelor, ambele fiind exprimate ca funcţii de n, unde n este mărimea datelor de intrare.
6. Rezolvarea problemei canibalilor din punct de vedere practic
Sa presupunem ca mal de referinta malul stang, mal pe care se afla 3misionari, 3canibali si 1 barca. Deci starea curenta este 3,3,1 dorim sa mutam convenabil cei 3 misionari si canibali pe malul drept a.i canibalii sa nu manance misionarii(deci nr.canibali<=nr.misionari).
Deci starea finala va fi 0,0,0 pe malul stang.
Cand barca se afla pe malul drept va fi 0(valoare false am folosit in program variabila mal de tip bool) cand barca se afla pe malul stang va fi 1( valoare true).
In plus se stie ca la fiecare transport efectuat barca nu poate transporta decat 2 oameni.
Rezolvarea din punct de vedere practic a problemei misionarilor si canibalilor implica efectuare de trasporturi astfel incat pe malul stang sa nu mai ramana nici un misionar, nici un canibal si barca se va afla pe malul drept deci starea finala va fi 0,0,0.
Iata si ordinea transporturilor care trebuiesc efectuate si care conduce la rezolvarea problemei misionarilor si canibalilor:
Transport 1: Se iau 2 canibali in barca si se lasa unul pe malul drept
Transport 2: Barca se intoarce cu un canibal
Transport 3: Se iau 2 canibali in barca si se lasa unul pe malul drept
Transport 4: Barca se intoarce cu un canibal
Transport 5: Se iau 2 misionari si se lasa unul pe malul drept
Transport 6: Barca se intoarce cu 1 misionar si 1 canibal si se lasa canibalul pe malul drept
Transport 7: Se iau 2misionari si se lasa ambii pe malul drept
Transport 8: Barca se intoarce cu un canibal
Transport 9: Se iau 2 canibali si se lasa unul pe malul drept
Transport 10: Barca se intoarce cu un canibal
Transport 11: Se iau 2 canibali in barca si se lasa ambii pe malul drept
|
|
