|

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?

  1. 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ă.
  2. Caracteristici principale:
    • Construiește soluția pas cu pas.
    • Testează toate posibilitățile.
    • Elimină soluțiile incorecte la un stadiu incipient.
  3. 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

  1. Generarea permutărilor și combinațiilor.
  2. Problema reginelor pe tabla de șah.
  3. Problema labirintului.
  4. Sudoku.
  5. Problema rucsacului (varianta cu toate combinațiile).

4. Avantaje și dezavantaje

AvantajeDezavantaje
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

  1. Modelarea problemei:
    Definește soluția în termeni de pași succesivi.
  2. Funcția de validare:
    Verifică dacă o soluție parțială respectă constrângerile.
  3. Apelul recursiv:
    Construiește soluția pas cu pas, revenind la pasul anterior dacă soluția curentă este invalidă.
  4. Criteriul de oprire:
    Determină când o soluție completă a fost găsită.

6. Exemple practice


Exemplu 1: Permutările unui șir

  1. Problema:
    Generați toate permutările unui șir dat.
  2. 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

  1. Problema:
    Plasați 8 regine pe o tablă de șah 8×88 \times 88×8 astfel încât niciuna să nu atace alta.
  2. 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

  1. Problema:
    Determinați un traseu de la intrare la ieșire într-un labirint reprezentat ca o matrice.
  2. 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

  1. Implementați un algoritm backtracking pentru a rezolva Sudoku.
  2. Scrieți un program care generează toate combinațiile de dimensiune kkk dintr-un șir de numere.
  3. Realizați un program care găsește toate drumurile posibile între două puncte dintr-un graf neorientat.

8. Scheme logice

  1. Fluxul backtracking:
    • Start -> Generare pas -> Verificare validitate -> Dacă nu e valid, revenire -> Continuare -> Stop.
  2. 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.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *