+

Algoritmi i tehnici de programare

Cursul 12

+

Greedy metoda optimului local

Backtracking cutare complet

+Spaiul soluiilor

Fie mulimile , = 1, , card() = , o relaie de

ordine pe

= 1 2 = = 1, 2, , | spaiul soluiilor

: , funcie de validare

= | = mulimea soluiilor rezultat =

: 1 2 , funcii de validare parial 1 = se poate aduga un element cu

= .

+Greedy metoda optimului local

Metod rapid, de complexitate redus, pentru obinerea uneisoluii acceptabile (nu neaprat cea mai bun)

La fiecare pas se alege cea mai bun cale n contextul local,ignornd contextul general

Uneori soluia poate fi cea mai puin dezirabil

Este folosit atunci cnd gsirea celei mai bune soluii esteprea costisitoare.

+Greedy metoda optimului local

Probleme rezolvate prin metoda Greedy

Problema poate fi imaginat ca o mulime cu elemente

O soluie posibil este o submulime ( ) carendeplinete o condiie dat ( este acceptabil);

Pot exista mai multe submulimi diferite acceptabile (soluiiposibile), dintre care una este considerat soluie optim,pe baza unui criteriu care trebuie maximizat (minimizat).

+Greedy metoda optimului local

Operaii (nu snt ntotdeauna evidente)

Alegerea unui element candidat din mulimea ( )

Verificarea acceptabilitii elementului ales: adugareaelementului la soluia parial construit o menineacceptabil sau o face inacceptabil?

{} este acceptabil?

Adugarea elementului ales la soluia parial, dac earmne acceptabil.

= {}

+Greedy metoda optimului local

Algoritm general

se primete mulimea cu elemente

se iniializeaz soluia ca mulime vid

repet de (maxim) ori

alege un element candidat din mulimea

verific dac este soluie acceptabil

dac da, adaug la mulimea : =

se trimite mulimea ca soluie

+Greedy metoda optimului local

Exemple de probleme rezolvate prin algoritmi de tip Greedy:

Determinarea arborelui parial de cost minim (soluia este ntotdeauna optim)

Algoritmul lui Kruskal, algoritmul lui Prim

Problema rucsacului

ntreag: obiectele pot fi transferate doar in intregime;

Continu: pot fi selectate obiecte in intregime sau fractiuni ale obiectelor.

Interclasarea optim a n vectori

Suma maxim dintr-o mulime de numere

Plata unei sume (cu bancnot unitate)

Problema paznicului

Determinarea unui produs de transpoziii

Algoritmul Dijkstra

+Greedy metoda optimului localProblema rucsacului (continu)

// I: capacitate totala (q), nr. obiecte (n), capacitate ocupata (c),// cistig (v)// E: solutia x

void Rucsac_c(float q, int n, float* c, float* x){ float qr;

int i,j;

qr=q;for(i=0; i0; i++)

if(qr>=c[i]){ x[i]=1;

qr=qr-c[i]; //qr=qr - c[i]*x[i]}else{ x[i]=qr/c[i];

qr=0; //qr=qr - c[i]*x[i]for(j=i+1;j

+Backtracking cutare complet

Metod lent, costisitoare, complexitate mare

Verificarea (aproape) tuturor elementelor spaiului soluiilor

= 1, 2, , , , = 1,

=

- condiii de continuare

se construiete element cu element primete o valoare din numai dup toate elementele anterioare (1,2, , 1)

1, 2, , = se trece la elementul + 1

altfel se alege alt valoare pentru

valoarea aleas pentru e consumat mulimea valorilor consumate

dac nu mai snt valori disponibile se revine la elementul anterior

1, 2, , = nu garanteaz obinerea unei soluii rezultat

+Backtracking cutare complet

Forma general a algoritmului iniializare , , , = , = , //construire configuraie iniial

k=

ct timp > //ct timp configuraia nu e final

Dac k== + //configuraie de tip soluie?

reine soluia = , , , k= //revenire dup construirea unei soluii

altfel

dac //mai snt valori neconsumate

alege o valoare = dac (, , , , ) satisfac condiiile de continuare

= //atribuie i avanseaz

= +

altfel //revenire

=

=

+Backtracking cutare complet

Algoritm modificat =

= //primul element minus raia, de multe ori 0=1-1

ct timp >

= //variabila de impas

ct timp < i == //alegerea unei noi valori pentru = + //urmtorul termen n progresie

posibil(,vb) //snt ndeplinite condiiile de continuare

dac == //impas => revenire

=

altfel

dac ==

dac condiii_finale(x) //configuraie soluie?

reine_soluia = , , , altfel //avans

= +

=

+Backtracking cutare complet

Implementarea recursiv Metoda este de natur recursiv, deci uor de implementat

recursiv

Forma recursiv general

backtracking(i)

dac i==n+1

retine_solutia();

altfel

pentru fiecare element j din Si

x[i]=j;

daca posibil(i)

backtracking(i+1);

+Backtracking cutare complet

Exemple de probleme care se rezolv prin metodabacktracking:

Problema celor 8 (n) regine.

Problema cavalerilor mesei rotunde.

Plata unei sume (cu/fr bancnot unitate).

Generarea tuturor permutrilor.

Generarea tuturor aranjamentelor.

Generarea tuturor combinrilor.

Problema colorrii hrilor.

+Backtracking cutare complet

Permutrile unei mulimivoid backtracking()

{

k=0;

init();

while (k>=0)

if (k==n)

{

nrsol++;

printf("Solutia cu nr: %d \n",nrsol);

tipar();

printf("\n");

k--;

}

else

if (st[k]

+Backtracking cutare complet

Permutrile unei mulimivoid init()

{

for (i=0;i