Количество умножений чисел, при умножении матриц Опции

[samec]

Даны три матрицы A(m1,n1); B(m2,n2); C(m3,n3). Как мне вычислить количество умножений чисел, которое потребуется для умножения матриц, например, следующим образом (A*B)*C ??

[samec]

это выяснил, если:
A(k,n)*B(n,m) = AB(k,m)
число умножений k*n*m
AB(k,m)*C(m,l) = ABC(k,l)
число умножений k*m*l
в результате k*n*m + k*m*l.
А вот если матриц у меня от 1 до n штук, то как мне расставить скобки при умножении этих матриц, чтобы количество умножений чисел было минимальным ??

[Lapp]

Могу дать тебе половину решения..
Вот программа, которая выдает само минимальное количество умножений, но не говорит, как расставить скобки. Попробуй разобраться с ней и добавить расстановку скобок .

Начальные данные задаются в константе Dim. При этом, поскольку соседние размерности одинаковые, я не повторяю их. Например, если у тебя есть 5 матриц таких размеров:
(3,4), (4,5), (5,6), (6,7), (7,2)
- то в массив Dim (его размер будет 5+1=6) надо занести:
3, 4, 5, 6, 7, 2
(Этот пример как раз использован в программе)

const
  n=5;

type
  tDim=array[1..n+1]of integer;

const
  Dim:tDim=(3,4,5,6,7,2);

var
  i,L:integer;

function MinMult(L:integer):integer;
var
  i,j,k,q,D,Mult:integer;
begin
  if L=2 then MinMult:=Dim[1]*Dim[2]*Dim[3]
  else begin
    k:=MaxInt;
    for j:=1 to L-1 do begin
      Mult:=Dim[j]*Dim[j+1]*Dim[j+2];
      D:=Dim[j+1];
      for i:=j+1 to L do Dim[i]:=Dim[i+1];
      q:=MinMult(L-1);
      if q+Mult<k then  k:=q+Mult;
      for i:=L downto j+1 do Dim[i+1]:=Dim[i];
      Dim[j+1]:=D
    end;
    MinMult:=k
  end
end;

begin
  WriteLn(MinMult(n));
end.

Можешь задавать вопросы..

[samec]

Почти такой же пример (только не рекурсивный вариант, в книге сказано, что рекурсивный вариант алгоритма экспоненциально зависит от количества матриц, что не лучше полного перебора...) я нашёл в книге Кормена: Алгоритмы. Построение и анализ.
Вот так я его реализовал на паскале:

program matr;
uses crt;
const KOL_M=50;
type
 matr_typ=array[1..KOL_M,1..KOL_M] of Longint;

var
 p:array[0..KOL_M] of integer;
 kol:integer;
 m,s:matr_typ;

procedure vvod;
var
 i:integer;
begin
 write('Vvedite kol-vo matric: ');
 readln(kol);
 writeln('Vvod razmernostey matric');
 writeln('Vvedite razmernost 1-oy matrici: ');
 write('Vvedite kol-vo strok: ');
 readln(p[0]);
 write('Vvedite kol-vo stolbcov: ');
 readln(p[1]);
 for i:=2 to kol do
  begin
   write('Vvedite kol-vo stolbcov ',i,'-oy matrici: ');
   readln(p[i]);
  end;
end;

procedure Minim;
var
 n,i,j,l,k:integer;
 q:Longint;
begin
 n:=kol;
 for i:=1 to n do
  m[i,i]:=0;
 for l:=2 to n do
  for i:=1 to n-l+1 do
   begin
    j:=i+l-1;
    m[i,j]:=2147483647;
    for k:=i to j-1 do
     begin
      q:=m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j];
      if (q<m[i,j]) then
       begin
        m[i,j]:=q;
        s[i,j]:=k;
       end;
     end;
   end;
 writeln('M');
 for i:=1 to kol do
  begin
   for j:=1 to kol do
    write(m[i,j]:10,' ');
   writeln;
  end;
 writeln('S');
 for i:=1 to kol do
  begin
   for j:=1 to kol do
    write(s[i,j]:3,' ');
   writeln;
  end;
end;

begin
 clrscr;
 vvod;
 Minim;
 readkey;
end.

В матрице m в элементе [1..n], где n - количество матриц, хранится минимальное количество умножений. В матрице s, в элементе s[i,j] - записано место последнего умножения при оптимальной расстановке скобок.
Также в этой книге есть процедура, реализующая произведение матриц с оптимальной расстановкой скобок, вот её псевдокод:

Код

Matrix-Chain-Multiply(A,s,i,j);

1 if j>i
2  then X<-Matrix-Chain-Multiply(A,s,i,s[i,j])
3       Y<-Matrix-Chain-Multiply(A,s,s[i,j]+1,j)
4       return Matrix-Multiply(X,Y)
5 else return Ai

Думаю, что для расстановки скобок переделать нужно именно эту процедуру...но вот как? что то у меня не получается ... помогите, пожалуйста....

Сообщение отредактировано: samec - 2.07.2007 13:07