Problema Rucsacului

Algoritmica - Curs 12 1

CURS 11:

Programare dinamic- II -


Structura

Ce este programarea dinamic ?

Aplicaie: problema discret a rucsacului

Funcii de memorie (memoizare)

Aplicaie: nmulirea optimal a matricilor

Aplicaie: nchiderea tranzitiv a unei relaii binare



Este o tehnic de rezolvare a problemelor care pot fi descompusen subprobleme care se suprapun poate fi aplicat problemelorce au proprietatea de substructur optim

Particularitatea programrii dinamice const n faptul c rezolvfiecare subproblem o singur dat i stocheaz soluiilesubproblemelor ntr-o structur tabelar



Etapele principale:

Analiza structurii unei soluii: se stabilete legatura dintre soluiaproblemei i soluiile subproblemelor (este echivalent cu verificarea proprietii de substructur optim). In aceasta etapse identific problema generic i subproblemelecorespunztoare.

Determinarea relaiei de recuren dintre valoarea (criteriul de optim) corespunztoare soluiei problemei i valorilecorespunztoare soluiilor subproblemelor.

Dezvoltarea (n manier ascendent) a relaiei de recuren icompletarea structurii tabelare utile n construirea soluiei.

Construirea soluiei (utiliznd informaiile completate n etapaanterioar)


Aplicaie: problema rucsacului

Considerm un set de n obiecte, fiecare fiind caracterizat de o dimensiune d i de o valoare v, i un rucsac de capacitate C. Sse selecteze un subset de obiecte astfel incat dimensiunea totala obiectelor selectate s fie mai mica dect C iar valoarea total a obiectelor selectate s fie maxim.

Variante:(i) Varianta continu (fracionara): pot fi selectate obiecte in

ntregime sau fraciuni ale obiectelor.(ii) Varianta discret(0-1): obiectele pot fi transferate doar n

ntregime



Ipoteza (varianta simplificat): Capacitatea rucsacului (C ) i dimensiunile obiectelor d1,,dn sunt

numere naturale

Problema rucsacului poate fi reformulat astfel:se caut (s1,s2,,sn) cu si in {0,1} astfel nct:

s1d1 ++ sndn



Exemplu: n=3, C=5, d1=1, d2=2, d3=3v1=6, v2=10, v3=12

Valoare relativa: vri=vi/di

vr1=6, vr2=5, vr3=4

Ideea tehnicii greedy: Se sorteaz lista de obiecte

descresctor dup valoarearelativ (vri=vi/di)

Se selecteaz obiectele n aceast ordine pn cnd nu maincap elemente in rucsac

Soluia greedy: (1,1,0)Valoarea total: V=16

Obs: aceasta nu este soluia optim; soluia (0,1,1) este mai bun ntruct V=22



1. Analiza structurii unei soluii optimeFie P(i,j) problema generic a seleciei din setul de obiecte {o1,,oi}

pentru a umple optimal un rucsac de capacitate j.Obs: P(n,C) este problema initiala Daca i se ajunge la subproblema P(i-1,j) i dac s(i,j) este optim pt pb. P(i,j) atunci i s(i-1,j) trebuie sfie solutie optim pentru subproblem

Deci problema rucsacului are proprietatea de substructur optim



2. Stabilirea relaiei de recuren

Fie V(i,j) valoarea corespunztoare soluiei a problemei P(i,j)

0 dac i=0 sau j=0 (multimea de obiecte este vida saucapacitatea disponibil n rucsac e 0)

V(i,j) = V(i-1,j) daca di>j sau V(i-1,j)>V(i-1,j-di)+ vi(obiectul i nu incape in rucsac sau prin selectia lui s-arobtine o solutie mai putin buna decat daca obiectulnu s-ar selecta)

V(i-1,j-di)+vi in celelalte cazuri



Relaia de recuren poate fi descris i astfel:

0 daca i=0 sau j=0

V(i,j) = V(i-1,j) daca di>j

max{V(i-1,j), V(i-1,j-di)+ vi } daca di



