Metoda Branch and Bound

Metoda Branch and Bound

I.1.1         Descrierea metodei

Metoda Branch and Bound ("Ramifica si margineste") este inrudita cu metoda Backtracking in sensul ca spatiul solutiilor posibile are forma arborescenta. Similar, timpul de calcul este de regula exponential, ceea ce face ca metoda sa fie utilizata atunci cand nu se cunosc algoritmi alternativi mai rapizi.

Ca si in cazul metodei Backtracking, limitarea cautarii in spatiul solutiilor se face prin stabilirea unor conditii de continuare cu ajutorul carora se va alege, la fiecare pas, drumul cel mai promitator in arbore, adica drumul care are cele mai mari sanse de a conduce la o solutie rezultat. De regula, in cazul metodei Branch and Bound conditiile de continuare au la baza un criteriu de optimalitate, ce consta in minimizarea sau maximizarea unui indicator, in functie de problema concreta.

O diferenta substantiala intre cele doua metode este data de modalitatea in care este parcurs arborele solutiilor posibile, metoda Backtracking efectuand o parcurgere in adancime (de la radacina catre nodul terminal ce reprezinta solutia rezultat). Faptul ca la Branch and Bound se urmeaza de fiecare data cea mai promitatoare continuare face ca aici sa aiba loc un alt tip de parcurgere a arborelui solutiilor posibile.

Metoda Branch and Bound presupune utilizarea unei liste in care sunt asezate pre-solutii care nu au fost inca analizate. Acestea se numesc noduri active. Dintre acestea se alege un nod care urmeaza a fi prelucrat. De regula alegerea se face dupa un criteriu de optim Nodul ales se va numi nod curent. Odata ce nodul curent este prelucrat, el este eliminat din lista nodurilor active, in timp ce toti descendentii sai sunt inclusi in lista, ei constituind, alaturi de celelalte noduri din lista, posibile continuari -netestate inca- ale generarii solutiei rezultat.

I.1.2         Exemplu - Jocul Perspico

Fiind data o tabla de 4X4 pozitii in care se afla numerele de la 1 la 15 intr-o ordine oarecare data (figura V-16.a), una dintre casute ramanand astfel libera, sa se genereze sirul cel mai scurt de mutari ale casutei libere (sus/jos/stanga/dreapta) astfel incat sa se obtina o configuratie data, de exemplu cea din figura V-16.b), pe care o vom numi de aici incolo CF.

Fig. V . Configuratie initiala (a), Configuratie finala CF (b)

In primul rand, trebuie observat ca nu orice configuratie initiala poate duce la solutia finala. De exemplu, orice succesiune de mutari ale casutei libere am efectua, din configuratia prezentata in figura V-17) nu vom obtine niciodata solutia finala CF din figura V-16b).

Fig. V . Exemplu de configuratie initiala din care nu se poate obtine V-16b)

De aceea trebuie stabilite mai intai conditiile in care o configuratie accepta transformarea ceruta. In acest sens se va introduce o ordine intre cele 16 casute de pe tabla: pentru fiecare casuta cu numarul i, vom defini L(i) ca fiind numarul de casute aflate dupa ea (la dreapta si in jos) care au numere mai mici decat ea - vom considera ca in casuta libera se afla numarul 16.

Pentru exemplul de mai sus avem:

L(14)=1

L(9)=1

L(16)=9

L(11)=0

S-a demonstrat matematic urmatoarea propozitie:

O configuratie data poate fi transformata in configuratia finala CF daca si numai daca

este un numar par.

unde l si c sunt linia si coloana casutei libere numerotata cu 16.

Spatiul arborescent al solutiilor posibile va fi construit (recursiv) astfel: configuratia initiala este radacina arborelui; fiecare nod are cel mult patru fii obtinuti prin deplasarea casutei libere in sus, jos, la stanga sau la dreapta-atunci cand se poate efectua aceasta mutare.

Fig. V . Reprezentarea arborescenta a spatiului solutiilor

Asa cum arata exemplul considerat, o abordare a problemei cu metoda Backtracking ar fi inoportuna din doua motive: pe de o parte pentru ca arborele construit mai sus este infinit, efectuarea repetata, ciclica a unui set de mutari duce la crearea unui drum infinit, pe de alta parte o parcurgere sistematica ("orbeasca") in adancime necesita un numar foarte mare de pasi, in timp ce problema de mai sus se rezolva in numai trei pasi, prin succesiunea de mutari: jos, dreapta, jos. De aceea trebuie imaginata o metoda care sa aleaga intre pozitiile obtinute la un moment dat pe aceea care "pare" a fi mai apropiata de starea finala. Prelucrarea celorlalte pozitii va fi amanata si nu se va renunta la ele, intrucat este posibil ca alegerea facuta sa nu conduca la rezultatul final.

Prin urmare, se impune definirea unei functii de cost pe multimea nodurilor arborelui, functie care sa poata fi evaluata de sus in jos, pe masura ce arborele solutiilor posibile se ramifica. O alegere naturala ar fi considerarea functiei de cost:

