Перемножение нескольких матриц

Содержание

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

1. Перемножение нескольких матриц…………………………………….…..5

2. Когда применимо динамическое программирование……………………12

3. Наибольшая общая подпоследовательность…………………………..…17

4. Оптимальная триангуляция многоугольника……………………….........21

Замечания………………………………………………………………..25

Заключение………………………………………………………………27

Приложение……………………………………………………………...28

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

Подобно методу «разделяй и властвуй», динамическое программирование решает задачу, разбивая её на подзадачи и объединяя их решения.Как мы видели в главе 1, алгоритмы типа «разделяй и властвуй» делят задачу на независимые подзадачи, эти подзадачи—на более мелкие подзадачи и так далее, а затем собирают решение основной задачи «снизу вверх». Динамическое программирование применимо тогда, когда подзадачи не являются независимыми, иными словами, когда у подзадач есть общие «подподзадачи». В этом случае алгоритм типа «разделяй и властвуй» будет делать лишнюю работу, решая одни и те же подподзадачи по нескольку раз. Алгоритм, основанный на динамическом программировании, решает каждую из подзадач единожды и запоминает ответы в специальной таблице. Это позволяет не вычислять заново ответ к уже встречавшейся подзадаче.

В типичном случае динамическое программирование применяется к задаче оптимизации (optimization problems). У такой задачи может быть много возможных решений; их «качество» определяется значением какого-то параметра и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи) Вообще говоря, оптимум может достигаться для нескольких разных решений

Как строится алгоритм, основанный на динамическом программировании. Надо:

1) описать строение оптимальных решений,

2) выписать рекуррентное соотношение, связывающее оптимальные значение параметра для подзадач,

3) двигаясь снизу вверх, вычислить оптимальное значение параметра для подзадач,

4) пользуясь полученной информацией, построить оптимальное решение.

Основную часть работы составляют шаги 1-3. Если нас интересует только оптимальное значение параметра, шаг 4 не нужен. Если же шаг 4 необходим, для построения оптимального решения иногда приходится получать и хранить:

дополнительную информацию в процессе выполнения шага 3.

В этой главе мы решим несколько оптимизационных задач с помощью динамического программирования. В разделе 16.1 мы выясним, как найти произведение нескольких матриц, сделав как можно меньше умножений. В разделе 2 мы обсудим, какие свойства задачи делают возможным применение динамического программирования. После этого мы расскажем (в разделе 3), как найти наибольшую общую подпоследовательность двух последовательностей. Наконец, в разделе 4 мы воспользуемся динамическим программированием для нахождения оптимальной триангуляции выпуклого многоугольника. (Удивительным образом эта задача оказывается похожей на задачу о перемножении нескольких матриц.)

Перемножение нескольких матриц

Мы хотим найти произведение

A₁A₂....A_n (1)

последовательности п матриц (A₁A₂....A_n). Мы будем пользоваться стандартным алгоритмом перемножения двух матриц в качестве подпрограммы. Но прежде надо расставить скобки в (16.1), чтобы указать порядок умножений. Будем говорить, что в произведении матриц полностью расставлены скобки (product is fully parenthesized), если это произведение либо состоит из одной-единственной матрицы, либо является заключенным в скобки произведением двух произведений с полностью расставленными скобками. Поскольку умножение матриц ассоциативно, конечный результат вычислений не зависит от расстановки скобок. Например, в произведении A₁A₂A₃A₄ можно полностью расставить скобки пятью разными способами:

(A₁(A₂(A₃A₄))), (A₁((A₂A₃)A₄)), ((A₁A₂)(A₃A₄)), ((A₁(A₂A₃))A₄), (((A₁A₂)A₃)A₄);

во всех случаях ответ будет один и тот же.

Не влияя на ответ, способ расстановки скобок может сильно повлиять на стоимость перемножения матриц. Посмотрим сначала, сколько операций требует перемножение двух матриц. Вот стандартный алгоритм (rows и columns обозначают количество строк и столбцов матрицы соответственно):

int p,q,w,r;

double Matrix_Multiply(float a[p][q], b[w][r], c[p][r]);

{ if (q!=w) { cout <<"умножение невозможно"}

else { for (i=1;i<=p;i++)

{ for (j=1;j<=r;j++)

{c[i][j]=0}

for (k=1;k<=q;k++)

{c[i][j]=c[i][j]+a[i][k]*b[k][j]}}

return c}

Матрицы А и В можно перемножать, только если число столбцов у A равно числу строк у В. Если А— это (р* q) матрица, а В —это (q* r)-матрица, то их произведение С является (р*r)- матрицей. При выполнении этого алгоритма делается pqr умножений (строка 7) и примерно столько же сложений. Для простоты мы будем учитывать только умножения.

Чтобы увидеть, как расстановка скобок может влиять на стоимость, рассмотрим последовательность из трех матриц (A₁A₂A₃).размеров 10 х 5 100 х 5 и 5 х 50 соответственно. При вычислении ((A₁A₂)A₃).нужно 10x100x5 — 5000 умножений, чтобы найти (10 х 5)-матрицу А₁А₂, а затем 10x 5x50=2500 умножений, чтобы умножить эту матрицу на A₃. Всего 7500 умножений при расстановке скобок (A₁₍A₂A₃)) мы делаем 100 х 5 х 50 = 25000 умножений для нахождения (100 х 50)-матрицы A₂A₃ плюс ещё 10 х 100 х 50 - 50000 умножений (умножение А₁ на A₂A₃), итого 75 000 умножений. Тем самым, способ расстановки скобок в 10 раз выгоднее.

Задача об умножении последовательности матриц (matrix-chain multipltion problem) может быть сформулирована следующим образом: дана последовательность из п матриц (A₁,A₂,..., A_n) заданных размеров (матрица А_i, имеет размер p_i-1 x p_i); требуется найти такую (полную) расстановку скобок в произведении А₁А₂...A_n, чтобы вычисление произведения требовало наименьшего числа умножений.

Дата добавления: 2015-12-08