Решение задачи о расстановке скобок при перемножении матриц

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

Заметим, что операция умножения матриц ассоциативна и следовательно,

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

Сформулируем задачу в общем виде.

Рассмотрим произведение матиц …, имеющих размерности соответственно …,

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

Разобьем произведение следующим образом где Индекс будем называть точкой разрыва. Тогда , где – количество операций умножения при перемножении матриц и Другими словами, оптимальная расстановка скобок между матрицами и сводится к поиску точки разрыва при которой количество операций умножения матриц и минимально.

Запишем окончательное рекуррентное соотношение, позволяющее вычислить минимальное количество операций умножения, в следующем виде:

Определим для примера минимальное количество операций умножения для матриц и из рассмотренного выше примера:

На 9 и 10 представлена функция OptimalM, реализующая алгоритм поиска оптимальной расстановки скобок при перемножении нескольких матриц.

Рис. 9. Функция оптимальной расстановки скобок при перемножении матриц

Рис. 10. Реализация функции OptimalM

На рис. 11 приведен пример программы, вызывающей функцию OptimalM для оптимальной расстановки скобок при перемножении шести матриц, а на рис. 12 – результат выполнения этой программы.

Рис. 11. Пример вызова функции OptimalM

Рис. 12. Результат выполнения программы, представленной на рис. 11

Функция OptimalM имеет четыре входных параметра: i (номер первой матрицы), j (номер последней матрицы), n (общее количество перемножаемых матриц), c (массив размерностбю n, содержащий размерности матриц), а также один выходной параметр s (двумерный массив размерностью n, содержащий точки разрыва). Кроме того, к точке вызова возвращается минимальное количество операций умножения, необходимых для перемножения матриц заданной размерности.

Функция OptimalM является рекурсивной, так как она в процессе своей работы вызывает саму себя. Дно рекурсии достигается при совпадении значений двух первых параметров функции.

Расстановку скобок в заданной последовательности матриц можно осуществить с помощью двумерного массива s, возвращаемого функцией в последнем параметре. Поясним принцип использования этого массива для расстановки скобок при перемножении шести матриц размерности которых заданы массивом Mc на рис. 7.11. Массив (матрица) s, который используется далее для расстановки скобок, является результатом работы программы (рис. 11) и выведен на рис. 12.

Скобки расставляются по принципу «сначала внешние – затем внутренние». Найдем элемент в матрице s на рис. 12. Он равен 3. Это означает, что точка разрыва находится между первой и шестой матрицей после третьей матрицы, что позволяет расставить внешние скобки следующим образом:

Точку разрыва между первой и третьей матрицей определяет элемент а между четвертой и шестой – После расстановки скобок выражение будет выглядеть следующим образом Полученная расстановка скобок позволяет получить минимальное количество операций умножения, равное 15 125.