CATEGORII DOCUMENTE |
Metode de elaborare a algoritmilor. Backtracking.
Metoda Backtracking (cautare cu revenire) este o metoda generala de rezolvare a unei clase de probleme de optimizare bazata pe principiul construirii solutiilor, in mod treptat, prin alegeri succesive ale solutiilor partiale. Spre deosebire de metoda Greedy, bazata pe acelasi principiu, Backtracking ofera posibilitatea revenirii asupra unor decizii anterioare, fapt care conduce la obtinerea solutiilor optime globale in orice situatie. In plus, daca sunt mai multe solutii, metoda le determina pe toate.
Metoda cautarii cu revenire realizeaza o explorare sistematica a spatiului solutiilor posibile, construieste solutiile finale, fara a genera insa toate solutiilor posibile din care s-ar putea extrage doar acele solutii ce indeplinesc conditii specifice problemei. Un dezavantaj major al metodei este acela ca este o metoda relativ costisitoare in privinta timpului de executie.
Problemele rezolvabile cu metoda Backtracking sunt probleme in care solutia este reprezentata sub forma unui vector:
,
unde si
sunt multimi finite nu neaparat distincte.
Cerinta problemei este determinarea tuturor solutiilor posibile, care satisfac anumite conditii specifice problemei (denumite conditii interne).
O abordare
simplista ar genera toate solutiile posibile - elementele produsului cartezian , si ulterior s-ar verifica aceste solutii in vederea identificarii acelora
care verifica conditiile interne. Abordarea aceasta este neeficienta. Generarea
tuturor solutiilor implica memorie si timp suplimentar. Backtracking este o
alternativa inspirata de rezolvare a problemelor de acest gen. Metoda evita
generarea tuturor solutiilor posibile, solutiile finale se obtin prin alegerea succesiva de elemente din
multimile
,
, .,
cu posibilitatea revenirii asupra unei alegeri
daca aceasta nu a condus la obtinerea unei solutii finale.
Algoritmii
Backtracking pornesc cu o solutie initiala reprezentata de vectorul vid.
Ulterior acesta va fi marit prin adaugarea elementelor din
multimea corespunzatoare
, treptat
pentru k=1,2,.. Daca vectorul
partial
verifica anumite conditii de validare, deduse
din conditiile interne, se va continua cu augmentarea vectorului curent prin
adaugarea unui nou element
din multimea corespunzatoare
. Daca
vectorul nu indeplineste conditiile de validare se incearca un nou element din
multimea
si se reverifica conditiile de validare.
Exista posiblitatea ca
sa nu mai contina alte elemente care au ramas
neverificate, ceea ce produce o revenire
la o decizie anterioara si incercarea unui alt element pe pozitia anterioara k-1 din vector.
Asupra vectorului solutie se actioneaza prin doar doua operatii: adaugare nou element dupa ultimul adaugat, respectiv, eliminare ultim element adaugat. Aceste operatii corespund unor operatii cunoscute: push si pop; astfel, vectorul solutie functioneaza pe principiul unei stive.
O problema se identifica ca o problema rezolvabila prin metoda Backtracking daca putem identifica urmatoarele aspecte din specificatiile sale:
spatiul solutiilor este un produs cartezian
solutia probleme poate fi reprezentata ca un vector
exista un set de conditii prin care
putem decide daca o solutie partiala data de vectorul ,
este valida → conditiile de validitate
exista un set de conditii prin care putem decide daca o solutie partiala este finala → conditiile de finalitate
solutia (vectorul) se poate construi pas
cu pas, astfel incat daca este valid, are sens completarea vectorului cu
un element pe pozitia k+1.
Consideram solutia partiala reprezentata
ca stiva in imaginile alaturate:
Cazul 1
Nivelul k+1 |
xk+1 |
Nivelul k+1 |
xk+1 |
|
Nivelul k |
xk |
Nivelul k |
xk |
|
Nivelul k-1 |
xk-1 |
Nivelul k-1 |
xk-1 |
|
Nivelul 2 |
x2 |
Nivelul 2 |
x2 |
|
Nivelul 1 |
x1 |
Nivelul 1 |
x1 |
Cazl 2.1
Nivelul k+1 |
xk+1 |
Nivelul k+1 |
xk+1 |
|
Nivelul k |
xk |
Nivelul k |
|
|
Nivelul k-1 |
xk-1 |
Nivelul k-1 |
xk-1 |
|
Nivelul 2 |
x2 |
Nivelul 2 |
x2 |
|
Nivelul 1 |
x1 |
Nivelul 1 |
x1 |
Cazul 2.2
Nivelul k+1 |
xk+1 |
Nivelul k+1 |
xk+1 |
|
Nivelul k |
xk |
Nivelul k |
xk |
|
Nivelul k-1 |
xk-1 |
Nivelul k-1 |
xk-1 |
|
Nivelul 2 |
x2 |
Nivelul 2 |
x2 |
|
Nivelul 1 |
x1 |
Nivelul 1 |
x1 |
Tratarea nivelului k se face diferentiat pentru cazurile urmatoare:
Cazul 1. verifica conditiiile
de validitate: in acest caz se va trece la completarea nivelului urmator al
stivei cu un element
din
. (operatie
push). Daca vectorul partial verifica si conditiile de finalitate
se va furniza solutia.
Cazul 2. NU verifica conditiile de validitate si:
Cazul
2.1. mai exista elemente din care nu au fost incercate, atunci:
- se alege alt
element neincercat din
si se reverifica conditiile de validitate.
Cazul
2.2 Nu mai exista elemente din ramase neincercate, atunci:
- se revine pe nivelul anterior k-1 (operatie pop).
Procesul este
unul repetitiv, pentru fiecare nivel curent al stivei se va proceda similar. Descrierea
algoritmului se poate face in doua variante: iterativ si recursiv, si in ambele
situatii vom considera subalgoritmii de tip functie prin care se verifica
conditiile de validitate respectiv de
finalitate pentru o solutie partiala oarecare .
Functie Valid(k) este:
//verifica
daca solutia partiala din stiva este
valida sau nu
//intoarce Adevarat sau Fals in functie de rezultatul testului
SfFunctie
Functie Final(k) este:
//verifica
daca solutia partiala este finala sau
nu
//intoarce Adevarat sau Fals in functie de rezultatul testului
SfFunctie
Varianta Iterativa:
Algoritm BackTrackingIterativ este:
k=1 //initializarea nivelului stivei
Cattimp (k≥1)
Daca
(
"neincercat" ) atunci
//operatia
push
Daca Valid(k)=Adevarat atunci
Daca Final(k)=Adevarat atunci
Tipareste
"Solutie:" Stiva
Altfel
k=k+1 //trece la alt nivel
SfDaca
SfDaca
Altfel
//operatia pop
k=k-1 //revine la nivelul precedent
SfDaca
SfCattimp
SfAlgoritm
Varianta recursiva:
Subalgoritm Backtracking( k) este: //trateaza nivelul k
Pentru fiecare
//operatia
push
Daca Valid(k)=Adevarat atunci
Daca Final(k)=Adevarat atunci
Tipareste
"Solutie:" Stiva
Altfel
Cheama Backtracking( k+1) //autoapel
SfDaca
SfDaca
SfPentru
SfSubalgoritm
Observatie: In varianta recursiva, operatiile pop (revenirea pe un nivel inferior al stivei solutie) se executa automat la revenirile din apelurile subalgoritmului.
Pentru furnizarea solutiilor, se va apela:
Cheama Backtracking (1).
Problema 1. Problema damelor. Se da o tabla de sah de n linii si n coloane. Avand n regine, se cer toate solutiile de aranjare a reginelor pe tabla de sah, astfel incat oricare doua piese de acest tip sa nu se atace.
Analiza problemei:
Pornind de la
observatia ca doua dame se ataca in conditiile in care ambele se situeaza: fie
pe aceiasi linie, fie pe aceiasi coloana, fie pe o diagonala a tablei de sah,
putem deduce o varianta simplificata de reprezentare a unei solutii prin
impiedicarea oricaror dame de a fi situate pe aceiasi coloana. Consideram
astfel ca dama k este blocata sa
ocupe coloana k a tablei de sah. Astfel, oricare doua dame
sunt pozitionate pe coloane distincte si solutia finala poate fi reprezentata
printr-un vector de n elemente astfel incat:
k- reprezinta indicele coloanei pe care se afla dama k
Stiva[k] - elementul din stiva este indicele liniei ocupate de dama k
Practic, pozitia in stiva: k - corespunde atat indicelui de coloana cat si identificatorului damei, iar valoare de pe nivelul k din stiva coincide cu numarul liniei ocupate de dama k.
Spatiul solutiilor posibile este
produsul cartezian: , unde A=.
Solutia este reprezentata printr-un vector (stiva).
Conditiile ca o solutie partiala sa fie valida se reduc la a verifica daca a k-a dama nu ataca oricare din damele
pozitionate pe primele k-1 coloane.
O solutie este finala daca s-a reusit pozitionarea tuturor damelor, respectiv, dimensiunea vectorului construit este n (s-a completat nivelul n al stivei)
Daca pe tabla de sah sunt dispuse k-1 dame astfel incat acestea nu se ataca (solutie partiala valida), se poate trece la pozitionarea celei de-a k-a piesa.
Pe baza consideratiilor 1-5 problema 1 se poate rezolva printr-un algoritm Backtracking. Algoritmul general descris anterior nu se modifica, in schimb vor fi detaliate functiile Valid si Final:
Functie Valid(k) este
//verifica daca a k-a dama ataca damele 1,2,.,k-1
Valid=Adevarat
Pentru i de la 1 la k-1
Daca () SAU ( (k-i)=(
) ) atunci
/ damele k si i sunt situate pe aceiasi linie sau pe aceiasi diagonala
Valid=Fals
SfDaca
SfPentru
SfFunctie
Functie Final(k) este:
Daca k=n atunci
// am ajuns la nivelul n al stivei - s-au pozitionat toate cele n regine
Final=Adevarat
Altfel
Final=Fals
SfDaca
SfFunctie
Rezolvare1: Programul C pentru rezolvarea problemei damelor (varianta nerecursiva)
#include <stdio.h>
#include <math.h>
int stiva[100]; //solutia se construieste in stiva
int nrsolutii;
int n;
int valid(int k)
int final(int k)
void tipareste()
void main()
}
if (gasit==0) //nu s-au mai gasit
else
if (final(k)==1)
else
k=k+1;
}
printf('n Numarul de solutii=%d',nrsolutii);
Rezolvare2: Programul C pentru rezolvarea problemei damelor (varianta recursiva)
#include <stdio.h>
#include <math.h>
int stiva[100]; //solutia se construieste in stiva
int nrsolutii;
int n;
int valid(int k)
int final(int k)
void tipareste()
void dame(int k)
void main()
Problema 2. Se da un labirint reprezentat sub forma de matrice cu m linii si n coloane, ale carei elemente sunt valori 1 sau 0. Fiecare element al matricei reprezinta o camera a labirintului (1 pentru zid si 0 pentru drum liber). Intr-una din camere, de coordonate Xstart si Zstart se afla o persoana. Determinati toate drumurile prin care persoana va putea iesi din labirint,daca aceasta va putea efectua doar miscari spre Nord, Sud, Est si Vest.
Analiza problemei:
Fie L - matricea de reprezentare a labirintului:
,
O solutie finala a problemei poate fi reprezentata printr-un sir al miscarilor efectuate in labirint, insa configuratia stivei in care sunt salvate camerele traversate este usor modificata fata de problema damelor. Astfel, fiecare pozitie noua pe care o incearca persoana in labirint este identificata prin doua elemente: linia si coloana matricei prin care este reprezentat labirintul. Aceasta observatie ne este utila in modul de construire a stivei: fiecare nivel al stivei necesita memorarea a doua elemente (spre deosebire de rezolvarea problemei 1): linia si coloana pozitiei in matrice.
Acest gen de probleme pentru care fiecare nivel al stivei retine mai multe elemente se rezolva cu un algoritm Backtracking generalizat. Principul aplicat este acelasi ca si la Backtracking-ul simplu: solutia/solutiile se construiesc treptat.
Solutiile finale ale problemei labirintului sunt vectori de perechi (i,j) cu semnificatia pozitiei camerelor prin care a trecut persoana pentru a iesi din labirint. Lungimile acestor vectori solutie sunt diferite. Anumite drumuri parcurse pot fi mai scurte decat altele. Conditia ca un vector de perechi (i,j) sa fie solutie finala a problemei este adevarata daca ultima camera (pozitie) parcursa se afla la marginea labirintului: pe prima sau ultima coloana, sau, pe prima sau ultima linie a matricei de reprezentare.
Conditiile de validitate se deduc din specificatiile problemei. Drumul persoanei poate continua intr-o noua pozitie (i,j) daca valoarea elementului de pe linia i si coloana j din matricea L este 0 (drum liber). Mai mult, pentru a evita parcurgerea acelorasi camere de mai multe ori, se impune restrictia ca pozitiile prin care trece persoana sa fie distincte. Astfel, persoana poate trece intr-o camera vecina daca: nu este zid (camera libera) si nu a mai fost traversata.
De asemenea, tot specificatiile problemei ne indica faptul ca mutarea intr-o noua camera se va face doar prin 4 miscari posibile in pozitiile vecine: stanga, dreapta, sus si jos
In continuare este descris algoritmul backtracking de rezolvare a problemei labirintului (varianta recursiva), punand in evidenta conditiile de validitate si finalitate prin subalgoritmi corespunzatori:
Functie Valid(k)
// k-nivelul stivei
Fie (i,j) -pozitia memorata in Stiva[k]
Daca (a(i,j)=0) atunci
//camera libera
Valid=Adevarat
Pentru l de la 1 la k-1
Daca
atunci
//camera a mai fost traversata in drumul memorat in stiva
Valid=Fals
SfDaca
SfPentru
Altfel
//camera ocupata - zid
Valid=Fals
SfDaca
SfFunctie
Functie Final (k)
Fie (i,j) -pozitia memorata in Stiva[k]
Daca i=1 sau j=1 sau i=m sau j=n atunci
Final=Adevarat
Altfel
Final=Fals
SfDaca
SfFunctie
Subalgoritm Labirint(k) este:
Pentru fiecare vecin posibil (i,j) al camerei salvate in Stiva[k-1]
Stiva[k]=(i,j) //operatia push
Daca Valid(k)=Adevarat atunci
Daca Final(k)=Adevarat atunci
Tipareste "Solutie:" Stiva
Altfel
Cheama Labirint(k+1)
SfDaca
SfDaca
SfPentru
SfSubalgoritm
Rezolvarea
problemei labirintului se face prin initializarea stivei cu pozitia de start: si apelul:Cheama Labirint(1).
Problema rezolvata PERMUTARI: Programul urmator geneeaza permutarile de n prin metoda Backtracking - varianta recursiva.
#include <stdio.h>
int n, stiva[200];
void TiparesteSolutia()
int valid(int k)
void permutari(int k)
void main()
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 1717
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2025 . All rights reserved