Exemplu:

0 daca i=0 sau j=0

V(i,j) = V(i-1,j) daca di>j

max{V(i-1,j), V(i-1,j-di)+ vi } if di



3. Dezvoltarea relaiei de recurenta

0 daca i=0 sau j=0

V(i,j) = V(i-1,j) if di>j

max{V(i-1,j), V(i-1,j-di)+ vi } if di



4. Construirea solutiei

Exemplu:

0 1 2 3 4 50 0 0 0 0 0 0

1 0 6 6 6 6 6

2 0 6 10 16 16 16

3 0 6 10 16 18 22

Etape:

Compar V[3,5] cu V[2,5]. Intruct valorile sunt diferite inseamn c o3 esteselectat

Se trece la V[2,5-d3]=V[2,2]=10 i se compar cu V[1,2]=6. Intruct valorilesunt diferite inseamn c o2 este de asemenea selectat

Se trece la V[1,2-d2]=V[1,0]=0. Intruct s-a ajuns la 0 rezult c s-a ajuns la soluie

Soluia obinut este{o2,o3} adic s=(0,1,1)Obs: se presupune ca cel puin un obiect are

dimensiunea mai mic dect capacitatearucsacului



4. Construirea soluiei

Exemplu:

0 1 2 3 4 50 0 0 0 0 0 0

1 0 6 6 6 6 6

2 0 6 10 16 16 16

3 0 6 10 16 18 22

Algoritm:

Construct(V[0..n,0..C],d[1..n])FOR i1,n DO s[i] 0 ENDFORin; jCWHILE V[i,j]>0 DO

IF V[i,j]=V[i-1,j]THEN ii-1

ELSEs[i] 1jj-d[i]ii-1

ENDIFENDWHILERETURN s[1..n]



Obs

0 1 2 3 4 50 0 0 0 0 0 0

1 0 6 6 6 6 6

2 0 6 10 16 16 16

3 0 6 10 16 18 22

Pt a construi soluia sunt suficiente doarvalorile marcate

Numrul calculelor poate fi redus dacse calculeaz doar valorilenecesare construciei solutiei

Acest lucru se poate realiza prinmbinarea abordrii descendentecu cea ascendent (cu reinereavalorilor calculate)

Aceasta este denumita tehnicamemoizrii (engleza: memoization)


Tehnica memoizrii

Scop: se rezolva doar subproblemele a cror soluie intervine in soluia problemei initiale (in plus o subproblem este rezolvato singur dat)

Idee: se combin abordarea descendent (top down) cu ceaascendent (bottom up)

Motivatie: Abordarea descendent clasic rezolv doar subproblemele ce

contribuie la solutia problemei insa o subproblema este rezolvatade cate ori apare (din acest motiv implementarea recursiva estein general ineficienta)

Abordarea ascendenta clasica rezolva toate subproblemele (chiarsi cele care nu contribuie la solutia optima) insa fiecare problemaeste rezolvata o singura data

Tehnica memoizarii rezolva o singura data doar subproblemele cecontribuie la solutia problemei


Tehnica memoizriiEtape in aplicarea tehnicii

memoizarii: Se initializeaza tabelul cu o

valoare virtuala (aceasta valoare trebuie sa fie diferita de orice valoare s-ar obtine prin dezvoltarea relatiei de recurenta)

Se calculeaza valoarea tinta (ex: V[n,C]) in maniera recursiva insa toate valorile intermediare se stocheaza si se utilizeaza atunci cand e necesar

Initializare cu valoarea virtuala:FOR i0,n DOFOR j0,C DO V[i,j] -1 ENDFOR

ENDFORImplementare recursiva:comp(i,j)IF i=0 OR j=0 THEN V[i,j] 0; RETURN V[i,j]ELSE

IF V[i,j]-1 THEN RETURN V[i,j]ELSEIF j



Se dau n matrici A1, A2, , An si se urmrete calculul produsuluiA1*A2** An . S se determine o modalitate de grupare a matricilor

