36
правок
Изменения
Нет описания правки
'''Задача о порядке перемножения матриц''' — классическая задача динамического программирования, в которой дана последовательность матриц<tex> A_1, A_2, ..., A_n </tex> и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов <tex> A_{i - 1}</tex> совпадает с количеством строк <tex> A_i </tex> матрицы).
== Подробное описание задачи ==
Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 3 матрицы <tex> A_1, A_2, A_3 </tex> размерами соответственно<tex> 10 \times 100, 100 \times 5</tex> и <tex>5 \times 50</tex>. Существует 2 способа их перемножения (расстановки скобок): <tex>((A_1A_2)A_3)</tex> и <tex>(A_1(A_2A_3))</tex>. В первом случае нам потребуется <tex>10\cdot100\cdot5 + 10\cdot5\cdot50 = 7500</tex> скалярных умножений, а во втором случае <tex>100\cdot5\cdot50 + 10\cdot100\cdot50 = 75000</tex> умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб.
Таким образом, даны <tex>n</tex> матриц: <tex>A_1: \, p_0 \times p_1</tex>, <tex>A_2: \, p_1 \times p_2</tex>, …, <tex>A_n: \, p_{n-1} \times p_{n}</tex>. Требуется определить, в каком порядке перемножать их, чтобы количество операций умножения было минимальным.
==Динамическое решение==
===Сведение задачи к подзадачам ===
Обозначим результат перемножения матриц <tex>A_iA_{i+1} \ldots A_j</tex> через <tex>A_{i..j}</tex>, где <tex>i<=\le j</tex>. Если<tex> i<j</tex>, то при любом способе расстановки скобок, последнее выполненное умножение для вычисления <tex>A_{i..j}</tex> между матрицами <tex>A_k</tex> и <tex>A_{k+1}</tex>, i<=\le k<j</tex>, то есть чтобы вычислить <tex>A_{i..j}</tex> надо сначала вычислить <tex>A_{i..k}</tex>, потом <tex>A_{k+1..j}</tex> и затем их перемножить.
Заметим, что если способ расстановки скобок оптимален, то расстановка скобок в этих матрицах должна быть оптимальной, иначе если бы существовал более эффективный способ расстановки скобок в матрицах <tex>A_{i..k}</tex> и <tex>A_{k+1..j}</tex>, то мы могли бы получить <tex>A_{i..j}</tex> за меньшее число умножений, получаем противоречие, что расстановка скобок в <tex>A_{i..j}</tex> оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.
===Рекурсивное решение ===
\begin{array}{ll}
0, & i=j \\
min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i <= \le k < j) & i < j
\end{array}
\right.
Объясняется оно просто: для того, чтобы найти произведение матриц <tex>A_{i..j}</tex> при i=j не нужно ничего делать — это и есть сама матрица <tex>A_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>A_{i..j}</tex> на матрицы <tex>A_{i..k}</tex> и <tex>A_{k+1..j}</tex>, ищем кол-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>A_{i..j}</tex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>A_{i..k}A_{k+1..j}</tex>). Считаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>A_i</tex> равен <tex>p_{i-1} \times p_i</tex>. В данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным из-за большого кол-ва перекрывающихся подзадач.
=== Динамическое программирование ===
Будем запоминать в двумерном массиве <tex>m</tex> результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач. После вычислений ответ будет в <tex>m[1,n]</tex>(Сколько перемножений требуется для последовательности матриц от <tex>1</tex> до <tex>n</tex> — то есть ответ на поставленную задачу).Сложность алгоритма будет <tex>O(n^3)</tex>, так как у нас <tex>{n \choose 2}</tex> вариантов выбора <tex>i, j : 1 <= \le i <= \le j <= \le n</tex> и <tex>O(N)</tex> точек разделения для каждого варианта.
==Ссылки==
использованы материалы ru.wikipedia.org [http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%B5_%D0%BF%D0%B5%D1%80%D0%B5%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86]
== Литература ==
* Томас Х. Кормен и др. Алгоритмы: построение и анализ
* Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms
