Cuprins:
Definiție - Ce înseamnă Backtracking?
Backtracking este un algoritm pentru captarea unor sau a tuturor soluțiilor la problemele de calcul date, în special pentru problemele de satisfacție de constrângere. Algoritmul poate fi utilizat doar pentru problemele care pot accepta conceptul de „soluție parțială a candidatului” și permite un test rapid pentru a vedea dacă soluția candidat poate fi o soluție completă. Backtracking este considerat o tehnică importantă pentru a rezolva problemele de satisfacție și puzzle-uri de constrângere. Este, de asemenea, considerată o tehnică excelentă pentru analiză și constituie, de asemenea, baza multor limbaje de programare logice.
Techopedia explică Backtracking
Backtracking ajută la rezolvarea unei probleme generale, găsind o soluție la prima sub-problemă și apoi încercând recursiv să rezolve alte sub-probleme bazate pe soluția primei probleme. Dacă problema actuală nu poate fi rezolvată, pasul este retrocedat și următoarea soluție posibilă se aplică la etapele anterioare, apoi se continuă. De fapt, unul dintre lucrurile cheie în backtracking este recursivitatea. De asemenea, este considerată ca o metodă de căutare exhaustivă folosind diviziune și cucerire. Un algoritm de backtracking se încheie atunci când nu mai există soluții la prima sub-problemă.
Backtracking este un algoritm care poate ajuta la realizarea implementării nondeterminismului. Este nevoie de o primă căutare în profunzime a unui spațiu de emisiune dat. Este folosit mai ales în limbaje de programare logică precum Prolog. Oriunde se poate aplica backtracking, este mai rapid decât tehnica forței brute, deoarece elimină un număr mare de candidați cu un singur test.
