Programare dinamică

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ã.