Backtracking si Branch-and-Bound

Exista doua strategii de generare a nodurilor corespunzatoare starilor problemei : depth-first si breadh-first.

Nodurile se clasifica in:

-nod viu -nod generat pentru care nu s-au generat descendenti;

-E-noduri -noduri in expandare - noduri vii pentru care procesul de generare al

descendentilor este in curs;

-noduri moarte -nod generat care nu are descendenti sau (si nici nu va avea)

sau pentru care toti descendentii s-au generat.

In strategia depth-first, pentru E-nodul curent se identifica un descendent C care devine noul E-nod si procesul se aplica recursiv.

In strategia breadth-first, pentru E-nodul curent se genereaza toti descendentii si se trec in lista de noduri vii sau moarte.

In ambele strategii in orice moment se aplica functia criteriu (restrictiile implicite), numita si functia de marginire care seteaza un nod ca nod mort fara a-i mai genera descendentii.

Prima tehnica este numita backtracking

A doua tehnica este numita Branch-and-Bound

Exemplu pentru tehnica backtracking: Problema celor 4 dame:

Ordinea de generare este:

2. Modelul matematic

Fie (x₁,x₂,x_i) un drum de la radacina la un nod intr-un arbore spatiu de stari.

Fie T(x₁,x₂,..x_i) multimea tuturor valorilor posibile pentru x_i+1 astfel incit

(x₁,x₂,..x_i,x_i+1) este de asemenea un drum de la radacina la un nod.

Fie B_i+1(x₁,x₂,..x_i+1) functia (predicatul) de marginire derivat din P - functia criteriu

B_i+1(x₁,x₂,..x_i+1) = false daca x_i+1 este nod mort, de blocaj; true daca x_i+1 se extinde;

backtrack(n)

Solutile sint generate in x[1,2,n];

// T(x₁,..x_k-1)=

// B_k(x₁, x_k) - functie (predicat) de marginire;

else

k-- ;

}

backtrack-recursiv(k)

// Solutile sint generate in x[1,2,n];

//T(x₁,..x_k-1)=

//B_k(x₁, x_k) - functie (predicat) de marginire;

for (each x_k a.i. x_k= y I T(x₁.x_k-1)

and B_k(x₁..x_k-1,x_k)=true

Observatii

1.Eficienta algoritmului depinde de

- timpul pentru generarea urmatorului x_k;

- numarul de elemente din T(x₁..x_k-1)

- functia de marginire B;

- numarul total de noduri.

2.Pentru multe probleme, multimile S_i, se pot lucra in orice ordine, iar elementele din T(x₁,x_k-1) la fel.

Folosind aceasta observatie se pot stabili anumite euristici - strategii de organizare a elementelor lui S_i

cu scopul de a reduce nivelul de backtraking.

3.Ordinul de complexitate este O(2ⁿ) sau O(n!)

Metoda insa rezolva , de obicei, mult mai rapid problemele fara insa a se sti exact cit de repede.

Uneori se poate incerca o estimare a timpului backtrcking si aceasta pornind de la o estimare a numarului de noduri.

Estimarea numarului de noduri se poate face prin urmatoarea procedura generala:

estimate

if(|T_k|=0) break;

r=r |T_k| ;

nr=nr+r ;

X_k=random-choose(T_k);

k=k+1;

}

return (nr)