Задача о порядке перемножения матриц — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
Строка 1: Строка 1:
'''Задача о порядке перемножения матриц''' — классическая задача динамического программирования, в которой дана последовательность матриц<tex> A_1, A_2, ..., A_n </tex> и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов <tex> A_{i - 1}</tex> совпадает с количеством строк <tex> A_i </tex> матрицы).
+
'''Задача о порядке перемножения матриц''' — классическая задача динамического программирования, в которой дана последовательность матриц <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> умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб.
+
Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 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>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<=j</tex>. Если<tex> i<j</tex>, то при любом способе расстановки скобок, последнее выполненное умножение для вычисления <tex>A_{i..j}</tex> между матрицами <tex>A_k</tex> и <tex>A_{k+1}</tex>, i<=k<j, то есть чтобы вычислить <tex>A_{i..j}</tex> надо сначала вычислить <tex>A_{i..k}</tex>, потом <tex>A_{k+1..j}</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>A_{i..k}</tex> и <tex>A_{k+1..j}</tex>, то мы могли бы получить <tex>A_{i..j}</tex> за меньшее число умножений, получаем противоречие, что расстановка скобок в <tex>A_{i..j}</tex> оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.
 
===Рекурсивное решение ===
 
===Рекурсивное решение ===
Строка 12: Строка 12:
 
\begin{array}{ll}
 
\begin{array}{ll}
 
  0, & i=j \\
 
  0, & i=j \\
  min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i <= k < j) & i < j  
+
  min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i \le k < j) & i < j  
 
  \end{array}
 
  \end{array}
 
  \right.
 
  \right.
Строка 19: Строка 19:
 
Объясняется оно просто: для того, чтобы найти произведение матриц <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>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 <= 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 \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]
 
использованы материалы 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

Версия 17:50, 24 декабря 2010

Задача о порядке перемножения матриц — классическая задача динамического программирования, в которой дана последовательность матриц [math] A_1, A_2, ..., A_n [/math] и требуется минимизировать количество скалярных операций для вычисления их произведения. Матрицы предполагаются совместимыми по отношению к матричному умножению (то есть количество столбцов [math] A_{i - 1}[/math] совпадает с количеством строк [math] A_i [/math] матрицы).

Подробное описание задачи

Произведение матриц — ассоциативная операция. Когда матрицы велики по одному измерению и малы по другому, количество скалярных операций может серьёзно зависеть от порядка перемножений матриц. Допустим, нам даны 3 матрицы [math] A_1, A_2, A_3 [/math] размерами соответственно [math] 10 \times 100, 100 \times 5[/math] и [math]5 \times 50[/math]. Существует 2 способа их перемножения (расстановки скобок): [math]((A_1A_2)A_3)[/math] и [math](A_1(A_2A_3))[/math]. В первом случае нам потребуется [math]10\cdot100\cdot5 + 10\cdot5\cdot50 = 7500[/math] скалярных умножений, а во втором случае [math]100\cdot5\cdot50 + 10\cdot100\cdot50 = 75000[/math] умножений — разница налицо. Поэтому может оказаться выгоднее потратить некоторое время на предобработку, решив, в каком порядке лучше всего умножать, чем умножать сразу в лоб. Таким образом, даны [math]n[/math] матриц: [math]A_1: \, p_0 \times p_1[/math], [math]A_2: \, p_1 \times p_2[/math], …, [math]A_n: \, p_{n-1} \times p_{n}[/math]. Требуется определить, в каком порядке перемножать их, чтобы количество операций умножения было минимальным.

Динамическое решение

Сведение задачи к подзадачам

Обозначим результат перемножения матриц [math]A_iA_{i+1} \ldots A_j[/math] через [math]A_{i..j}[/math], где [math]i \le j[/math]. Если [math] i\lt j[/math], то при любом способе расстановки скобок, последнее выполненное умножение для вычисления [math]A_{i..j}[/math] между матрицами [math]A_k[/math] и [math]A_{k+1}, i \le k\lt j[/math], то есть чтобы вычислить [math]A_{i..j}[/math] надо сначала вычислить [math]A_{i..k}[/math], потом [math]A_{k+1..j}[/math] и затем их перемножить. Заметим, что если способ расстановки скобок оптимален, то расстановка скобок в этих матрицах должна быть оптимальной, иначе если бы существовал более эффективный способ расстановки скобок в матрицах [math]A_{i..k}[/math] и [math]A_{k+1..j}[/math], то мы могли бы получить [math]A_{i..j}[/math] за меньшее число умножений, получаем противоречие, что расстановка скобок в [math]A_{i..j}[/math] оптимальна. Таким образом мы свели задачу к подзадачам. Это означает, что возможно решить задачу, используя динамическое программирование на подотрезке.

Рекурсивное решение

Обозначим через [math]m[i, j][/math] минимальное количество скалярных умножений для вычисления матрицы [math]A_{i..j}[/math]. Получаем следующее рекуррентное соотношение: [math] m[i,j] = \left \{ \begin{array}{ll} 0, & i=j \\ min(m[i,k] + m[k+1,j] + p_{i-1}p_kp_j | i \le k \lt j) & i \lt j \end{array} \right. [/math]

Объясняется оно просто: для того, чтобы найти произведение матриц [math]A_{i..j}[/math] при i=j не нужно ничего делать — это и есть сама матрица [math]A_i[/math]. При нетривиальном случае мы перебираем все точки разбиения матрицы [math]A_{i..j}[/math] на матрицы [math]A_{i..k}[/math] и [math]A_{k+1..j}[/math], ищем кол-во операций, необходимое чтобы их получить и затем перемножаем для получения матрицы [math]A_{i..j}[/math].(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц [math]A_{i..k}A_{k+1..j}[/math]). Считаем, что размеры матриц заданы в массиве [math]p[/math] и размер матрицы [math]A_i[/math] равен [math]p_{i-1} \times p_i[/math]. В данном случае рекурсивный метод нельзя использовать напрямую — он будет экспоненциальным из-за большого кол-ва перекрывающихся подзадач.

Динамическое программирование

Будем запоминать в двумерном массиве [math]m[/math] результаты вычислений для подзадач, чтобы избежать пересчета для уже вычислявшихся подзадач. После вычислений ответ будет в [math]m[1,n][/math](Сколько перемножений требуется для последовательности матриц от [math]1[/math] до [math]n[/math] — то есть ответ на поставленную задачу).Сложность алгоритма будет [math]O(n^3)[/math], так как у нас [math]{n \choose 2}[/math] вариантов выбора [math]i, j : 1 \le i \le j \le n[/math] и [math]O(N)[/math] точек разделения для каждого варианта.

Ссылки

использованы материалы ru.wikipedia.org [1]

Литература

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ
  • Sanjoy Dasgupta , Christos H. Papadimitriou, Umesh Vazirani Algorithms