GRUPUL SCOLAR INDUSTRIAL DE CHIMIE
C.D. NENITESCU
CRAIOVA







LUCRARE DE DIPLOMA





PROFESOR:
TOADER ELENA


NICOLA LILIANA – IONICA
CLASA a XII a F



2004

TEMA LUCRARII:

COLORAREA HARTILOR FOLOSIND METODA BACKTRACKING

Motivul alegerii acestei teme este:
Studierea si aprofundarea rezolvarii problemelor prin metoda backtracking.










CUPRINS:





METODA BACKTRACKING …… 3
APLICATII REZOLVATE …… 5
PROBLEMA COLORARII HARTILOR …… 13

METODA BACKTRACKING
NOTIUNI GENERALE


La dispozitia celor care rezolva probleme cu ajutorul calculatorului exista mai multe metode . Dintre acestea cel mai des utilizate sunt:

metoda Greedy;
metoda Divide et impera;
metoda Branch and Bound;
metoda Backtracking;

Metoda Backtracking se aplica problemelor în care solutia poate fi reprezentata sub forma unui vector – x = (x1, x2, x3, …xk,… xn) € S, unde S este multimea solutiilor problemei si S = S1 x S2 x… x Sn, si Si sunt multimi finite având s elemente si xi € si , (¥)i = 1..n.
Pentru fiecare problema se dau relatii între componentele vectorului x, care sunt numite conditii interne; solutiile posibile care satisfac conditiile interne se numesc solutii rezultat. Metoda de generare a tuturor solutiilor posibile si apoi de determinare a solutiilor rezultat prin verificarea îndeplinirii conditiilor interne necesita foarte mult timp.
Metoda backtracking evita aceasta generare si este mai eficienta. Elementele vectorului x, primesc pe rând valori în ordinea crescatoare a indicilor, x[k] va primi o valoare numai daca au fost atribuite valori elementelor x1.. x[k-1]. La atribuirea valorii lui x[k] se verifica îndeplinirea unor conditii de continuare referitoare la x1…x[k-1]. Daca aceste conditii nu sunt îndeplinite, la pasul k, acest lucru înseamna ca orice valori i-am atribui lui x[k+1], x[k+1], .. x[n] nu se va ajunge la o solutie rezultat.
Metoda backtracking construieste un vector solutie în mod progresiv începând cu prima componenta a v