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 soluții de comerț electronic

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

Șabloane de proiectare a interfețelor utilizator pentru aplicații web

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

Proiectarea Algoritmilor

1. INTRODUCERE ÎN PROIECTAREA ALGORITMILOR 1.1. Definiţii Un algoritm este o metodă de rezolvare pas cu pas a problemelor. O problemă este...

Design-ul și Machetarea Paginilor Web

Trei reguli faţă de un sit 1. Respectarea strictă a standardelor internet. 2. Alegerea riguroasă a conţinutului paginilor web. 3. Asigurarea...

Curs Excel

1. Noţiuni de bază 1.1. Lansarea în execuţie a programului Programul Excel, la fel ca şi programul Word, face parte din pachetul Microsoft...

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...

Concepte de Bază ale Tehnologiei Informației

Modulul 1 – Concepte de bază ale Tehnologiei informaţiei (IT) 1.1. Concepte generale 1.1.1. Hardware, Software, IT Ceea ce noi numim Tehnologia...

Informatică

Noţiunea de informatică - Informatica este un termen preluat din limba franceză (informatique), provenind din combinarea primei părţi a...

Te-ar putea interesa și

Întreprinderea SA Iugintertrans 2006

I. COMPARTIMENTUL ANALITIC 1.1. Caracteristica generală a întreprinderii SA "IUGINTERTRANS" Această întreprindere a fost înfiinţată în acea...

Generalități despre sistemele de vedere artificială

Dintre toate domeniile în care un robot, sau un calculator, poate fi comparat cu performanţele umane, percepţia (şi componenta sa cea mai...

Programare paralelă în sisteme distrbuite

Retelele de interconectare sunt de 2 tipuri: a)retele statice la care conexiunile intre noduri sunt fixe si punct la punct-transferul informatiei...

Structuri de Date

CURS 1. - STRUCTURI DE DATE Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii....

Structuri de Date și Algoritmi

Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...

Structuri de Date și Algoritmi

De ce SDA? Structuri de date : metode de organizare a unei mari cantitati de informatie Analiza algoritmilor : estimarea timpului de executie si...

Structuri de Date și Algoritmi - Curs 1

Curs 1 - Introducere. Structuri de date - noţiuni generale Introducere Tipuri de bază. Pointeri. Tablouri. Paradigme de programare Programare...

Structuri de Date și Algoritmi - Curs 2

Curs 2 – Liste simplu înlănţuite Structura unei liste. Definirea elementului listei Element Listă Curs 2 – Liste simplu înlănţuite typedef int...

Ai nevoie de altceva?