Metoda backtracking

Aceasta tehnica se foloseste in rezolvarea problemelor care indeplinesc simultan urmatoarele conditii:

- Solutia lor poate fi pusa sub forma unui vector S=x1x2, ,xn cu x1? A1, x2 ? A2, , xn ? An ;

- Multimile A1, A2, , An sunt multimi finite, iar elementele lor se considera ca se afla intr-o relatie de ordine bine stabilita;

- Nu se dispune de o alta metoda de rezolvare, mai rapida;

Aceasta tehnica presupune trei functii:

1. Functia de citire a valorile cunoscute;

2. Functia de tiparire a solutiilor;

3. Functia backtracking.

Schema generala a procedurii backtracking:

Void back (int k)

Int I, cont;

{

if (k=n+1) tipar ( );

else for (i=1; i=n; i++)

{

a[k]=i;

cont=1;

pentru cazul prost CONT ia valoarea FALS: cont=0;

if (cont = = 1) back (k+1);

}

}

Programele prezentate mai jos, in pseudocod, sunt:

- Paranteze;

- Comis-voiajor;

- Dame;

- Submultimi;

- Magazin;

- Permutari.