Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


METODE DE ELABORARE A ALGORITMILOR. BACKTRACKING.

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Determinarea elementului mediu
Tipuri de date predefinite
Analiza eficientei algoritmilor
Tablouri de pointeri, pointeri pe pointeri
Operatori aritmetici
PROGRAMARE IN C
Pointeri pe caractere si functii
Comaparatie pointeri
ARBORI - ARBORI PARTIAL ORDONATI. VECTORI HEAP
Derivare publica, functii virtuale

TERMENI importanti pentru acest document

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



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 963
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site