Branch & Bound - strategia cea mai sofisticata deare a algoritmilor

Este strategia cea mai sofisticata de proiectare a algoritmilor. Ea a aparut datorita existentei problemelor pentru care solutia de tip backtracking poate necesita un timp astronomic de rulare a programului. In rezolvarea acestor probleme apare o asemenea penurie de informatii incit modelul abstract asociat problemei - graful de cautare a solutiilor – nu poate fi precizat in avans, din etapa de analiza. Singura solutie care ramine este includerea unui subalgoritm suplimentar ce permite construirea acestui graf pe parcurs, din aproape in aproape. Aparitia acelui subalgoritm suplimentar da numele metodei: branch&bound.

Este posibila compararea algoritmului branch&bound cu un robot ce invata sa se deplaseze singur si eficient printr-un labirint. Acel robot va fi obligat sa-si construiasca in paralel cu cautarea iesirii o harta (un graf !) a labirintului pe care va aplica apoi , pas cu pas, metode eficiente de obtinere a drumului cel mai scurt.

La strategia de cautare a solutiei in spatiul (graful) de cautare - backtracking, fiecare pas urma automat unul dupa altul pe baza unei reguli incorporate, in timp ce la strategia greedy alegerea pasului urmator era facuta pe baza celei mai bune alegeri. In cazul acestei strategii – branch&bound, pentru pasul urmator algoritmul nu mai este capabil sa faca vreo alegere pentru ca este obligat mai intii sa-si determine singur nodurile vecine ce pot fi vizitate. Numele metodei, branch=ramifica si bound=delimiteaza, provine de la cele doua actiuni ce tin locul actiunii de alegere de la strategia Greedy. Prima actiune este construirea sau determinarea prin ramificare a drumurilor de continuare, iar a doua este eliminarea continuarilor (ramurilor) ineficiente sau eronate. Prin eliminarea unor ramuri, portiuni intregi ale spatiului de cautare a solutiei raminind astfel dintr-o data delimitate si “izolate”. Aceasta strategie de delimitare din mers a anumitor “regiuni” ale spatiului de cautare a solutiilor este cea care permite reducerea ordinului de marime a acestui spatiu. Solutia aceasta este eficienta doar daca cistigul oferit prin reducerea spatiului de cautare (scazind efortul suplimentar depus pentru determinarea si eliminarea din mers a continuarilor ineficiente) este substantial.

Solutiile de tip backtracking, avind la baza un schelet atit de general (algoritmul de traversare a grafului de cautare a solutiilor) sint relativ simplu de adaptat in rezolvarea unor probleme. Poate acesta este motivul care a condus pe unii programatori lipsiti de experienta la convingerea falsa ca “Orice este posibil de rezolvat prin backtracking”.

La ora actuala, lista problemelor pentru care nu se cunosc decit solutii exponentiale, total nerezonabile ca durata de executie a programului de solutionare, cuprinde citeva sute de probleme, una mai celebra ca cealalta. Reamintim doar de “banala” (dar agasanta) Problema a Orarului unei institutii de invatamint care nu admite o solutie backtracking datorita duratei astronomice de asteptare a solutiei.

Datorita totalei lor ineficiente in executie, solutiile backtracking obtinute dupa o analiza si o proiectare “la prima mina” (brute-force approach, in limba engleza) ajung sa fie reanalizate din nou cu mai multa atentie. Se constata atunci ca modelul abstract asociat problemei, fie este prea sarac in informatii pentru determinarea grafului de cautare a solutiilor, fie conduce la un graf de cautare avind dimensiunea nerezonabila (exponentiala sau factoriala, fata de dimensiunea n a vectorului de intrare). Singura solutie care ramine in aceasta situatie la dispozitie este ca aceste solutii sa fie reproiectate prin metoda branch&bound.

Un exemplu usor de inteles de “problema branch&bound“ il ofera Problema Generala a Labirintului. Spre deosebire de Problema Labirintului prezentata anterior (care admitea o solutie de tip backtracking), in varianta extinsa a acestei probleme, numarul directiilor posibile de urmat la fiecare pas poate fi oricit de mare, iar obstacolele pot avea orice forma si dimensiune. In acest caz, singura posibilitate este construirea “din mers” a spatiului de cautare a solutiei. Astfel, pentru determinarea unui drum de iesire din labirint sau a drumului cel mai scurt (daca este posibila determinarea acestuia in timp rezonabil!) este obligatorie adoptarea strategiei branch&bound.

Oferim in continuare o situatie concreta, ilustrata. Sesizati ca obstacolele, avind forme si dimensiuni diferite, nu pot fi ocolite decit pe un traseu “razant” sau pe un traseu ce urmeaza contorul exterior al acestora. Acest fapt complica mult problema si impune luarea unor decizii “la fata locului”, in momentul intilnirii si ocolirii fiecarui obstacol, ceea ce impune o strategie de rezolvare de tip branch&bound – ramifica si delimiteaza:

Desi aceasta strategie poate sa creasca uneori surprinzator de mult eficienta algoritmilor de solutionare (din nerezonabili ca timp de executie ei pot ajunge rezonabili, datorita reducerii dimensiunii exponentiale a spatiului de cautare a solutiei), aplicarea ei este posibila doar printr-un efort suplimentar in etapa de analiza si in cea de proiectare a algoritmului. Dezavantajul major al acestei metode consta deci in efortul major depus in etapa de analiza a problemei (analiza care insa se va face o singura data si bine!) si efortul suplimentar depus in etapa proiectarii algoritmului de solutionare.

Din experienta practica este cunoscut faptul ca, pentru a analiza o problema dificila un analist poate avea nevoie de saptamini sau chiar luni de zile de analiza, in timp ce algoritmul de solutionare proiectat va dura, ca timp de executie, doar citeva zeci de minute. Daca programul obtinut nu este necesar a fi rulat decit o data, aceasta este prea putin pentru “a se amortiza” costul mare al analizei si proiectarii sale. In acea situatie, solutia branch&bound este nerentabila si, probabil ca ar fi mai ieftina strategia backtracking de solutionare, chiar si cu riscul de a obtine o executie (singura de altfel) a programului cu durata de o saptamina (ceea ce poate sa insemne totusi economie de timp).