Tehnici Avansate de Programare

Metoda Greedy, Backtracking și

Divide-et-Impera

Asist. Univ. Drd. Ing. Mihailescu Marius Iulian

marius.mihailescu@utm.ro

Universitatea Titu Maiorescu

Facultatea de Informatică

Departamentul de Informatică

08.12.2012

Introducere în algoritmi (03.11.2012)

Arbori (17.11.2012)

Grafuri (17.11.2012)

Drumuri în grafuri (17.11.2012)

Metoda Greedy (08.12.2012)

Metoda Backtracking (08.12.2012)

Metoda Divide-et-Impera (08.12.2012)

Metoda Programării dinamice (15.12.2012)

Metoda Branch and Bound (15.12.2012)

Planificare Semestrul I – Anul III ID 2012-2013

Metoda Greedy Prezentare

Probleme propuse

Metoda Backtracking Prezentare

Probleme propuse

Metoda Divide-et-Impera Prezentare

Probleme propuse

Agenda

Metoda Greedy este una din cele mai directe tehnici de proiectare a algoritmilor care se aplică la o varietate largă de probleme.

In general,aceasta metoda se aplica problemelor de optimizare.

Specificul acestei metode consta in faptul ca se construieste solutia optima pas cu pas,la fiecare pas fiind selectat(sau "inghitit") in solutie elementul care pare "cel mai bun"la momentul respectiv,in speranta ca va duce la solutie optima globala.

Metoda Greedy

Presupunem o mulțime A cu n elemente și se cere să se determine o submulțime a sa (B) care satisface anumite restricții.

Soluția respectivă se numește soluție posibilă.

Se cere – determinarea unei soluții posibile care fie să maximizeze fie să minimizeze o anumită funcție obiectiv dată.

Soluția se numește soluție optimă.

Cum lucrează Metoda Greedy?

Metoda Greedy lucrează în paşi astfel:

Multimea B este vida la inceput

Se alege un element din A care pare a fi solutia optima la pasul i

Se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor, dacă da atunci va fi adăugat

Procedeul continuă astfel, repetitiv, până când au fost determinate toate elementele din mulţimea soluţiilor

Cum lucrează Metoda Greedy?

