Metoda branch and bound

Metoda branch and bound

Prezentarea metodei

Metoda branch and bound (in traducere "ramifica si margineste") este inrudita cu metoda backtracking prin faptul ca se poate reprezenta pe un arbore radacina.

Un nod reprezinta o solutie posibila numita si stare posibila.

Arborele atasat metodei branch and bound se numeste arbore radacina al spatiului de stari posibile pe care, in continuare, il numim arbore branch and bound. De asemenea, arborele radacina atasat metodei backtracking il numim arbore backtracking.

Principalele deosebiri dintre metodele backtracking si branch and bound constau in urmatoarele:

arborele branch and bound poate fi finit sau infinit;

arborele branch and bound poate avea noduri distincte care corespund aceleasi stari;

arborele branch and bound este parcurs BF (Breadth First = mai intai in latime) sau D (Depth = in adancime), in schimb arborele backtrackig este parcurs DF (Depth First = mai intai in adancime).

O stare admisibila este o stare posibila care verifica anumite conditii.

Problema consta in determinarea drumului minim de la o stare posibila data la starea admisibila. Pentru rezolvarea acestei probleme metoda branch and bound foloseste o lista L in care se inregistreaza noduri pentru a fi prelucrate ulterior. Nodurile din aceasta lista se numesc noduri active si nodul selectat pentru prelucrare se numeste nod curent.

In rezolvarea unor probleme cu metoda branch and bound parcurgerile BF si D ale arborelui asociat, nu sunt eficiente. In acest caz, trebuie selectat din lista L nodul cu cele mai multe sanse de a se afla mai aproape de nodul admisibil. Pentru aceasta se defineste functia cost c : N R , unde N este multimea nodurilor din arborele branch and bound G = (N, A ). Daca functia cost c este stabilita, atunci nodul curent este nodul cu costul minim. Aceasta parcurgere a arborelui branch and bound se numeste parcurgere LC (LeastCost = cost minim).

Functia c ideala este definita astfel:

Functia c este ideala din urmatoarele doua consideratii:

daca arborele branch and bound este infinit atunci ea nu poate fi calculata;

daca arborele branch and bound este finit atunci calculul ei necesita parcurgerea arborelui in totalitate, ceea ce de fapt dorim sa evitam.

Dacǎ functia c este calculatǎ, atunci pentru a ajunge la o stare admisibilǎ, este suficient sǎ determinǎm un drum de la nodul rǎdǎcinǎ r (solutia posibilǎ datǎ), la un nod admisibil y format din noduri x cu c(x) = c(r).

Deoarece functia c este idealǎ, se determinǎ o functie care aproximeaza pe c pentru fiecare problemǎ in parte. Functia trebuie sǎ indeplineasca conditiile:

sǎ poata fi calculatǎ pentru orice nod x cunoscand numai informatiile atasate nodurilor ascendente nodului x;

sǎ nu omita anumite noduri necesare la determinarea solutiei admisibile;

sǎ nu permita sǎ se mearga prea mult in adancime in cazul arborilor infiniti.

Metoda branch and bound este prezentatǎ in procedura BB:

PROCEDURA BB(G') ;

BEGIN

L :=  ;

WHILE L DO

se extrage i din L;

FOR fiecare nod j succesor al lui i DO

IF j este nod admisibil THEN

BEGIN

WRITE (D); EXIT;

END

ELSE

BEGIN

j este introdus in L; p(j) := i;

END;

ENDIF;

IF j este nod admisibil THEN

EXIT;

ENDIF;

ENDWHILE;

END;

Notatiile din procedura BB au urmatoarele semnificatii :

G este arborele branch and bound;

L este lista nodurilor active;

r este nodul rǎdǎcinǎ al arborelui G

j este succesorul nodului i;

D este drumul de la nodul rǎdǎcinǎ r la nodul admisibil j;

p este tabloul predecesor cu care se determinǎ drumul D;

Dupǎ modul de parcurgere a arborelui radacina, lista L trebuie organizata in modul urmator:

daca se efectueaza parcurgerea BF atunci lista L trebuie organizata ca o coada;

daca se efectueaza parcurgerea D atunci lista L trebuie organizata ca o stiva;

daca se efectueaza parcurgerea LC atunci lista L trebuie organizata ca un ansamblu (heap) cu functia prioritara functia .

Dacǎ arborele este finit, atunci metoda branch and bound converge intr-un numǎr finit de iteratii, indiferent care dintre cele trei parcurgeri este urmatǎ. Dacǎ arborele este infinit, atunci nu putem fi siguri cǎ metoda converge intr-un numar finit de iteratii. In cazul parcurgerii LC, o conditie suficientǎ de convergentǎ a metodei este datǎ de urmatoarea teoremǎ.

Teorema 4.8

Dacǎ existǎ un numar natural k astfel incat pentru oricare douǎ noduri x si y ale arborelui cu niv(x) + k niv(y) implicǎ (x) < (y) si dacǎ existǎ nod admisibil, atunci metoda branch and bound converge intr-un numar finit de iteratii.

Demonstratie

Din conditia niv(x) + k niv(y) implicǎ (x) < (y) rezultǎ cǎ dacǎ x este un nod admisibil, atunci el va deveni nod curent inaintea nodurilor y aflate pe nivelurile mai mari sau egale cu niv(x) + k, adica intr-un numar finit de pasi.

Teorema 4.9

Metoda branch and bound are complexitate exponentiala.

Observatii

Daca arborele    branch and bound este infinit si nu se stie dinainte daca exista nod admisibil, atunci se va margini vizitarea la nodurile al caror cost nu depaseste o valoare fixata.

In general, functia va fi aleasa astfel incat ≤ c.

Probleme rezolvate

Problema BB1

Jocul Perspico

Pe o tabla cadru cu 4 * 4 = 16 pozitii sunt incadrate 15 placute patrate numerotate de la 1 la 15, iar o pozitie din cele 16 este libera. Orice placuta vecina cu pozitia libera poate fi mutata in aceasta pozitie, pozitia din care a fost mutata placuta devenind pozitie libera. Se cere ca, plecand de la o stare posibila a tablei, folosind mutari posibile, sa se treaca la starea admisibila care va fi definita mai jos.

In figura 4.4(a), este prezentata o stare posibila si in figura 4.4(b), este prezentata starea admisibila.

(a) (b)

Figura 4.4

In continuare, se va identifica o stare a tablei printr-o matrice .

Astfel, starile din figura 4.4 sunt identificate cu matricele

S₁ = S_a =

unde se considera ca pozitia libera este numerotata cu 16.

Mai intai sa vedem care sunt conditiile de existenta a unui sir de mutari, pentru a trece dintr-o stare posibila, in starea admisibila. Pentru aceasta se introduce o ordine intre cele 16 pozitii ale tablei in modul urmator: ordinea pozitiilor este ordinea crescatoare a numerelor de pe placute din starea admisibila. Se defineste functia p : N, unde p(i) este numarul pozitiilor care urmeaza pozitiei ce contine placuta cu numarul i si care contin placute cu numere inferioare lui. De exemplu, pentru starea posibila data S₁, avem:

p(i) = 0,    i = 1, 2, 3, 4, 5, 6, 10, 11, 12;

p(i) = 1,    i = 7, 8, 9, 13, 14, 15;

p(16)=10.

Notand cu i₀ si j₀ linia si coloana pozitiei libere, se defineste:

p(0) =

Propozitia 4.3

Se poate trece din starea posibila data, in starea admisibila, daca si numai daca, numarul s = , corespunzator starii posibile date este par.

Demonstratie

Vezi

Pentru exemplul nostru avem s=16, deci se poate trece din starea posibila data S₁, in starea admisibila S_a .

Procedura TPA verifica daca se poate trece de la o stare posibila data S₁ la starea admisibila S_a conform criteriului din propozitia 4.1.

PROCEDURA TPA (S, v);

BEGIN

ARRAY S(4, 4);

s := 0;

FOR i := 1 TO 4 DO

FOR j := 1 TO 4 DO

IF ( S(i, j) = 16 ) AND ( i + j impar ) THEN

s := s+1;

ENDIF;

FOR k := i TO 4 DO

IF k = i

THEN c := j+1

ELSE c:= 1

ENDIF

FOR l := c TO 4 DO

IF s(k, l) < s(i, j) THEN

s := s+1;

ENDIF;

ENDFOR;

ENDFOR;

ENDFOR;

ENDFOR;

IF s impar

THEN v := 1

ELSE v := 0;

ENDIF;

END;

Prin abuz de limbaj, se poate spune ca pozitia libera se deplaseaza. Posibilitatile de deplasare sunt sus (), jos (J), stanga (S), dreapta (D).

Fie urmatoarele stari posibile:

S₂ = S₃ =

S₄ = S₅ =

S_i = S_k =

Tinand seama de aceste stari, o parte din arborele atasat starii posibile date S₁, este reprezentat in figura 4.5.

Arborele branch and bound asociat jocului Perspico este infinit, deoarece un ciclu descris de pozitia libera in mod repetat, corespunde unui drum    infinit divergent din nodul radacina.

Functia de aproximare , se poate defini astfel :

(x) = l(r, x) + q(x)

unde l(r, x) este lungimea drumului de la nodul radacina r la nodul x si q(x) este numarul de placute care nu sunt la locul lor.

Intr-adevar, numarul de mutari necesare pentru a obtine starea admisibila, este cel putin egal cu suma dintre numarul de mutari deja efectuate si numarul de placute ce nu se afla la locul lor.

Cum numarul de placute care nu sunt la locul lor pentru o stare posibila oarecare nu poate depasi pe 16, rezulta ca ne incadram in ipotezele Teoremei 4.3 si deci, algoritmul se termina indiferent din ce stare posibila (satisfacand conditiile propozitiei 4.1) plecam.

De exemplu, pentru partea de arbore aratata in figura 4.5, avem (S₁) = 5, (S₂) = 7, (S₃) = 5, (S₄) = 7, (S_i) = 5, (S_k) = 5, (S_a) = 4. Drumul de la S₁ la S_a este D = (S₁, S₃, S_i, S_a) cu (S₁) = (S₃) = (S_i) = (S_k) = 5.