Informatică Algoritmi
Algoritmi backtracking exemple rezolvate
Backtracking este o tehnică algoritmică care explorează toate soluțiile posibile într-o problemă, revenind la pașii anteriori când o căi devine invalidă. Este folosită în probleme combinatorii, cum ar fi problema reginelor sau labirinturile. Funcționează prin încercare și eroare, cu revenire la stări anterioare.
Pașii generali
- 1 Pasul 1 Alege o opțiune din mulțimea curentă de posibilități.
- 2 Pasul 2 Verifică dacă opțiunea duce la o soluție validă.
- 3 Pasul 3 Dacă da, continuă recursiv cu următorul pas; dacă nu, renunță la opțiune.
- 4 Pasul 4 Revenirea (backtrack) la pasul anterior pentru a încerca alte opțiuni.
Exemplu rezolvat: problema reginelor pe tabla 4x4
- Scop Plasează 4 regine pe o tablă de șah 4x4, fără să se atace.
- Soluția 1 Rând 1: regina la coloana 2; rând 2: coloana 4; rând 3: coloana 1; rând 4: coloana 3.
- Backtracking în acțiune Dacă la rândul 2 plasezi regina la coloana 1, atacă cu regina de la rândul 1 → renunți și încerci coloana 4.
- Soluția 2 Rând 1: coloana 3; rând 2: coloana 1; rând 3: coloana 4; rând 4: coloana 2.
Folosește backtracking pentru probleme cu spațiu de căutare mare, dar asigură-te că implementezi condiții de tăiere pentru eficiență.