GeeksforGeeks

cerințe preliminare :

• recursivitatea
• analiza complexității

Backtrackingul este o tehnică algoritmică pentru rezolvarea problemelor recursiv prin încercarea de a construi o soluție incremental, câte o bucată pe rând, eliminând acele soluții care nu reușesc să satisfacă constrângerile problemei în orice moment al timpului (în timp, aici se face referire la timpul scurs până la atingerea oricărui nivel al arborelui de căutare).

conform definiției wiki,

Backtracking – ul poate fi definit ca o tehnică algoritmică generală care ia în considerare căutarea oricărei combinații posibile pentru a rezolva o problemă de calcul.

există trei tipuri de probleme în backtracking–

1. problema deciziei – în acest sens, căutăm o soluție fezabilă.
2. problemă de optimizare – în aceasta, căutăm cea mai bună soluție.
3. problemă de enumerare – în aceasta, găsim toate soluțiile fezabile.

cum se determină dacă o problemă poate fi rezolvată folosind Backtracking?

în general, orice problemă de satisfacție a constrângerilor care are constrângeri clare și bine definite asupra oricărei soluții obiective, care construiește treptat candidatul la soluție și abandonează un candidat („backtracks”) de îndată ce determină că candidatul nu poate fi completat la o soluție validă, poate fi rezolvată prin Backtracking. Cu toate acestea, majoritatea problemelor discutate pot fi rezolvate folosind alți algoritmi cunoscuți, cum ar fi programarea dinamică sau algoritmi Greedy în complexitatea timpului logaritmic, liniar, liniar-logaritmic în ordinea dimensiunii intrării și, prin urmare, depășesc algoritmul de backtracking din toate punctele de vedere (deoarece algoritmii de backtracking sunt în general exponențiali atât în timp, cât și în spațiu). Cu toate acestea, rămân câteva probleme, care au doar algoritmi de backtracking pentru a le rezolva până acum.

luați în considerare o situație în care aveți trei cutii în fața dvs. și doar una dintre ele are o monedă de aur în ea, dar nu știți care dintre ele. Deci, pentru a obține moneda, va trebui să deschideți toate casetele unul câte unul. Mai întâi veți bifa prima casetă, dacă nu conține moneda, va trebui să o închideți și să bifați a doua casetă și așa mai departe până când găsiți moneda. Aceasta este ceea ce este backtracking-ul, adică rezolvarea tuturor subproblemelor una câte una pentru a ajunge la cea mai bună soluție posibilă.

luați în considerare exemplul de mai jos pentru a înțelege abordarea Backtracking mai formal,

având în vedere o instanță a oricărei probleme de calcul și date corespunzătoare instanței, toate constrângerile care trebuie satisfăcute pentru a rezolva problema sunt reprezentate de . Un algoritm de backtracking va funcționa după cum urmează:

algoritmul începe să construiască o soluție, începând cu un set de soluții goale . S = {}

1. adăugați la prima mișcare care este încă lăsată (toate mișcările posibile sunt adăugate la una câte una). Acest lucru creează acum un nou sub-copac în arborele de căutare al algoritmului.
2. verificați dacă satisface fiecare dintre constrângerile din .
   • dacă da, atunci sub-arborele este „eligibil” pentru a adăuga mai mulți „copii”.
   • altfel, întregul sub-arbore este inutil, deci revine la Pasul 1 folosind argumentul .
3. în cazul „eligibilității” subarborului nou format , revine la Pasul 1, folosind argumentul .
4. dacă verificarea pentru returnează că este o soluție pentru toate datele . Ieșire și termina programul.
   dacă nu, atunci returnați că nu este posibilă nicio soluție cu curentul și, prin urmare, aruncați-l.

diferența dintre Recursivitate și Backtracking:

în recursivitate, funcția se numește până când ajunge la un caz de bază. În backtracking, folosim recursivitatea pentru a explora toate posibilitățile până când obținem cel mai bun rezultat pentru problemă.

Pseudo cod pentru Backtracking :

1. Soluție recursivă de backtracking.

void findSolutions(n, other params) : if (found a solution) : solutionsFound = solutionsFound + 1; displaySolution(); if (solutionsFound >= solutionTarget) : System.exit(0); return for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); findSolutions(n+1, other params); removeValue(val, n);

2. Aflând dacă există sau nu o soluție

boolean findSolutions(n, other params) : if (found a solution) : displaySolution(); return true; for (val = first to last) : if (isValid(val, n)) : applyValue(val, n); if (findSolutions(n+1, other params)) return true; removeValue(val, n); return false;

să încercăm să rezolvăm o problemă standard de Backtracking, problema n-Queen.
Regina N este problema plasării reginelor de șah n pe o tablă de șah n n, astfel încât nici două regine să nu se atace reciproc. De exemplu, în urma este o soluție pentru 4 problemă Regina.

ieșirea așteptată este o matrice binară care are 1s pentru blocurile în care sunt plasate reginele. De exemplu, în urma este matricea de ieșire pentru soluția de mai sus 4 Regina.

{ 0, 1, 0, 0}{ 0, 0, 0, 1}{ 1, 0, 0, 0}{ 0, 0, 1, 0}

algoritm de Backtracking: ideea este de a plasa regine una câte una în coloane diferite, pornind de la coloana din stânga. Când plasăm o regină într-o coloană, verificăm dacă există ciocniri cu regine deja plasate. În coloana curentă, dacă găsim un rând pentru care nu există nicio ciocnire, marcăm acest rând și coloană ca parte a soluției. Dacă nu găsim un astfel de rând din cauza ciocnirilor, atunci ne întoarcem și ne întoarcem fals.

1) Start in the leftmost column2) If all queens are placed return true3) Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this as part of the solution and recursively check if placing queen here leads to a solution. b) If placing the queen in leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this (Backtrack) and go to step (a) to try other rows.3) If all rows have been tried and nothing worked, return false to trigger backtracking.

puteți consulta articolul despre Backtracking | Set 3 (Problema Reginei N) pentru implementarea completă a abordării de mai sus.
mai multe probleme de Backtracking:

• Backtracking | Set 1 (Problema tur Cavalerului)
• Backtracking | Set 2 (șobolan într-un labirint)
• Backtracking / Set 4 (suma subsetului)
• Backtracking / Set 5 (problema de colorat m)
• –> Click aici pentru mai multe