factor astfel nct numrul produselor de elemente sa fie minim

Obs:

1. Dimensiunile matricilor sunt compatibile. Presupunem cdimensiunile matricilor sunt: p0,p1,,pn Matricea Ai are pi-1 liniisi pi coloane

2. Diferitele grupri ale factorilor conduc la acelai rezultat (intruct nmulirea matricilor este asociativ) ins pot conduce la valoridiferite ale numrului de inmuliri de elemente



Exemplu: Fie A1, A2 si A3 trei matrici avnd dimensiunile: (2,20), (20,5) si (5,10)

p0=2 p1=20 p2=5 p3=10

Considerm urmtoarele grupri:

(A1*A2)*A3 - aceasta necesita (2*20*5)+2*5*10=300 inmultiriscalare (la nivel de element)

A1*(A2*A3) aceasta necesita (20*5*10)+2*20*10=1400 inmultiriscalare

Obs: pentru valori mari ale lui n numarul de grupari posibile poate fifoarte mare


Aplicatie: inmultirea optimala a matricilor

Gruparea factorilor are, in cazul general, un caracter ierarhic:

Primul nivel al gruparii corespunde ultimei inmultiri efectuate Celelalte nivele corespund gruparilor factorilor ramasi

Gruparea este identificata prin pozitia ultimei inmultiri. De exemplu gruparea

(A1**Ak)*(Ak+1**An)este specificata prin indicele de grupare k

