Extras din curs
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
Comertul electronic reprezinta multitudinea proceselor software si comerciale necesare proceselor business sa functioneze numai, sau în primul...
Capitolul 1 Introducere Lucrarea prezinta sabloanele de proiectare , ce sunt acestea si cum ne ajuta ele in rezolvarea problemelor de proiectare...
1. INTRODUCERE ÎN PROIECTAREA ALGORITMILOR 1.1. Definiţii Un algoritm este o metodă de rezolvare pas cu pas a problemelor. O problemă este...
Trei reguli faţă de un sit 1. Respectarea strictă a standardelor internet. 2. Alegerea riguroasă a conţinutului paginilor web. 3. Asigurarea...
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...
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...
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...
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
I. COMPARTIMENTUL ANALITIC 1.1. Caracteristica generală a întreprinderii SA "IUGINTERTRANS" Această întreprindere a fost înfiinţată în acea...
Dintre toate domeniile în care un robot, sau un calculator, poate fi comparat cu performanţele umane, percepţia (şi componenta sa cea mai...
8. Arbori 8.1. Arbori generalizaţi 8.1.1. Definiţii În definirea noţiunii de arbore se porneşte de la noţiunea de vector. Fie V o mulţime având...
Retelele de interconectare sunt de 2 tipuri: a)retele statice la care conexiunile intre noduri sunt fixe si punct la punct-transferul informatiei...
CURS 1. - STRUCTURI DE DATE Scop : prezentarea celor mai importante structuri de date ce pot fi utilizate pentru modelarea datelor din aplicatii....
Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...
De ce SDA? Structuri de date : metode de organizare a unei mari cantitati de informatie Analiza algoritmilor : estimarea timpului de executie si...
Curs 1 - Introducere. Structuri de date - noţiuni generale Introducere Tipuri de bază. Pointeri. Tablouri. Paradigme de programare Programare...