Backtracking

Tehnica Backtracking propune generarea solutiei prin completarea vectorului x în ordine x1x2... xn si are la bazÎ un principiu “de bun simt”: dacÎ se constatÎ cÎ având o combinatie partialÎ de formÎ v1v2...v k-1 (unde vi,…,vk-1 sunt valori deja fixate), dacÎ alegem pentru xk o valoare vk si combinatia rezultatÎ nu ne permite sÎ ajungem la o solutie, se renuntÎ la aceastÎ valoare si se încearcÎ o alta (dintre cele netestate în aceastÎ etapÎ). Într-adevÎr, oricum am alega celelalte valori, dacÎ una nu corespunde nu putem avea o solutie.

Altgoritmul general al metodei Backtracking

Pentru evitarea generÎrii combinatiilor neconvenabile se procedeazÎ astfel:

Presupunem cÎ s-au gÎsit valorile v1v2…vk-1 pentru componentele x1x2... xk-1 (au rÎmas de determinat valorile pentru xk…xn). ne ocupÎm în continuare de componenta xk. Pasii urmati sunt:

1. Pentru început, pentru xk nu s-a testat încÎ nici o valoare.

2. Se verificÎ dacÎ existÎ valori netestate pentru xk .

a) În caz afirmativ, se trece la pasul 3.

b) Altfel, se revine la componenta anterioarÎ, xk-1; se reia pasul 2 pentru k=k-1.

3. Se alege prima valoare v dintre cele netestate încÎ pentru xk.

4. Se verificÎ dacÎ acestÎ combinatie partialÎ v1v2…vk-1v ne poate conduce la un rezultat (dacÎ sunt îndeplinite anumite conditii de continuare).

a) DacÎ valoarea aleasÎ este bunÎ se trece la pasul 5.

b) Altfel, se rÎmâne pe aceeasi pozitie k si se reia cazul 2.

5. Se verificÎ dacÎ s-a obtinut o solutie .

a) În caz afirmativ, se tipÎreste aceastÎ solutie si se rÎmâne la aceeasi componentÎ xk, reluându-se pasul 2.

b) Altfel se reia altgoritmul pentru urmÎtoarea componentÎ (se trece la pasul 1 pentru k=k+1).

Înainte de a scrie programul care ne va obtine solutiile, trebuie sÎ stabilim unele detalii cu privire la:

- vectorul solutie – câte componente are, ce mentine fiecare componentÎ.

- multimea de valori posibile pentru fiecare componentÎ (sunt foarte importante limitele acestei multimi).

- conditiile de continuare (conditiile ca o valoare x[k]sÎ fie acceptatÎ).

- conditia ca ansamblul de valori generat sÎ fie solutie.

Probleme :

Problema damelor :

#include<iostream.h>

#include<math.h>

int st[100],n,k;

void init()

{

st[k]=0;

}

int am_succesor()

{

if(st[k]<n){st[k]++;

return 1;

}

else return 0;

}

int e_valid()

{

for(i=1;i<k;i++)if(st[k]==st[i] || abs(st[k]-st[i])==abs(k-i))return 0;

return 1;

}

int solutie()

{

return k==n;

}