Metoda backtracking

5x puncte

categorie: Istorie

nota: 9.90

nivel: Liceu

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A1,A2 ...,An si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

De exemplu, daca dorim sa gener[...]
DOWNLOAD REFERAT

Preview referat: Metoda backtracking

La intalnirea unei astfel de probleme, daca nu cunoastem aceasta tehnica, suntem tentati sa generam toate elementele produsului cartezian A1,A2 ...,An si fiecare element sa fie testat daca este solutie. Rezolvand problema in acest mod, timpul de executie este atat de mare, incat poate fi considerat infinit, algoritmul neavand nici o valoare practica.

De exemplu, daca dorim sa generam toate permutarile unei multimi finite A, nu are rost sa generam produsul cartezian AxAx.....xA, pentru ca apoi, sa testam, pentru fiecare element al acestuia, daca este sau nu permutare (nu are rost sa generam 1.1,1.......1, pentru ca apoi sa constatam ca nu am obtinut o permutare, cand de la a doua cifra 1 ne puteam da seama ca cifrele nu sunt distincte).

Am aratat ca orice solutie se genereaza sub forma de vector. Vom considera ca generarea solutiilor se face intr-o stiva. Astfel, x1 a,Z A1, se va gasi pe primul nivel al stivei, x2 a,Z A2 se va gasi pe al doilea nivel al stivei,... xk a,Z Ak se va gasi pe nivelul k al stivei. In acest fel, stiva (notata ST) va arata astfel:
ST
Nivelul k+1 al stivei trebuie initializat (pentru a alege, in ordine, elementele multimii k+1 ). Initializarea trebuie facuta cu o valoare aflata (in relatia de ordine considerata, pentru multimea Ak+1 ) inaintea tuturor valorilor posibile din multime. De exemplu, pentru generarea permutarilor multimii , orice nivel al stivei va lua valori de la 1 la n. Initializarea unui nivel (oarecare) se face cu valoarea 0. Procedura de initializare o vom numi INIT si va avea doi parametri: k (nivelul care trebuie initializat si ST (stiva)).

Gasirea urmatorului element al multimii Ak (element care a fost netestat) se face cu ajutorul procedurii SUCCESOR (AS,ST,K). Parametrul AS (am succesor) este o variabila booleana. In situatia in care am gasit elementul, acesta este pus in stiva si AS ia valoarea TRUE, contrar (nu a ramas un element netestat) AS ia valoarea FALSE..
Odata ales un element, trebuie vazut daca acesta indeplineste conditiile de continuare (altfel spus, daca elementul este valid). Acest test se face cu ajutorul procedurii VALID (EV,ST,K).
Testul daca s-a ajuns sau nu la solutia finala se face cu ajutorul functiei SOLUTIE(k) iar o solutie se tipareste cu ajutorul procedurii TIPAR. Prezentam in continuare rutina Backtracking:
DOWNLOAD REFERAT
« mai multe referate din Istorie

CAUTA REFERAT


TRIMITE REFERAT CERE REFERAT
Referatele si lucrarile oferite de E-referate.ro au scop educativ si orientativ pentru cercetare academica.