Metoda Backtracking
Backtracking-ul este o metoda ce foloseste principiul recursivitatii. Recursivitatea este o tehnica de programare in care o fuctie se apeleaza pe ea insasi, ceea ce se schimba in acest apel fiind valoarea parametrilor. Recursivitatea se foloseste atunci cand o anumita problema poate fi impartita in subprobleme de acelasi fel / de acelasi tip, dar mai mici.
Proncipiul de functionare
Metoda backtracking foloseste arborele de decizie explorand fiecare potentiala posibilitate de a ajunge la o solutie a problemei si revenind la un pas anterior in momentul in care solutia la care se ajunge nu este una valida adica nu respecta constrangerile/conditiile problemei. Ca sa fim mai expliciti si sa intelegem conceptual, sa ne gandim ca plecam de acasa catre o anumita destinatie. La un moment dat ajungem pe o straduta care se infunda. Ce facem? Ne intoarcem inapoi pana acasa? Nu - ne intoarcem doar pana la prima intersectie anterioara si o luam pe alt drum decat pe cel pe care o luasem anterior si care s-a infundat. Acelasi principiu este si in cazul backtracking: cand constatam ca solutia nu este una buna, ne intoarcem la un pas anterior si exploram alta optiune valida.
Pasi
- Pornim de la o soluție goală (Plecam de acasa).
- Încercăm să extindem soluția pas cu pas (Mergem pe straduta din dreapta de exemplu).
- Verificăm dacă soluția parțială este validă (Ne-am blocat sau nu?).
- Dacă este validă (Nu am ajuns pe straduta care se infunda), continuăm explorarea.
- Dacă nu este validă (Am ajuns pe straduta care se infunda), revenim la pasul anterior (intersesctia anteriara) și încercăm altă opțiune.
- Dacă am ajuns la o soluție completă (Am ajuns la destinatie), o afișăm/salvăm.
- Continuăm explorarea până când epuizăm toate posibilitățile (Cautam rute alternative).
Exemplu:
Se da o listă de n numere cu ajutorul carora dorim să generăm toate permutările posibile folosind metoda backtracking.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
#include <iostream>
using namespace std;
const int MAX_N = 10; //Numarul maxim de elemente
int N; // Numărul efectiv de elemente ale sirului
int numere[MAX_N]; // Lista inițială
int permutare[MAX_N]; // Permutarea curentă
bool utilizat[MAX_N] = {false}; // Marcam numerele utilizate
void backtrack(int k)
{
if (k == N) // Când permutarea este completă
{
for (int i = 0; i < N; i++)
cout << permutare[i] << " ";
cout << endl;
return;
}
for (int i = 0; i < N; i++)
{
if (!utilizat[i]) // Dacă numărul nu a fost folosit
{
utilizat[i] = true; // Marcam ca utilizat
permutare[k] = numere[i]; // Adăugăm numărul în permutare
backtrack(k + 1); // Apel recursiv pentru poziția următoare
utilizat[i] = false; // Backtracking: revenim la starea anterioară
}
}
}
int main()
{
cout<<"Cate elemente are multimea: N=";
cin>>N;
cout<<"Introduceti elementele multimii:"<<endl;
for (int i=0;i<N; i++)
{
cout<<"Numere["<<i<<"]=";
cin>>numere[i];
}
cout<<"Elementele multimii sunt:"<<endl;
for (int i=0;i<N;i++)
cout<<numere[i]<<" ";
cout<<endl;
cout <<"Permutarile sunt:\n";
backtrack(0); // Start recursiv de la poziția 0
return 0;
}
|
|
|
Cate numere are multimea: N=3
Introduceti elementele multimii:
Numere[0]=1
Numere[1]=2
Numere[2]=3
Elementele multimii sunt: 1 2 3
Permutarile sunt:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
|
