Metoda Branch and Bound

Extras din referat Cum descarc?

Prezentarea metodei Branch and bound
Metoda Branch and Bound foloseste la rezolvarea problemelor la care domeniul in care se cauta solutia este foarte mare si nu se cunoaste un alt algoritm care sa conduca mai rapid la rezultat. Problemele care pot fi abordate prin aceasta metoda pot fi modelate intr-un mod asemanator celui folosit la metoda Backtracking. Se pleaca de la o configuratie initiala si se retine sirul de operatii prin care aceasta este transformata intr-o configuratie finala daca aceasta este data, in alte cazuri se cere configuratia finala stiind ca trebuie sa verifice anumite conditii de optim.
Diferenta dintre cele doua metode consta in faptul ca metoda Backtracking la fiecare etapa selecteaza un singur succesor dupa care se face verificarea conditiilor de continuare, iar metoda Branch and Bound genereaza la fiecare pas toate configuratiile posibile (toti succesorii) care rezulta din cea curenta si le stocheaza intr-o lista. Se alege apoi un element din lista dupa un criteriu ce depinde de problema si se reia procesul de expandare.
Alegerea optima a unui element din aceasta lista pentru expandare se face cu ajutorul unei functii f = g + h in care g este o functie care masoara lungimea drumului parcurs de la configuratia initiala pana la nodul curent iar h este o functie (euristica) care estimeaza efortul necesar pana se ajunge la solutie si este specifica fiecarei probleme. Alegerea functiei h este foarte importanta din punct de vedere a vitezei de executie a programului.
Se lucreaza cu doua liste: lista open in care se retin configuratiile neexpandate inca si lista close care le memoreaza pe cele expandate. Solutia se construieste folosind un arbore care se parcurge pe baza legaturii tata.
Nodurile sunt inregistrari care cuprind urmatoarele informatii:
- configuratia la care s-a ajuns, t;
- valorile functiilor g si h,
- adresa nodului 'tata';
- adresa inregistrarii urmatoare in lista open sau close;
- adresa inregistrarii urmatoare in lista succesorilor. 
Algoritmul:
1. inregistrarea corespunzatoare configuratiei initiale este incarcata in open cu g=0 si f=h;
2. atat timp cat nu s-a selectat spre expandare nodul corespunzator configuratiei finale si lista open este nevida, se executa urmatoarele:


Fisiere in arhiva (1):

  • Metoda Branch and Bound.docx

Imagini din acest proiect Cum descarc?

Descarca gratuit aceast referat (0 €)

Completezi numele, prenumele și adresa de email. După aceea primesti prin email link-ul pentru descărcare. Completeaza o adresă de email validă.

1. Numele, Prenumele si adresa de email:

Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.



Hopa sus!