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;