Помощь - Поиск - Пользователи - Календарь
Полная версия: Количество умножений чисел, при умножении матриц
Форум «Всё о Паскале» > Разработка ПО, алгоритмы, общие вопросы > Алгоритмы
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
Могу дать тебе половину решения..
Вот программа, которая выдает само минимальное количество умножений, но не говорит, как расставить скобки. Попробуй разобраться с ней и добавить расстановку скобок smile.gif.

Начальные данные задаются в константе 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.

Можешь задавать вопросы.. smile.gif
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


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