TURNURILE DIN HANOI , RUTINA BACKTRACKING REFERAT SCOALA

Este o tehnica de programare aplicabila algoritmilor care oferă mai multe soluţii şi are ca rezultat obţinerea tuturor soluţiilor problemei. Fiecare soluţie se memorează într-o structura de date de tip stivă implementată cu ajutorul unui vector. Deci fiecare soluţie poate fi pusă sub forma unui vector. Într-un algoritm backtracking ne interesează toate soluţiile posibile. Pentru a obţine fiecare soluţie finală se completează stiva nivel cu nivel trecând astfel prin nişte soluţii parţiale. Astfel soluţiile finale cât şi cele parţiale pentru a fi luate în considerare trebuie să îndeplinească anumite condiţii numite condiţii de validare. O soluţie care îndeplineşte o astfel de condiţie se numeşte soluţie validă. Toate configuraţiile stivei ce reprezintă soluţii finale sunt alcătuite din elementele aceleiaşi mulţimi bine definite pe care o numim mulţimea soluţiilor. Fiecare nouă soluţie parţială se obţine prin completarea soluţiei parţiale precedente cu încă o nivel pe stivă. La fiecare nivel se pun valori din mulţimea soluţiilor care nu au fost încercate până când se obţine o soluţie validă. În acest moment se trece la nivelul următor în stivă pentru a completa mai departe soluţia reluând încercările pe noul nivel. La un moment dat pe un anumit nivel nu mai există nici o valoare neîncercată din mulţimea valorilor problemei. În acest caz se face un pas înapoi în stivă la nivelul anterior şi se reia căutarea cu valorile rămase neîncercate pe acest nivel anterior. Respectivul nivel a mai fost vizitat dar l-am abandonat după ce am pus o valoare care a generat o soluţie validă. Deci este posibil să fi rămas aici valori neîncercate. Dacă nici pe acest nivel nu mai avem valori neîncercate mai facem un pas înapoi în stivă. Mecanismul revenirilor a determinat denumirea de metoda backtracking.