90
правок
Изменения
Нет описания правки
'''Задача о порядке перемножения матриц''' — классическая задача динамического программирования, в которой дана последовательность матриц <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</ install [[Wikipediatex>, <tex>A_2:User\, p_1 \times p_2</tex>, …, <tex>A_n:Cacycle\, 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}, 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> оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.===Рекурсивное решение ===Обозначим через <tex>m[i, j]</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>A_{i..j}</wikEdtex>. Получаем следующее рекуррентное соотношение:<tex> m[i,j] = \left \{ \begin{array}{ll} 0, & i=j \\ min(m[i,k]+ m[k+1,j] in+ p_{i-browser text editor1}p_kp_j | i \le k < j) & i < j \end{array} \right.</tex> importScriptURI('httpОбъясняется оно просто:для того, чтобы найти произведение матриц <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}</entex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>A_{i..k}A_{k+1..wikipediaj}</tex>).orgСчитаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>A_i</wtex> равен <tex>p_{i-1} \times p_i</indextex>.php?titleВ данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным из-за большого кол-ва перекрывающихся подзадач.=== Динамическое программирование ===UserБудем запоминать в двумерном массиве <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 :Cacycle1 \le i \le j \le n</tex> и <tex>O(N)</wikEdtex> точек разделения для каждого варианта.js'+ '&action==Ссылки=raw&ctype=textиспользованы материалы ru.wikipedia.org [http://ru.wikipedia.org/javascript');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
