Metoda backtracking

Metoda Backtracking - metoda „revenirii”, definită şi elaborată de AI (Artificial Intelligence); este o metodă folosită în cazul problemelor în care se cere afişarea soluţiilor, iar o soluţie poate fi dată sub forma unui vector. Fiecare element al vectorului aparţine la rândul său unei mulţimi finite de elemente întregi, aflată într-o ordine bine stabilită. Este de reţinut că:

 Soluţia se construieşte pas cu pas, pornind de la primul element şi adăugând la vector următoarele elemente, cu revenire la elementul anterior în caz de insucces;

 Elementul care trebuie adăugat se caută în mulţime printre elementele care respectă restricţiile specifice problemei (condiţiile interne).

Pentru implimentarea acestei metode se foloseşte o rutină principală care conţine mai multe funcţii cu rol bine stabilit. În general rutina principală rămâne neschimbată în toate tipurile de probleme, schimbându-se doar funcţiile din cadrul rutinei.

Concepţia şi strategia metodei Backtracking

Metoda a fost concepută pentru a evita generarea tuturor soluţiilor posibile.

În acest sens metoda foloseşte un arbore virtual construit astfel:

• Nivelul 0conţine rădăcina virtuală r;

• Nivelul 1 conţine ca noduri, elementele mulţimii în care componenta x1ia valori, legăturile mulţimii etichetate cu 1,2..., ;

• Nivelul k ≥2, conţine ca noduri elementele mulţimii , astfel ca din orice nod de pe nivelul k-1pleacă exact muchii; nivelul conţine noduri;

• Nivelul n conţine noduri terminale.

Metoda Backtracking utilizează arborele ataşat soluţiilor posibile pentru a genera soluţiile rezultat, evitând generarea soluţiilor posibile prin verificarea condiţiilor de continuitate .

Implementarea metodei

Procedura nerecursivă

INPUT :

OUTPUT: soluţii rezultat.

Procedure BACK;

Varianta recursivă:

Utilizare :

BACK(1);

Această tehnică se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoare condiţii:

• Soluţia lor poate fi pusă sub forma unui vector S=x1x2,……..,xn cu x1 A1, x2  A2, …….., xn  An;

• Mulţimile A1, A2, …….., An sunt mulţimi finite, iar elementele lor se consider că se află într-o relaţie de ordine bine stabilite;

• Nu se dispune de o altă metodă de rezolvare, mai rapidă;