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

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

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

Несложно подсчитать, что количество операций умножения, которые необходимо выполнить при вычислении произведения будет а при вычислении – т.е. в 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. Это означает, что точка разрыва находится между первой и шестой матрицей послетретьей матрицы, что позволяет расставить внешние скобки следующим образом:

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