Вычисление минимальной сложности алгоритма перемножения матриц

Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А1,...Аn, заданных своими размерами n(i)*m(i). При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.

Замечание:
n(i) - число строк в матрице Ai
m(i) - число столбцов в матрице Ai
n(i)=m(i)+1.

Рассмотрим М = M1 * M2 * … * Mn, где Mi – матрица размера ri-1 * ri.
Как известно, количество элементарных умножений элементов матрицы зависит от порядка умножения матриц.

Составим алгоритм нахождения наименьшего количества элементарных операций умножений матриц с задаными размерами r0, r1, … rn.
Обозначим: mi,j – минимальная сложность вычисления перемножения матриц, причем 1 ≤ I ≤ j ≤ n.
Тогда возможны два случая сложности вычисления:
1. При i = j, mi,j = 0
2. При j ≥ 1, MINIMUM (mi,k mk+1,j + ri-1 * rk * rj)

// матрица размера n*m умножается на матрицу размера m*k
 
#include <conio.h>
#include <stdlib.h>
#define MIN (x,y) ((x<y) ? x : y) // макрос для нахождения минимума из двух чисел
 
int main()
{
 
// заполнения матриц случайными числами
randomize();
 
for (i = 0; i <= n; i++)
{
   for (j = 0; j <= m; j++)
   {
      random (m[i][j]);
   }
}
 
for (i = 0; i <= m; i++)
{
   for (j = 0; j <= k; j++)
   {
      random (r[i][j]);
   }
}
 
// вывод матриц на экран
for (i = 0; i <= n; i++)
{
   for (j = 0; j <= m; j++)
   {
      printf ("%d ", m[i][j]);
   }
   printf ("\n");
}
 
for (i = 0; i <= m; i++)
{
   for (j = 0; j <= k; j++)
   {
      printf ("%d ", r[i][j]);
   }
   printf ("\n");
}
 
 
int i(0), l(0);	// вспомогательная переменные
 
for (i = 1; i <= n; i++)   m[i][i] = 0; // обнуляем элементы по диагонали
 
for (l = 1; l <= n-1; l++)
{
   for (i =1; i <= n-l; i++)
   {
      j = i + l; // вычисляем j-й индекс
      m[i][j] = MIN (m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j]); //перемножение
   }
}
 
for (i = 0; i <= n; i++)
{
   for (j = 0; j <= m; j++)
   {
      printf ("%d ", m[i][j]);
   }
   printf ("\n");
}
 
return 0;
}

Ключевые слова: 
перемножения матриц, сложность алгоритма
ВложениеРазмер
Matrix.zip6.49 кб