Metoda Backtracking

Proiect
8/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 27 în total
Cuvinte : 1987
Mărime: 4.40MB (arhivat)
Cost: 5 puncte
Profesor îndrumător / Prezentat Profesorului: Prof. Ing. Stan Maria
pentru c++

Cuprins

1.DESCRIEREA GENERALA A METODEI BACKTRACKING

2.MECANISMUL METODEI BACKTRACKING

3.EXEMPLE DE IMPLEMENTARE ALE ALGORITMULUI

DESCRIEREA GENERALA A METODEI BACKTRACKING

Extras din document

Metoda backtracking se utilizeaza pentru rezolvarea unor probleme in care:

- se obtin mai multe solutii;

-solutia este formata din unul sau mai multe elemente, fiind reprezentata printr-un tablou X=(x1,x2,…,xn) unde x1 M1,x2 M2,…,xn Mn;

-tabloul X este o structura finala de stiva;

-multimile M1,M2,…,Mn sunt multimi finite avand c1,c2,…,cn elemante;

-elementele depuse in tablou indeplinesc anumite conditii impuse de enuntul fiecarei problem.

Generarea tuturor tablourilor X cu elementele produsului cartezian M1*M2*…*Mn-numit spatial solutiilor posibile- conduce la un timp de executie foarte mare.

Metoda Backtracking are la baza o strategie prin care se genereaza doar solutiile care indeplinesc conditiile specific problemei, denumite conditii interne.

Solutiile posibile care respecta conditiile interne se numesc solutii rezultat.

Daca un element xj primeste o valoare din multimea Mj care este admisa in solutia rezultat, aceasta valoare se numeste valoare valida.Conditiile de validare sunt deduse din conditiile interne.

EXEMPLU:

Sa se determine toate modalitatile de colorare a tarilor de pe o harta,folosind un numar minim de culori precizat,spre exemplu, 4 culori.Conditia interna rezulta din asezarea tarilor pe harta;pentru a fi vizibile,zonele geografice invecinate –tarile-trebuie colorate distinct.Conditiile de validare se obtin prin compunerea urmatoarelor conditii simple:daca tara i este vecina cu tara j (in matricea de vecinatati M[i][j]=1) atunci culoarea folosita pentru tara i trebuie sa difere de culoarea folosita pentru tara j(in tabloul solutie,X[i]<>X[j]).

Problemele care se rezolva cu aceasta metoda pot avea anumite particularitati:

-numarul n de elemente care pot participa la construirea unei solutii nu este o valoare constanta(fixa) ;

-se poate obtine si o singura solutie,denumita solutie optima;

-elementele x1,x2,x3,…,xn ale unei solutii pot fi si ele tablouri;

-multimile M1,M2,M3,…,Mn pot avea aceleasi elemente.

Exemplu:

Sa se genereze toate numerele naturale cu trei cifre distinct din multimea {1,2,4}

Solutie:

Spatiul solutiilor posibile S=({1,2,4}x{1,2,4}x{1,2,4}={1,1,1},{1,1,2},{1,1,4},{1,2,1},{1,2,2},…,{4,4,4})

Rezolvarea problemei prin generarea tuturor solutiilor conduce la 27 de solutii posibile,dintre care doar 6 sunt solutii rezultat.In tabel s-au generat toate solutiile posibile fiind marcate solutiile rezultat.

Preview document

Metoda Backtracking - Pagina 1
Metoda Backtracking - Pagina 2
Metoda Backtracking - Pagina 3
Metoda Backtracking - Pagina 4
Metoda Backtracking - Pagina 5
Metoda Backtracking - Pagina 6
Metoda Backtracking - Pagina 7
Metoda Backtracking - Pagina 8
Metoda Backtracking - Pagina 9
Metoda Backtracking - Pagina 10
Metoda Backtracking - Pagina 11
Metoda Backtracking - Pagina 12
Metoda Backtracking - Pagina 13
Metoda Backtracking - Pagina 14
Metoda Backtracking - Pagina 15
Metoda Backtracking - Pagina 16
Metoda Backtracking - Pagina 17
Metoda Backtracking - Pagina 18
Metoda Backtracking - Pagina 19
Metoda Backtracking - Pagina 20
Metoda Backtracking - Pagina 21
Metoda Backtracking - Pagina 22
Metoda Backtracking - Pagina 23
Metoda Backtracking - Pagina 24
Metoda Backtracking - Pagina 25
Metoda Backtracking - Pagina 26
Metoda Backtracking - Pagina 27

Conținut arhivă zip

  • Metoda Backtracking.doc

Alții au mai descărcat și

Tehnici de Programare

LIMBAJUL DE PROGRAMARE JAVA Java este un limbaj de programare de nivel înalt, dezvoltat de JavaSoft, companie în cadrul firmei Sun Microsystems....

Arhitectura Calculatoarelor - Intel vs AMD

Rezultatele din testul 3DS Max 7 SPECapc Test Testul alaturat consta in crearea modelelor 3D, modificarea si randarea scripturilor. Conform...

Backtracking Labirint

#include <iostream> #include <fstream> // Moraru-backtracking generalizat pg.221 problema 51 using namespace std; int...

Grafuri

SCURT ISTORIC AL TEORIEI GRAFURILOR Originile teoriei grafurilor se gãsesc în rezolvarea unor probleme de jocuri si amuzamente matematice,care au...

Metoda Backtracking

Prezentarea tehnicii Backtracking Aceasta tehnica se foloseste în rezolvarea problemelor care îndeplinesc simultan urmatoarele conditii: -...

Metoda Backtracking, Arbori, Grafuri, Greedy, Divide et Impera, Metoda Programarii Dinamice, Algoritmi

• Arbori Numim arbore un graf neorientat conex şi fără cicluri. Aceasta nu este singurul mod în care putem defini arborii. Câteva definiţii...

Ai nevoie de altceva?