Căutarea backtracking , backtracking este o metodă generală de găsire a soluțiilor la o problemă care necesită o enumerare completă a tuturor opțiunilor posibile dintr-un anumit set M. De regulă, vă permite să rezolvați probleme care pun întrebări precum: „Enumerați toate opțiunile posibile . ..” , „Câte moduri...”, „Există o cale...”, „Există un obiect...”, etc.
Termenul de backtracking a fost inventat în 1950 de matematicianul american Derrick Henry Lehmer .
Modificările minore ale metodei de backtracking legate de reprezentarea datelor sau de caracteristicile de implementare au alte denumiri: metoda ramurilor și legate , căutarea în adâncime , metoda încercării și erorii etc. Căutarea backtracking a fost inventată de mulți cercetători aproape simultan și independent înainte de descrierea sa formală.
Rezolvarea problemei prin metoda backtracking se reduce la extinderea succesivă a unei soluții parțiale. Dacă la pasul următor o astfel de extindere eșuează, atunci se întorc la o soluție parțială mai scurtă și continuă căutarea în continuare. Acest algoritm vă permite să găsiți toate soluțiile la problemă, dacă acestea există. Pentru a accelera metoda, ei încearcă să organizeze calculele în așa fel încât să identifice cât mai devreme opțiunile evident nepotrivite. Adesea, acest lucru poate reduce semnificativ timpul necesar pentru găsirea unei soluții.
Un exemplu clasic de utilizare a unui algoritm de backtracking este problema celor opt regine . Formularea sa este următoarea: „Aranjați 8 dame pe o tablă de șah standard cu 64 de celule, astfel încât niciuna dintre ele să nu fie atacată de alta”. Mai întâi, o regină este așezată pe tablă și apoi încearcă să plaseze fiecare regină următoare, astfel încât să nu fie învinsă de matcile deja stabilite. Dacă la pasul următor nu se poate face o astfel de setare, se întorc cu un pas înapoi și încearcă să pună matca instalată anterior în alt loc.
În plus, metoda backtracking vă permite să rezolvați multe alte probleme de enumerare. De exemplu, folosindu-l puteți obține toate subseturile , plasamentele , permutările , combinațiile unui anumit set M.
Metoda de backtracking este generică. Este destul de ușor să proiectați și să programați algoritmi pentru rezolvarea problemelor folosind această metodă. Cu toate acestea, timpul pentru găsirea unei soluții poate fi foarte lung chiar și cu dimensiuni mici ale problemei (cantitatea de date inițiale), și este atât de lung (poate fi ani sau chiar secole) încât nu poate fi vorba de aplicarea practică. . Prin urmare, atunci când se proiectează astfel de algoritmi, este necesar să se estimeze teoretic timpul de lucru al acestora pe date specifice. Există și probleme de selecție, pentru care puteți construi algoritmi unici, „rapidi”, care vă permit să obțineți rapid o soluție chiar și cu dimensiuni mari ale problemei. Metoda backtracking este ineficientă în astfel de probleme.
| Algoritmi de căutare grafică | ||
|---|---|---|
| Metode neinformate | ||
| Metode informate | ||
| Comenzi rapide | ||
| Arborele de întindere minim | ||
| Alte | ||