Informatică Programare
Algoritmi de backtracking exemple C++
Algoritmii de backtracking sunt tehnici de explorare sistematică a tuturor soluțiilor posibile într-o problemă, revenind la pașii anteriori când o căi devine invalidă. Aceștia sunt folosiți în probleme combinatorii, cum ar fi generarea permutărilor sau rezolvarea Sudoku. În C++, backtracking-ul este implementat de obicei cu funcții recursive care testează și revin la stări anterioare. De exemplu, poți genera toate permutările numerelor 1, 2, 3 folosind această metodă.
Pașii generali ai backtracking-ului
- Alegerea unei opțiuni La fiecare pas, alege un element dintr-o mulțime disponibilă, cum ar fi un număr pentru o permutare.
- Verificarea validității Verifică dacă alegerea curentă respectă constrângerile problemei; dacă nu, renunță la ea și revino.
- Explorarea recursivă Dacă alegerea este validă, continuă cu următorul pas, apelând recursiv funcția pentru restul elementelor.
- Revenirea (backtrack) După explorarea tuturor opțiunilor dintr-un pas, revino la pasul anterior pentru a încerca alte alegeri.
Exemplu rezolvat în C++: Generarea permutărilor
- 1 Pasul 1: Definirea funcției recursive Creează o funcție backtrack(vector<int>& permutare, vector<bool>& folosit) care primește permutarea curentă și un vector pentru a marca numerele folosite.
- 2 Pasul 2: Condiția de oprire Dacă permutarea are dimensiunea n (de ex., n=3), afișează permutarea, cum ar fi {1, 2, 3}.
- 3 Pasul 3: Parcurgerea opțiunilor Pentru i de la 1 la n, dacă numărul i nu este folosit, adaugă-l la permutare și marchează-l ca folosit.
- 4 Pasul 4: Apelul recursiv Apelează backtrack(permutare, folosit) pentru a continua cu următoarele poziții.
- 5 Pasul 5: Revenirea După apelul recursiv, elimină ultimul element din permutare și marchează numărul ca nefolosit pentru a încerca alte variante.
Pentru a exersa, implementează algoritmul pentru generarea combinărilor sau rezolvarea unei probleme simple de plasare a reginelor pe o tablă de șah.