METODA BACKTRACKING

1. Observatii

1.1. nu pentru toate problemele n este cunoscut de la început;

1.2. x1,x2,...,xn pot fi la rîndul său vectori

1.3. în multe probleme, mulțimile A1, A2,..., An

2. Principiul ce sta la baza metodei

2.1. În general, produsul cartezian are nn elemente, din care permutări sunt n!. Este evident că un astfel de algoritm de generare a permutărilor este ineficient… Tehnica Backtracking are la bază un principiu extrem de simplu: Dacă în procesul de generare a unui vector soluție S= x1,x2,...,xn , pentru componenta k, atunci cînd am generat deja x1,x2,...,xk constatăm că valoarea xk nu este bine aleasă (păstrînd-o, nu se va ajunge la soluție), nu trecem la componenta k+1, ci reluăm căutarea pentru altă valoare a lui k, iar dacă această valoare nu există reluăm căutarea pentru componenta k-1.

3. Grupul

3.1. Buruiana ,Lupan , Ribac

4. Conditii

4.1. soluția problemelor poate fi pusă sub forma unui vector soluția problemelor poate fi pusă sub forma unui vector

4.2. mulțimile A1,A2,...,An sunt mulțimi finite, iar elementele lor se consideră că se află într-o ordine bine stabilită

4.3. nu se dispune de o altă metodă de rezolvare, mai rapidă

5. Utilizarea

5.1. Metoda reluarii(backtracking) se aplică numai atunci cînd nu există o altă cale de rezolvare a problemei propuse, deoarece timpul de execuție este de ordin exponențial (crește exponențial o dată cu dimensiunea datelor de intrare ), rezolvarea problemei, chiar pe un calculator rapid, poate dura foarte mult.

6. Functii componente

6.1. Valid

6.2. Solutie

6.3. Tipar