Backtracking

Backtracking este numele unui algoritm general de descoperire a tuturor soluțiilor unei probleme de calcul, algoritm ce se bazează pe construirea incrementală de soluții-candidat, abandonând fiecare candidat parțial imediat ce devine clar că acesta nu are șanse să devină o soluție validă.^[1]^[2]^[3]

Exemplul de bază folosit în numeroase manuale de liceu și de nivel universitar este problema reginelor, care cere să se găsească toate modurile în care pot fi așezate pe o tablă de șah opt regine astfel încât să nu se atace. În abordarea backtracking, candidatele parțiale sunt aranjamente de câte k regine pe primele k rânduri ale tablei, toate pe rânduri și coloane diferite. Orice soluție parțială ce conține două regine care se atacă poate fi abandonată, deoarece în mod clar restul de regine nu pot fi așezate într-o soluție validă.

Tehnica backtracking se poate aplica doar pentru probleme ce admit conceptul de „candidat parțial de soluție” și oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluție validă. Când se poate aplica, însă, backtrackingul este adesea mult mai rapid decât căutarea prin metoda forței brute prin toți candidații, întrucât este capabilă să elimine dintr-un singur test un mare număr de candidați.

Backtrackingul este util la rezolvarea unor probleme de satisfacere a constrângerilor, cum ar fi cuvintele încrucișate, jocuri de sudoku și alte probleme similare. Ea stă la baza unei serii de limbaje de programare logică, cum ar fi Icon, Planner și Prolog.

Termenul „backtrack” a fost inventat de matematicianul american D. H. Lehmer în anii 1950.^[4]

Note

^ Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley.
^ Thomas H. Cormen (1990). Introduction to Algorithms. McGraw-Hill.
^ Gurari, Eitan (1999). „CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms”. Arhivat din original la 17 martie 2007. Accesat în 28 aprilie 2011.
^ Rossi, Francesca (august 2006). „Constraint Satisfaction: An Emerging Paradigm”. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Amsterdam: Elsevier. p. 14. ISBN 978-0-444-52726-4. Accesat în 30 decembrie 2008. Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.

[1] Donald E. Knuth (1968). The Art of Computer Programming. Addison-Wesley.

[2] Thomas H. Cormen (1990). Introduction to Algorithms. McGraw-Hill.

[3] Gurari, Eitan (1999). „CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms”. Arhivat din original la 17 martie 2007. Accesat în 28 aprilie 2011.

[4] Rossi, Francesca (august 2006). „Constraint Satisfaction: An Emerging Paradigm”. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Amsterdam: Elsevier. p. 14. ISBN 978-0-444-52726-4. Accesat în 30 decembrie 2008. Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.

[1]

[2]

[3]

[4]