Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Backtracking si Branch-and-Bound

algoritmi

+ Font mai mare | - Font mai mic



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 (x1,x2,xi) un drum de la radacina la un nod intr-un arbore spatiu de stari.

Fie T(x1,x2,..xi) multimea tuturor valorilor posibile pentru xi+1 astfel incit

(x1,x2,..xi,xi+1) este de asemenea un drum de la radacina la un nod.

Fie Bi+1(x1,x2,..xi+1) functia (predicatul) de marginire derivat din P - functia criteriu

Bi+1(x1,x2,..xi+1) = false daca xi+1 este nod mort, de blocaj; true daca xi+1 se extinde;

backtrack(n)

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

// T(x1,..xk-1)=

// Bk(x1, xk) - functie (predicat) de marginire;

else

k-- ;

}

backtrack-recursiv(k)

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

//T(x1,..xk-1)=

//Bk(x1, xk) - functie (predicat) de marginire;

for (each xk a.i. xk= y I T(x1.xk-1)

and Bk(x1..xk-1,xk)=true

Observatii

1.Eficienta algoritmului depinde de

- timpul pentru generarea urmatorului xk;

- numarul de elemente din T(x1..xk-1)

- functia de marginire B;

- numarul total de noduri.

2.Pentru multe probleme, multimile Si, se pot lucra in orice ordine, iar elementele din T(x1,xk-1) la fel.

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

cu scopul de a reduce nivelul de backtraking.

3.Ordinul de complexitate este O(2n) 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(|Tk|=0) break;

r=r |Tk| ;

nr=nr+r ;

Xk=random-choose(Tk);

k=k+1;

}

return (nr)





Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1134
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2023 . All rights reserved