Managerul artistic al unui festival trebuie sa selecteze o multime cat mai ampla de spectacole ce pot fi jucate in singura sala pe care o are la dispozitie.Stiind ca i s`au propus n (n <= 100) spectacole si pentru fiecare spectacol ia fost anuntat intervalul in care se poate desfasura [Si,Fi] (Si reprezinta ora si minutul de inceput,iar Fi ora si minutul de final al spectacolului i),scrieti un program care sa permita spectatorilor vizionarea unui numar cat mai mare de spectacole.

Date de intrare (spectacole.in):

Datele de ieșire (spectacole.out):

Probleme rezolvate cu Metoda Greedy Problema Spectacolelor

Un hot nepravazator are la dispozitie un singur rucsac cu care poate transporta o greutate maxima Gmax.Hotul are de ales din n <= 50 obiecte si,evident,intentioneaza sa obtina un castig maxim in urma singurului transport pe care il poate face. Cunoscand, pentru fiecare obiect i greutatea Gi si castigul Ci pe care hotul l-ar obtine transportand obiectul respectiv in intregime,scrieti un program care sa determine o incarcare optima a rucsacului, in ipoteza ca hotul poate incarca in rucsac orice parte dintr-un obiect.

Date de intrare (rucsac.in): 5 100

1000 120 500 20 400 200 1000 100 25 1

Datele de ieșire (rucsac.out):

2 100.00% 4 79.00% 5 100.00%

Probleme rezolvate cu Metoda Greedy Problema Rucsacului

Backtracking este numele unui algoritm general de descoperire a tuturor soluțiilor unei probleme de calcul, algoritm ce se bazează pe construirea incrementală de soluții-candidat, abandonând fiecare candidat parțial imediat ce devine clar că acesta nu are șanse să devină o soluție validă. [sursa: Wikipedia]

Se poate aplica doar pentru probleme ce admit conceptul de „candidat parțial de soluție” și oferă un test relativ rapid asupra posibilității ca un astfel de candidat să fie completat către o soluție validă. Când se poate aplica, însă, backtrackingul este adesea mult mai rapid decât căutarea prin metoda forței brute prin toți candidații, întrucât este capabilă să elimine dintr-un singur test un mare număr de candidați.

Metoda Backtracking

Problema 1 – Să se genereze în ordine lexico-grafică cuvintele din mulțimea a – h cu n litere și care nu conțin două vocale alăturate.

Problema 2 – Să se genereze cuvintele de k litere care încep cu o vocală și se termină cu o consoană.

Problema 3 - n persoane stau pe scaune numerotate de la 1 la n. Oricare doi vecini

se ceartă. Să se afişeze toate posibilităţile de a-i reaşeza pe scaune astfel încât să nu fie 2 foşti vecini alăturaţi

Probleme rezolvate

Metoda Divide et Impera (Imparte si Stapaneste) este o metoda de programare care se aplica problemelor care pot fi descompuse in subprobleme independente, similare problemei initiale, de dimensiuni mai mici si care pot fi rezolvate foarte usor.

Procesul se reia pana cand (in urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediata.

Metoda Divide-et-Impera

Descompunerea problemei Pb curente in subprobleme independente SubPbi. In cazul in care subproblemele SubPbi. admit o rezolvare imediata se compun solutiile si se rezolva problema Pb

Altfel se descompun in mod similar si subproblemele SubPbi

Cum lucrează metoda Divide-et-Impera?

Se citește un vector cu n componente, numere naturale. Se cere să se tipărească valoarea maximă. Funcția căutată va genera valoarea maximă dintre numerele reținute în

vector pe o poziție dintre i și j (inițial, i=1, j=n). Pentru aceasta, se procedează astfel: dacă i=j, valoarea maxima va fi v[i];

în caz contrar, se imparte vectorul în doi subvectori - presupunem varianta

pentru paralelizare pe 2 procesoare. Se calculează mijlocul m al intervalului [i, j]: m = (i+j) div 2. Primul subvector va conține componentele de la i la m, al doilea va conține componentele de la (m+1) la j; se rezolvă subproblemele (aflându-se astfel maximul pentru fiecare din subvectori), iar soluția curentă va fi dată de valoarea maximă dintre rezultatele celor două subprobleme.

Probleme propuse Valoarea maximă dintr-un vector

Se citește un vector cu n componente numere întregi (numerele se presupun ordonate crescător) și o valoare întreagă ("nr"). Să se decidă dacă nr se găsește sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care conține această valoare.

O rezolvare în care nr se compară pe rând cu toate cele n componente reperzintă o pierdere de performanță (nu exploatează faptul că cele n valori sunt în secvență crescătoare). Algoritmul care va fi propus este optim și se poate spune că face parte dintre algoritmii "clasici".

Funcția care va fi implementată va decide dacă valoarea căutată se găsește printre numerele aflate pe poziții de indice cuprins între i și j (inițial, i=1, j=n). Pentru aceasta, se va proceda astfel: dacă nr coincide cu valoarea de la mijloc, aflată pe poziția de indice (i+j)/2, se tipărește indicele și se revine din apel (problema a fost

rezolvată).

în caz contrar, dacă mai sunt și alte elemente de analizat (adică i<j, deci nu au fost verificate toate pozițiile necesare), problema se descompune astfel: dacă nr este mai mic decât valoarea testată (din mijloc), înseamnă că nu se poate afla pe pozițiile din partea dreaptă, întrucât acestea

sunt cel puțin mai mari decât valoarea testată. Nr se poate găsi doar printre componentele cu indice între i și (i+j)/2 - 1, caz în care se reapelează funcția cu acești parametri;

dacă nr este mai mare decât valoarea testată (din mijloc), înseamnă că nu se poate afla în stânga; se poate găsi doar printre componentele cu indicele între (i+j)/2 + 1 și j, caz în care se reapelează funcția cu acești parametri.

dacă nu mai sunt alte elemente de analizat (pentru că i=j și valoarea din mijloc, v[i], nu coincide cu nr), se concluzionează că nr nu apare în cadrul vectorului.

Această problemă nu mai necesită analiza tuturor subproblemelor în care se descompune, ea se reduce la o singură subproblemă, iar partea de combinare a soluțiilor dispare. În linii mari, această rezolvare este tot de tip "divide et impera".

Probleme propuse Căutarea binară

Sa se determine produsul a n numere intregi

Sa se determine maximul (minimul) a n numere intregi

Sa se determine cel mai mare divizor comun a n valori dintr-un vector

Sa se caute o valoare intr-un vector. Daca se gaseste se va afisa pozitia pe care s-a gasit, altfel se va afisa un mesaj.

Sa se caute o valoare intr-un vector ordonat crescator

Sa se numere cate valori sunt egale cu x dintr-un sir de numere intregi citite.

Probleme propuse