La primul nivel exista (n-1) grupari posibile (1



Numarul de grupari pentru un produs cu n factori este:

1 n2

Obs:K(n)=C(n-1) unde C(0),C(1) sunt numerele lui Catalan:

C(n)=Comb(2n, n)/(n+1)

Ordinul de marime al lui K(n) este 4n-1/(n-1)3/2Tehnica fortei brute este inaplicabila!



1. Analiza structurii unei solutii optime

Fie A(i..j) produsul Ai*Ai+1**Aj (i



2. Identificarea relaiei de recuren

Fie c(i,j) numrul de nmuliri scalare necesare pentru a calcula A(i..j).

0 daca i=jc(i,j)=

min{c(i,k)+c(k+1,j)+pi-1pkpj | i



3. Dezvoltarea relaiei de recuren

0 if i=jc(i,j)=




Analiza complexitii:

Dimensiunea problemei: n

Operaie dominant: inmultirescalara

Ordin complexitate: (n3)

AlgoritmCompute(p[0..n])FOR i1,n DO c[i,i] 0 ENDFORFOR q 1,n-1 DO

FOR i 1,n-q DOj i+qc[i,j] c[i,i]+c[i+1,j]+p[i-1]*p[i]*p[j]s[i,j] iFOR k i+1,j-1 DO

r c[i,k]+c[k+1,j]+p[i-1]*p[k]*p[j] IF c[i,j]>r THEN c[i,j] r

s[i,j] kENDIF

ENDFORENDFOR ENDFOR

RETURN c[1..n,1..n],s[1..n,1..n]



4. Construirea solutiei

Variante ale problemei:

Determinarea numarului minim de inmultiri scalareSolutie: este data de c(1,n)

Calcul A(1..n) in maniera optimalaSolutie: algoritm recursiv (opt_mul)

Identificarea gruparii optimale a factorilor (plasarea parantezelor)Solutie: algoritm recursiv (opt_group)



Calculul lui A(1..n) in maniera optimala

Ipoteze: A[1..n] un tablou global avand elemente de tip matrice (A[i] este

matricea Ai) s[1..n,1..n] este o variabila globala iar classic_mul este o functie

pentru calculul produsului a doua matrici

opt_mul(i,j)IF i=j THEN RETURN A[i]ELSE

X opt_mul(i,s[i,j]) Y opt_mul(s[i,j]+1,j)Z classic_mul(X,Y)RETURN Z

ENDIF



Afisarea gruparii optimale (pozitiile unde se plaseaza parantezele)

opt_group(i,j)IF ij THEN

opt_group(i,s[i,j])WRITE i-1, s[i,j], jopt_group(s[i,j]+1,j)

ENDIF


Aplicatie: inchiderea tranzitiva a unei relatii binare

Fie R {1,2,,n}x{1,2,,n} o relatie binara. Inchiderea sa tranzitiva este cea mai mica (in sensul relatiei de incluziune) relatie R* care este tranzitiva si include pe R

R* are urmatoarele proprietati:

daca i si j sunt din {1,,n} si exista i1,i2,.im in {1,2,,n} astfel incat (i1,i2) in R, ., (im-1,im ) in R i1=i si im=jatunci (i,j) in R

Exemple: a) R={(1,2),(2,3)} R*={(1,2),(2,3),(1,3)}

b) R={(1,2),(2,3),(3,1)} R*={(1,2),(2,3),(3,1),(1,3),(1,1),(2,1),(2,2),(3,2),(3,3)}



R* este construita succesiv pornind de la R0=R si utilizand R1, R2,Rn=R*

Relatiile intermediare Rk (k=1..n) sunt definite prin:

(i,j) in Rk < = > (i,j) in Rk-1 sau (i,k) Rk-1 si (k,j) in Rk-1

Exemplu:R={(1,2),(2,3)} R1=RR2={(1,2),(2,3),(1,3)} R*=R3 ={(1,2),(2,3),(1,3)}



Reprezentarea relatiilor binare:

Presupunem ca o relatie binara este specificata printr-o matrice n*n ale carei elemente sunt definite astfel:

1 daca (i,j) in R r(i,j) =

0 daca (i,j) nu apartine lui R

Exemplu: R ={(1,2),(2,3)} 0 1 0

r= 0 0 10 0 0



Relatia de recurenta pentru matrici:

1 if rk-1(i,j)=1 OR (rk-1(i,k)=1 AND rk-1(k,j)=1)rk(i,j) =

0 altfel

Exemplu:0 1 0 0 1 0 0 1 1 0 1 1

r= 0 0 1 r1= 0 0 1 r2= 0 0 1 r3= 0 0 10 0 0 0 0 0 0 0 0 0 0 0



Algoritm Warshall

Dezvolta relatia de recurenta folosind doua matrici aditionale r1 si r2

Closure(r[1..n,1..n])r2[1..n,1..n] r[1..n,1..n]FOR k 1,n DO

r1[1..n,1..n] r2[1..n,1..n]FOR i 1,n DOFOR j 1,n DOIF r1[i,j]=0 OR r1[i,k]=1 AND r1[k,j]=1

THEN r2[i,j] 1ELSE r2[i,j] 0

ENDIFENDFOR

ENDFORENDFORRETURN r2[1..n,1..n]


Cursul urmator va fi despre

Backtracking

si aplicatii

Slide Number 1StructuraCe este programarea dinamic ?Ce este programarea dinamic ?Aplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiAplicaie: problema rucsaculuiTehnica memoizriiTehnica memoizriiAplicaie: nmulirea optimal a matricilorAplicaie: nmulirea optimal a matricilorAplicatie: inmultirea optimala a matricilorAplicatie: inmultirea optimala a matricilorAplicatie: inmultirea optimala a matricilorAplicaie: nmulirea optimal a matricilorAplicaie: nmulirea optimal a matricilorAplicaie: nmulirea optimal a matricilorAplicaie: nmulirea optimal a matricilorAplicaie: nmulirea optimal a matricilorAplicatie: inmultirea optimala a matricilorAplicatie: inmultirea optimala a matricilorAplicatie: inchiderea tranzitiva a unei relatii binareAplicatie: inchiderea tranzitiva a unei relatii binareAplicatie: inchiderea tranzitiva a unei relatii binareAplicatie: inchiderea tranzitiva a unei relatii binareAplicatie: inchiderea tranzitiva a unei relatii binareCursul urmator va fi despre

Problema Rucsacului

Documents

Transcript of Problema Rucsacului