Лекция: Программа 7.

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

// размеры которых r0, r1, …, rn заданы в массиве 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 = M1 ´ M2 ´ M3´ M4 ´ M5 ´ M6,

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

соответствующие размеры которых указаны под матрицами. Здесь величины r0, r1,r2, r3,r4, r5,r6 соответственно равны 15, 7, 8, 46, 2, 39, 38. В результате работы алгоритма 7 получается матрица минимальных сложностей умножения, показанная в таблице 4. Из матрицы видно, что минимальная сложность умножения данных шести матриц равна 5162. Из этой же таблицы несложно получить и порядок умножения матриц. Для этого надо приписать к каждой клетке таблицы то значение k, на котором достигается минимум (1.11). Для удобства полученные значения k показаны в маленьких левых нижних клетках, а в верхних маленьких клетках показаны индексы i и j из (1.11).

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

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

Цифры в левом верхнем углу i=1, j=6 показывают, что данная клетка показывает минимальную сложность умножения матриц с первой по шестую. Эта сложность равна 5162. Цифра k=4 показывает оптимальную расстановку скобок, а именно — нужно умножить сначала матрицы (M1´M2´…´M4), далее матрицы (M5´M6), после чего найти произведение полученных сомножителей. Чтобы найти оптимальный способ умножения (M1´M2´…´M4) необходимо найти в таблице ячейку с параметрами i=1, j=4. Число k=1 в этой ячейке указывает на то, что сначала необходимо найти произведение матриц (M2´M3´M4), а далее умножить его на M1. И так далее. В результате получается следующий способ оптимального умножения матриц с точки зрения сложности вычислений (и далеко не очевидный при самостоятельном поиске варианта расстановки скобок):

Mопт = (M1 ´ (M2 ´ (M3´ M4))) ´ (M5 ´ M6).

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

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

M = M1 ´ M2 ´ M3´ M4 ´ M5 ´ M6,

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