Программа 7

// Программа рассчитывает матрицу минимальных сложностей умножения NUM матриц,

// размеры которых r₀, r₁, …, r_n заданы в массиве Sizes

# include <stdlib.h>

# include <stdio.h>

# include <io.h>

# define NUM 6 // Число перемножаемых матриц

# define NUM1 NUM+1 // Размер массива Sizes

unsigned Sizes[NUM1]; // Массив, содержащий размеры перемножаемых матриц

unsigned long Time_comp[(NUM1*NUM)>>1]; // Матрица минимальных сложностей умножения

void main ()

{

unsigned long value, temp, *ptr, *current[NUM<<1];

unsigned ind, index, count, curr, max, min;

// Здесь должна стоять функция ввода массива Sizes

// Процедура заполнения матрицы Time_copm с помощью метода

// динамического программирования

ptr=Time_comp;

for (index=0; index<NUM; *ptr++=0, index++); // Первая строка заполняется нулями

for (ind=1; ind<NUM; ind++)

{

max=(ind<<1)-1;

// Предварительный расчёт указателей на элементы матрицы Time_copm, которые

// используются в дальнейшем при выборе минимальной сложности умножения.

// Указатели хранятся в массиве current.

for (index=0; index<ind; index++)

{

count=(index*((NUM<<1)-index+1))>>1;

curr=count+ind-index;

current[index<<1]=&Time_comp[count];

current[(index<<1)+1]=&Time_comp[curr];

}

for (index=1; index<NUM; index++)

{

count=ind+index;

if (count>NUM) break;

// Выбор минимальной сложности умножения заданного количества матриц

value=4294967294; // максимальное число типа long int

for (curr=index; curr<count; curr++)

{

min=(curr-index)<<1;

temp=*current[min]++ + *current[max-min]++ + Sizes[index-1]*Sizes[curr]*Sizes[count];

if (value > temp) value=temp;

}

*ptr++=value; // Заполнение текущего элемента матрицы Time_comp

}

}

} // Конец main

Рассмотрим характерный пример умножения некоторого количества матриц.

Пример 1.8. Предположим, что требуется найти произведение шести матриц

M = M ₁ ´ M ₂ ´ M ₃´ M ₄ ´ M ₅ ´ M ₆,

(15´7) (7´8) (8´46) (46´2) (2´39) (39´38)

соответствующие размеры которых указаны под матрицами. Здесь величины r ₀, r ₁, r ₂, r ₃, r ₄, r ₅, r ₆ соответственно равны 15, 7, 8, 46, 2, 39, 38. В результате работы алгоритма 7 получается матрица минимальных сложностей умножения, показанная в таблице 4. Из матрицы видно, что минимальная сложность умножения данных шести матриц равна 5162. Из этой же таблицы несложно получить и порядок умножения матриц. Для этого надо приписать к каждой клетке таблицы то значение k, на котором достигается минимум (1.11). Для удобства полученные значения k показаны в маленьких левых нижних клетках, а в верхних маленьких клетках показаны индексы i и j из (1.11).

Таблица 4. Сложности вычисления произведений M _i ´ M _i+1 ´…´ M _j

	0		0		0		0		0		0
	840		2576		736		3588		2964
	6360		848		1360		6224
	1058		1394		4308
	2228		4344
	5162

Теперь рассмотрим последнюю клетку таблицы

	5162

Цифры в левом верхнем углу i=1, j=6 показывают, что данная клетка показывает минимальную сложность умножения матриц с первой по шестую. Эта сложность равна 5162. Цифра k=4 показывает оптимальную расстановку скобок, а именно - нужно умножить сначала матрицы (M ₁´ M ₂´…´ M ₄), далее матрицы (M ₅´ M ₆), после чего найти произведение полученных сомножителей. Чтобы найти оптимальный способ умножения (M ₁´ M ₂´…´ M ₄) необходимо найти в таблице ячейку с параметрами i=1, j=4. Число k=1 в этой ячейке указывает на то, что сначала необходимо найти произведение матриц (M ₂´ M ₃´ M ₄), а далее умножить его на M ₁. И так далее. В результате получается следующий способ оптимального умножения матриц с точки зрения сложности вычислений (и далеко не очевидный при самостоятельном поиске варианта расстановки скобок):

M_опт = (M ₁ ´ (M ₂ ´ (M ₃´ M ₄))) ´ (M ₅ ´ M ₆).

(15´7) (7´8) (8´46) (46´2) (2´39) (39´38)

Если теперь сравнить полученный результат с вариантом, когда матрицы умножаются без расстановки скобок последовательно в порядке записи

M = M ₁ ´ M ₂ ´ M ₃´ M ₄ ´ M ₅ ´ M ₆,

то получится сложность умножения, равная 31140. С другой стороны, если попробовать найти полученное оптимальное расположение скобок простым перебором всех возможных вариантов, то получится задача сложности зачастую превышающей сложность самой задачи умножения матриц.