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;
}
Proiect despre backtracking.Am inceput cu definitia metodei de backtracking,dupa asta am dat pasii de rezolvarea a problemelor cu backtracking si niste detalii despre vectori care se folosesc,stive si altele.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.