Structuri de Date și Algoritmi Curs 6

Curs
8/10 (1 vot)
Domeniu: Calculatoare
Conține 14 fișiere: pdf, ppt, cpp
Pagini : 46 în total
Cuvinte : 1332
Mărime: 194.68KB (arhivat)
Cost: Gratis

Extras din document

Backtracking

generare permutări, generare aranjamente, generare combinări, colorare hartă cu n ţări folosind cel mult 4 culori (ţările vecine sunt colorate diferit), problema comis-voiajorului (vizitarea unică a oraşelor) (Traveling Salesman Problem), plata unei sume dintr-o colecţie de monede, DINAR + MARCA + FRAC = MONEDE, problema labirintului (m linii, n coloane), colorarea unei suprafeţe închise, drapele tricolore cu 6 culori, etc.

interativ

recursiv

Plasarea a N regine pe o tablă de dimensiune NxN

Pt anumite probleme, când nu avem alte metode la dispoziţie

Verifică toate posibilităţile din spaţiul soluţiilor

Ipoteze

Soluţia problemei se scrie sub forma unui vector,

Elementele vectorului aparţin unor mulţimi finite, între ele existând o relaţie de ordine

Construim o soluţie parţială, . Extindem această soluţie şi o testăm.

Dacă soluţia parţială este validă,

continuăm.

altfel

încercăm altă valoare pt x(k).

Dc am testat toate valorile posibile pt x(k), fără succes, ne întoarcem pe poziţia k-1, încercând valorile care au mai rămas pt x(k-1).

Implementare iterativă

void backtrackingIterativ(n)

k = 1//adaugam primul element in vectorul solutiilor

initializareSolutie(k)

while(k>0)

if(potCompletaSolutie(k))//am gasit o solutie valida pt k

if(solutieFinala)//am atins dimensiunea vectorului

tiparesteSolutia;

numaraSolutia;

else

k++;

initializareSolutie(k+1)

else k--

Implementare recursivă

void backtrackingRecursiv(k, n)

if(k = n+1)//solutie finala

tiparesteSolutia;

else

for(toate valorile posibile pt x(k))

if(x(k) este valida) //am gasit o solutie valida pt k

backtrackingRecursiv(k+1, n)

//apelam functia pt pozitia k+1 din vectorul solutie

x(k) = 0;

Conținut arhivă zip

  • backtracking.cpp
  • Curs6_backtracking.pdf
  • Curs6_Backtracking.ppt
  • Curs6_DivideEtImpera.ppt
  • Curs6_greedy.pdf
  • Curs6_Greedy.ppt
  • Curs6_ProgramareDinamica.ppt
  • Curs7_Sortare.ppt
  • DivideEtImpera.pdf
  • divideImpera.cpp
  • greedy.cpp
  • programareDinamica.cpp
  • programareDinamica.pdf
  • sortare.cpp

Alții au mai descărcat și

Proiectarea unei Solutii de Comert Electronic

Comertul electronic reprezinta multitudinea proceselor software si comerciale necesare proceselor business sa functioneze numai, sau în primul...

Sabloane de Proiectare a Interfetelor Utilizator pentru Aplicatii Web

Capitolul 1 Introducere Lucrarea prezinta sabloanele de proiectare , ce sunt acestea si cum ne ajuta ele in rezolvarea problemelor de proiectare...

Algoritmi și Structuri de Date

Introducere: Semiotica se ocupã cu studiul semnelor în natura si în societate. Semnul nu este o calitate în sine a unui obiect, ci o functie pe...

Arbori Partiali de Cost Minim

I. Arbori Fie G un graf orientat. G este un arbore cu radacina r, daca exista in G un varf r din care oricare alt varf poate fi ajuns printr-un...

Algoritmi de Rutare

Algoritmii de rutare pot fi diferenţiaţi după obiectivul particular dorit, impactul asupra reţelei şi resurselor ruterului, metricile folosite....

Modelarea Aplicațiilor Web cu UML 2

Modelarea aplicaţiilor web cu UML 2. Studii de caz Vă prezentăm în continuare (vezi tabelul 1) o metodologie de modelare a unei aplicaţii web cu...

Bazele Matematice ale Graficii 2D

Transformarea de vizualizare. Pentru a prezenta grafic figuri şi imagini trebuie să dispunem de informaţii despre acestea. În general, aceste...

Structuri de Date și Algoritmi

1. Conceptul de dată În informatică, prin dată, se desemnează un model de reprezentare a informaţiei, model cu care se poate opera pentru a obţine...

Ai nevoie de altceva?