c(nod)=lungimea drumului de la radacina la nod + numarul de casute care nu se afla la locul lor.

Cu ajutorul acestei functii de cost vom aprecia cat de aproape suntem de solutia finala si cat de multe mutari am efectuat deja (informatia prezinta interes atata vreme cat ni se cere un numar minim de mutari). Un numar prea mare de mutari sau un numar mare de casute ce nu sunt la locul lor duc la alegerea spre continuare a unei alte stari active.

Odata ce asemenea functie de cost a fost definita, la fiecare pas se va alege drept nod curent acel nod activ cu cost minim. O astfel de parcurgere a spatiului starilor se numeste LC-parcurgere (Least Cost = Cost Minim).

Pentru exemplul considerat, starile succesive ale listei nodurilor active au fost reprezentate mai jos:

Se introduce configuratia initiala in lista

Se elimina singurul nod din lista si se adauga cei patru fii ai sai (pana cand se ajunge la configuratia ceruta). Adaugarea s-a facut la sfarsitul listei.

Se alege nodul cu cel mai mic cost -cel cu costul 4-; daca sunt mai multe noduri cu cost minim se considera unul oarecare dintre ele, daca acesta nu duce la solutia finala, atunci se va reveni si la celelalte. Se elimina din lista nodul de cost 4 si se adauga fiii sai.

Se identifica nodul de cost minim, se sterge din lista si se adauga fiii sai. Se observa ca fiul obtinut prin deplasarea casutei libere in jos este chiar configuratia ceruta, astfel ca algoritmul se incheie.

Din punctul de vedere al complexitatii, metoda Branch and Bound are asociat un timp de calcul exponential, ca si metoda Backtracking dealtfel, aceasta datorita ramificarii sale arborescente. Aceasta face ca metoda sa fie utilizata numai atunci cand nu exista algoritmi alternativi polinomiali.

Un algoritm general de rezolvare este dat de:

Din punctul de vedere al complexitatii, metoda Branch and Bound are asociat un timp de calcul exponential, ca si metoda Backtracking dealtfel, aceasta datorita ramificarii sale arborescente. Aceasta face ca metoda sa fie utilizata numai atunci cand nu exista algoritmi alternativi polinomiali.

I.1.3         Aplicatii

Jocul Perspico

Enuntul aplicatiei a fost prezentat mai sus.

Solutie: Pentru simplificare, in locul listei a fost folosit un vector. Pentru ca un nod (element din vector) sa nu fie vizitat de doua ori costul sau a fost ridicat la un numar foarte mare (1e6 ). Fiecare nod contine trei campuri: configuratia curenta a tablei, sirul de mutari prin care a fost obtinuta si costul sau. Se poate observa ca odata ce cunoastem mutarile efectuate nu va mai fi necesar sa includem si configuratia curenta, putem crea o functie care sa genereze tabla dupa un sir dat de mutari. Lasam cititorul sa experimenteze aceasta modalitate de rezolvare.

Jocul Perspico

#include<iostream.h>

#include<string.h>

#define X 16

struct TNod;

TNod active[1500];

int n;//numar noduri

void CautaX (int A[][4], int& l, int& c)

int solv(int A[][4])

int cost(int A[][4])

int Mutare(int tata, char directie)

//adauga un nod activ nou, descendent din tata

//obtinut prin mutarea casutei libere in directia specificata

//intoarce 1 daca a fost obtinuta configuratia finala, 0 altfel

}

int l,c, cont;char dir[]=' ';

CautaX(active[tata].A,l,c);// caut X de coordonate (l, c)

//daca nu se poate efectua deplasarea casutei libere in directia dorita renuntam

if((directie=='u'&&l==0)||(directie=='r'&&c==3)||(directie=='d'&&l==3)||(directie=='l'&&c==0))

return 0;

// copiem starea curenta a casutelor (matricea)

for(int i=0;i<16;i++)

active[n].A[i/4][i%4]=active[tata].A[i/4][i%4];

// deplasam casuta libera (l,c) cu (l+1,c)

int temp=active[n].A[l][c];

switch(directie)

// adaugam noua configuratie in lista

active[n].sol=new char[strlen(active[tata].sol)+2];

strcpy(active[n].sol,active[tata].sol);

dir[0]=directie;

strcat(active[n].sol,dir);

if((cont=cost(active[n].A))==0/*sfarsit*/)

active[n].cost=strlen(active[n].sol)+cont;

n++;

return 0;

void Perspico()while(1);

void main()

//inseram configuratia initiala in lista

for(int i=0;i<16;i++)

active[0].A[i/4][i%4]=A[i/4][i%4];

active[0].sol=new char;

active[0].sol[0]='0';

active[0].cost=cost(A);

n=1;

if(active[0].cost==0)

cout<<'Aceasta este solutia finala!';

else

if(solv(A))

else

cout<<'problema nu are solutie';