Оптимальне множення матриць

Маючи дві матриці A і B, ми можемо обчислити матрицю C = AB за стандартними правилами множення матриць:

Кількість стовпців у матриці A повинна дорівнювати кількості рядків у матриці B. Нехай матриця A має розмір m × n, а матриця B — розмір n × p. Тоді матриця C матиме розмір m × p, і для її обчислення потрібно виконати m * n * p множень.

Наприклад, якщо A має розмір 10 × 20, а B — розмір 20 × 15, то для обчислення матриці C потрібно виконати 10 × 20 × 15 = 3000 множень.

Перемножувати кілька матриць можна різними способами. Наприклад, якщо у нас є матриці X, Y і Z, то обчислити XYZ можна як (XY)Z або X(YZ). Нехай X має розмір 5 × 10, Y — розмір 10 × 20, а Z — розмір 20 × 35.

Порахуємо кількість множень, необхідних для перемноження трьох матриць у кожному з цих двох випадків:

(XY)Z

• 5 × 20 × 10 = 1000 множень для обчислення матриці (XY), що має розмір 5 × 20.

• Потім 5 × 35 × 20 = 3500 множень для отримання кінцевого результату.

• Загальна кількість множень: 4500.

X(YZ)

• 10 × 35 × 20 = 7000 множень для обчислення матриці (YZ), що має розмір 10 × 35.

• Потім 5 × 35 × 10 множень для отримання кінцевого результату.

• Загальна кількість множень: 8750.

Очевидно, що при обчисленні (XY)Z потрібно менше множень.

За заданою послідовністю перемножуваних матриць потрібно знайти оптимальний порядок їх множення. Оптимальним вважається такий порядок, при якому кількість елементарних множень є мінімальною.