Задача о порядке перемножения матриц — различия между версиями
Tsarevfs (обсуждение | вклад) |
Tsarevfs (обсуждение | вклад) |
||
Строка 20: | Строка 20: | ||
=== Динамическое программирование === | === Динамическое программирование === | ||
Будем запоминать в двумерном массиве <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 <= i <= j <= n</tex> и <tex>O(N)</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 <= i <= j <= n</tex> и <tex>O(N)</tex> точек разделения для каждого варианта. | ||
+ | |||
+ | ==Ссылки== | ||
+ | использованы материалы [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] |
Версия 17:25, 24 декабря 2010
Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц
и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов совпадает с количеством строк матрицы).Содержание
Подробное описание задачи
Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 3 матрицы
размерами соответственно и . Существует 2 способа их перемножения (расстановки скобок): и . В первом случае нам потребуется скалярных умножений, а во втором случае умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб. Таким образом, даны матриц: , , …, . Требуется определить, в каком порядке перемножать их, чтобы количество операций умножения было минимальным.Динамическое решение
Сведение задачи к подзадачам
Обозначим результат перемножения матриц
через , где . Если , то при любом способе расстановки скобок, последнее выполненное умножение для вычисления между матрицами и , i<=k<j, то есть чтобы вычислить надо сначала вычислить , потом и затем их перемножить. Заметим, что если способ расстановки скобок оптимален, то расстановка скобок в этих матрицах должна быть оптимальной, иначе если бы существовал более эффективный способ расстановки скобок в матрицах и , то мы могли бы получить за меньшее число умножений, получаем противоречие, что расстановка скобок в оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.Рекурсивное решение
Обозначим через
минимальное количество скалярных умножений для вычисления матрицы . Получаем следующее рекуррентное соотношение:Объясняется оно просто: для того, чтобы найти произведение матриц
при i=j не нужно ничего делать — это и есть сама матрица . При нетривиальном случае мы перебираем все точки разбиения матрицы на матрицы и , ищем кол-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы .(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц ). Считаем, что размеры матриц заданы в массиве и размер матрицы равен . В данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным из-за большого кол-ва перекрывающихся подзадач.Динамическое программирование
Будем запоминать в двумерном массиве
результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач. После вычислений ответ будет в (Сколько перемножений требуется для последовательности матриц от до — то есть ответ на поставленную задачу).Сложность алгоритма будет , так как у нас вариантов выбора и точек разделения для каждого варианта.Ссылки
использованы материалы [1]