Metoda Backtracking în Programare 2
1. Obiectivele lecției:
- Să înțeleagă conceptul metodei backtracking.
- Să învețe cum să modeleze problemele folosind metoda backtracking.
- Să implementeze exemple practice care utilizează backtracking pentru a explora toate soluțiile posibile.
2. Ce este metoda Backtracking?
- Definiție:
Metoda backtracking este o tehnică de explorare sistematică a tuturor posibilităților pentru rezolvarea unei probleme. Aceasta testează soluții parțiale, revenind (backtracking) atunci când o soluție nu mai este validă. - Caracteristici principale:
- Construiește soluția pas cu pas.
- Testează toate posibilitățile.
- Elimină soluțiile incorecte la un stadiu incipient.
- Etapele metodei:
- Generarea: Construirea treptată a soluției.
- Validarea: Verificarea dacă soluția parțială este validă.
- Revenirea: Eliminarea unei alegeri și revenirea la pasul anterior.
3. Probleme rezolvate prin backtracking
- Generarea permutărilor și combinațiilor.
- Problema reginelor pe tabla de șah.
- Problema labirintului.
- Sudoku.
- Problema rucsacului (varianta cu toate combinațiile).
4. Avantaje și dezavantaje
Avantaje | Dezavantaje |
Garantează găsirea soluției, dacă există. | Ineficient pentru probleme de dimensiuni mari. |
Explorează toate posibilitățile. | Timp de execuție poate fi foarte mare (explozie combinatorică). |
Permite revenirea și testarea altor soluții. | Poate necesita optimizări pentru a fi practică. |
5. Etapele implementării backtracking-ului
- Modelarea problemei:
Definește soluția în termeni de pași succesivi. - Funcția de validare:
Verifică dacă o soluție parțială respectă constrângerile. - Apelul recursiv:
Construiește soluția pas cu pas, revenind la pasul anterior dacă soluția curentă este invalidă. - Criteriul de oprire:
Determină când o soluție completă a fost găsită.
6. Exemple practice
Exemplu 1: Permutările unui șir
- Problema:
Generați toate permutările unui șir dat. - Implementare:
#include <iostream>
#include <vector>
using namespace std;
void permuta(vector<int>& sir, int index) {
if (index == sir.size()) {
for (int num : sir) {
cout << num << ” „;
}
cout << endl;
return;
}
for (int i = index; i < sir.size(); i++) {
swap(sir[index], sir[i]); // Schimbă elementele
permuta(sir, index + 1); // Continuă cu următorul index
swap(sir[index], sir[i]); // Revine la configurația inițială
}
}
int main() {
vector<int> sir = {1, 2, 3};
permuta(sir, 0);
return 0;
}
Exemplu 2: Problema celor 8 regine
- Problema:
Plasați 8 regine pe o tablă de șah 8×88 \times 88×8 astfel încât niciuna să nu atace alta. - Implementare:
#include <iostream>
#include <vector>
using namespace std;
const int N = 8;
bool esteValid(vector<int>& regine, int rand, int coloana) {
for (int i = 0; i < rand; i++) {
if (regine[i] == coloana || abs(regine[i] – coloana) == abs(i – rand)) {
return false;
}
}
return true;
}
void regine(vector<int>& regine, int rand) {
if (rand == N) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << (regine[i] == j ? „Q ” : „. „);
}
cout << endl;
}
cout << endl;
return;
}
for (int coloana = 0; coloana < N; coloana++) {
if (esteValid(regine, rand, coloana)) {
regine[rand] = coloana;
regine(regine, rand + 1);
}
}
}
int main() {
vector<int> regine(N, -1);
regine(regine, 0);
return 0;
}
Exemplu 3: Rezolvarea unui labirint
- Problema:
Determinați un traseu de la intrare la ieșire într-un labirint reprezentat ca o matrice. - Implementare:
#include <iostream>
using namespace std;
const int N = 4;
int labirint[N][N] = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
bool esteValid(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && labirint[x][y] == 1);
}
bool rezolvaLabirint(int x, int y, int sol[N][N]) {
if (x == N – 1 && y == N – 1) {
sol[x][y] = 1;
return true;
}
if (esteValid(x, y)) {
sol[x][y] = 1;
if (rezolvaLabirint(x + 1, y, sol)) return true;
if (rezolvaLabirint(x, y + 1, sol)) return true;
sol[x][y] = 0; // Backtracking
}
return false;
}
int main() {
int sol[N][N] = {0};
if (rezolvaLabirint(0, 0, sol)) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << sol[i][j] << ” „;
}
cout << endl;
}
} else {
cout << „Nu există soluție.” << endl;
}
return 0;
}
7. Activități practice pentru elevi
- Implementați un algoritm backtracking pentru a rezolva Sudoku.
- Scrieți un program care generează toate combinațiile de dimensiune kkk dintr-un șir de numere.
- Realizați un program care găsește toate drumurile posibile între două puncte dintr-un graf neorientat.
8. Scheme logice
- Fluxul backtracking:
- Start -> Generare pas -> Verificare validitate -> Dacă nu e valid, revenire -> Continuare -> Stop.
- Diagrama de apeluri recursive:
- Nivele succesive de apeluri pentru fiecare alegere.
9. Concluzie
- Backtracking-ul este o metodă puternică și flexibilă pentru probleme care necesită explorarea tuturor soluțiilor posibile.
- Este esențială definirea corectă a criteriilor de validare și a condiției de oprire.
- Practica este crucială pentru a învăța să aplici eficient această metodă la diverse probleme.