Backtracking

Previzualizare documentatie:

Extras din documentatie:

1.1.1 Prezentare generala

In multe din aplicatiile metodei, solutia se poate exprima sub forma unui vector (x1,x2 xn) unde xi S1, ( ) i {1,2, ,n}, multimile Si fiind finite si ordonate. De multe ori, pentru a fi rezolvata, problema necesita gasire unui vector care maximizeaza (minimizeaza sau satisface) o anumita conditie P (x1, x2, ,xn). Uneori sunt cautati toti vectorii care satisfac P. De exemplu, sortarea crescatoare a tabloului de numere intregi x[1 n] este o problema a carei solutie este de forma unui vector. Daca i este indexul celui mai mic element, conditia P este in acest caz: xi xi +1, i {1,2, ,n}, dar sortarea nu este in mod obisnuit o problema care se rezolva cu ajutorul acestei metode. Presupunem ca mi este cardinalul multimii Si. Fie m (m=m1*m2* *mn) vectori cu n componente care pot satisface conditia P. O metoda directa de gasire a solutiilor, cunoscuta sub numele de metoda fortei brute, ar fi aceea de a genera toti acesti vectori si de a alege doar pe aceia care verifica conditiile problemei. Metoda backtracking are ca avantaj abilitatea de a ne indrepta catre acelasi raspuns, dar efectuand mai putin de m incercari. Ideea de baza este sa construim vectorul solutiilor componenta cu componenta si sa folosim conditii modificate Pk (x1, x2, ,xk), denumite uneori functii, utile pentru a verifica daca vectorul format are sansa de success. Principalul avantaj al acestei metode este urmatorul: daca se constata ca vectorul partial (x1, x2, , xk) nu poate conduce la o solutie "realizabila ", atunci cei mk+1, mn vectori ramasi netestati pot fi ignorati in totalitate. Multe din problemele care se rezolva utilizand metoda backtracking necesita ca solutiile sa satisfaca un set complex de restrictii.

Pentru orice problema, aceste restrictii pot fi impartite in doua categorii: implicite si explicite.

Definitia 1. Restrictiile explicite sunt reguli care impun ca fiecare xk sa ia valori dintr-o multime data.

Exemplul 1:

xk>=0 sau Sk={xk|xk Z+}

(xk=0 sau xk=1) sau Sk {0, 1}

1k <=xk <=uk sau Sk= {a|1k<=a<=uk}

Restrictiile explicite depind de conditia specifica i a fiecarei a problemei de rezolvat. Cu alte cuvinte toti vectorii care satisfac restrictiile explicite definesc spatiul solutiilor posibile S1 x S2 x x Sn.

Definitia 2. Restrictiile implicite sunt reguli care determina ce vectori din domeniul solutiilor lui xk satisfac functia criteriu. Astfel, restrictiile implicite descriu felul in care elementele componente xk trebuie sa se lege intre ele.

1.1.2 Problema celor 8 regine

O problema clasica este plasarea a 8 regine pe o tabla de sah 8 x 8 astfel incat sa nu se atace reciproc, altfel spus, sa nu se afle doua regine pe acelasi rand, pe aceeasi coloana sau diagonala.

Se numeroteaza liniile si coloanele de pe tabla de sah de la 1 la 8. De asemenea, reginele se numeroteaza de la 1 la 8. Daca fiecare regina trebuie sa se afle pe randuri diferite, putem plasa regina k pe linia k. Deci, toate solutiile problemei pot fi reprezentate ca vectori (x1, x2, , x8), unde xk este coloana unde este plasata regina k. Utilizand aceasta formulare, restrictiile explicite sunt Sk = {x1, x2, , x8}, 1<=k<=8.

Rezulta ca domeniul solutiilor este format din 88 vectori. Restrictiile implicite ale problemei impun ca toate elementele xk sa fie diferite intre ele (toate reginele sa se afle pe coloane diferite) si nici o regina sa nu fie pe aceeasi diagonala cu o alta regina. Prima din aceste doua restrictii presupune ca toate solutiile sunt permutari ale vectorului (1, 2, 3, 4,5, 6, 7, 8). Acest lucru reduce marimea domeniului solutiilor de la 88 la 8! posibilitati. Vom incerca sa prezentam in termenii lui xi (coloanele tablei) restrictiile cerute:

Figura

Pentru ca regina de pe linia i coloana xi sa fie pe aceeasi diagonala cu regina de pe linia k si coloana xk, triunghiul dreptunghic care se formeaza ar trebui sa aiba unghiurile de 450, deci sa fie isoscel. Prin urmare catetele de lungimi |i-k| respectiv |xi-xk| trebuie sa fie egale; conditia |i-k| != |xi-xk| exprima faptul ca doua regine nu pot fi plasate pe aceeasi diagonala. Faptul ca nu pot fi plasate doua regine pe aceeasi coloana poate fi exprimat prin conditia xi != xk.

Solutia data in figura este (4, 6, 8, 2, 7, 1, 3, 5)

Download gratuit

Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.

Alte informații:
Tipuri fișiere:
doc
Diacritice:
Da
Nota:
8/10 (1 voturi)
Nr fișiere:
1 fisier
Pagini (total):
21 pagini
Imagini extrase:
21 imagini
Nr cuvinte:
3 598 cuvinte
Nr caractere:
19 230 caractere
Marime:
77.25 KB (arhivat)
Nivel studiu:
Liceu
Tip document:
Documentatie
Materie:
Informatica
Data publicare:
29.07.2017
Structură de fișiere:
  • Backtracking.doc
Predat:
la liceu

Ai gasit ceva în neregulă cu acest document?

Te-ar putea interesa și:
Introducere Metoda backtracking foloseste la rezolvarea multor probleme. Pentru ca o problema sa...
Tehnica Backtracking propune generarea solutiei prin completarea vectorului x in ordine x1x2......
Este una dintre cele mai cunoscute metode de elaborare a algoritmilor. Ea se aplic acelor...
In capitolul 1 am prezentat rutina de backtracking clasica,nerecursiva.In acest capitol prezentam...
Generarea permutarilor. Se citeste un numar natural n. Sa se genereze toate permutarile multimii...
Sus!