Extras din curs
Metoda programãrii dinamice
Problemã generalã
Fie A si B douã multimi oarecare.
Fiecãrui element x.A urmeazã sã i se asocieze o valoare v(x).B.
Initial v este cunoscutã doar pe submultimea X.A, X.O.
Pentru fiecare x.AX sunt cunoscute:
Ax.A : multimea elementelor din A de a cãror valoare depinde v(x);
fx : functie care specificã dependenta de mai sus. Dacã Ax={a1,...,ak}, atunci v(x)=fx(v(a1),...,v(ak)).
Se mai dã z.A.
Se cere sã se calculeze, dacã este posibil, valoarea v(z).
Exemplu. Considerãm:
A={1,2,...,5};
X={1,2};
A3={1,2,4}; A4={1,2}; A5={1,3};
Elementele din X au asociatã valoarea 1.
Fiecare functie fx calculeazã v(x) ca fiind suma valorilor elementelor din Ax. Alegem z=5. O ordine posibilã de a considera elementele lui AX astfel încât sã putem calcula valoarea asociatã lor este: 4,3,5. Astfel:
v(4) = v(1) + v(2) = 2,
v(3) = v(4) + v(1) + v(2) = 4,
v(5) = v(1) + v(3) = 5
Lucrurile devin mai clare dacã reprezentãm problema pe un graf de dependente. Vârfurile corespund elementelor din A, iar descendentii unui vârf x sunt vârfurile din Ax. Vârfurile din X apar subliniate.
Problema enuntatã nu are totdeauna solutie, asa cum se vede pe graful de dependente de mai jos, în care existã un circuit care nu permite calculul lui v în z=3.
4
5
3
2
1
1
3
4
2
2
Observatii:
- A poate fi chiar infinitã;
- B este de obicei N, Z, R, {0,1} sau un produs cartezian;
- fx poate fi un minim, un maxim, o sumã etc.
Pentru orice x.A, spunem cã x este accesibil dacã, plecând de la X, poate fi calculatã valoarea v(x). Evident, problema are solutie dacã si numai dacã z este accesibil.
Pentru orice x.A, notãm prin Ox multimea vârfurilor observabile din x, adicã multimea vârfurilor y pentru care existã un drum de la y la x (a elementelor de a cãror valoare depinde valoarea lui x).
Problema enuntatã are solutie dacã si numai dacã:
1) Oz nu are circuite;
2) vârfurile din Oz în care nu sosesc arce fac parte din X.
. Încercare de rezolvare cu metoda Divide et Impera
Este folositã o procedurã DivImp, apelatã prin DivImp(z).
procedure DivImp(x)
for toti y.AxX
DivImp(y)
calculeazã v(x) conform functiei fx
end;
Apare un avantaj: sunt parcurse doar vârfurile din Oz. Dezavantajele sunt însã decisive pentru renuntarea la aceastã încercare:
- algoritmul nu se terminã pentru grafuri ciclice;
- valoarea unui vârf poate fi calculatã de mai multe ori, ca de exemplu pentru situatia:
Este evident cã problema se transpune imediat la grafurile de dependentã: se cere o parcurgere a vârfurilor grafului astfel încât dacã existã un arc de la i la j, atunci i trebuie vizitat/prelucrat înaintea lui j (adicã o sortare topologicã a vârfurilor grafului indus de vârfurile observabile din z).
3
. Solu.ie: Sortarea topologicã pentru graful indus de vârfurile observabile din z
Etapele sunt urmãtoarele:
- identificãm Gz = subgraful asociat lui Oz ;
- aplicãm sortarea topologicã.
Observatii:
- problema are solutie dacã si numai dacã graful este aciclic;
- dacã existã solutie, ea nu este neapãrat unicã.
Ar fi totusi mai bine dacã :
- am cunoaste de la început Gz;
- forma grafului ar permite o parcurgere mai simplã.
Preview document
Conținut arhivă zip
- Programare Dinamica.pdf