Algorytmy wyklady, Programowanie dynamiczne, MATRIX-CHAIN-ORDER ( p );


PROGRAMOWANIE DYNAMICZNE

MATRIX-MULTIPLY ( A, B );

{ Oblicza iloczyn : C = A * B }

begin

if kol(A) <> rows(B) then error

else for i := 1 to rows (A) do

for j := 1 to kol (B) do

begin

C [i,j ] := 0;

for k := 1 to kol (A) do

C [i,j ] := C [i,j] + A [i,k] * B [k,j]

end;

return C;

end;

MATRIX-CHAIN-ORDER ( p );

{ p[0..n] - tablica rozmiarów macierzy A1, ... , An ,

tzn .: Ai ma rozmiar p[i-1] * p[i] }

begin

n := length (p) - 1;

for i := 1 to n do

m [i,i] := 0;

for r := 2 to n do

for i := 1 to n-r+1 do

begin

j := i + r - 1;

m [i,j] := ∞;

for k := i to j-1 do

begin

q := m [i,k] + m [k+1, j ] + p i-1 * pk * pj ;

if q < m [i,j ]

then

begin

m [i,j ] := q ;

s [i,j] := k

end

end

end

return m and s

end ;

MATRIX-CHAIN-MULTIPLY ( A, s, i, j);

{Oblicza optymalnie iloczyn Ai * A i+1 * ... * A j }

begin

if j > i

then begin

X := MARTIX-CHAIN-MULTIPLY ( A, s, i, s[i,j ] );

Y := MARTIX-CHAIN-MULTIPLY ( A, s, s[i,j ] +1 , j);

Z := MATRIX-MULTIPLY ( X, Y );

return Z

end

else return Ai

end;


MULTIPLY (A, p);

{Oblicza optymalnie iloczyn A1 * ... * An) }

begin

MATRIX-CHAIN-ORDER (p);

MATRIX-CHAIN-MULTIPLY ( A, s, 1, n )

end;



Wyszukiwarka