Изменения

{{Задача|definition = Дана последовательность из <tex>n<//Не окончательный вариант --[[Участник:GosuGDR|GosuGDR]] 07:02tex> матриц, 10 декабря 2011 (MSK)требуется найти самый эффективный способ их перемножения.}}

'''Задача о порядке У нас есть множество способов перемножить матрицы, потому что операция перемножения матриц''' — классическая задача, которая может быть решена с помощью динамического программированияассоциативна. Нам дается последовательность матрицДругими словами, нет разницы в которой мы хотим найти самый эффективный способ их перемножения. На самом деле задача заключается не в нахождении результата перемножениякаком порядке расставляются скобки между множителями, а в нахождении нужного порядка этого перемножениярезультат будет один и тот же.

У нас есть множество способов перемножить, потому что операция перемножения ассоциативна[[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно <tex>n</tex>–ому [[Числа Каталана | числу Каталана]]. Другими словамиОднако, нет разницы порядок в каком порядке мы расставим котором расставляются скобки между множителямиматрицами повлияет на количество арифметических операций, результат будет один и тот же. Напримеркоторые потребуются на вычисление ответа, или, если у нас есть четыре матрицы ''A''другими словами, на ''Bэффективность''. Например, ''C'' и ''D''предположим, то существуют следующие варианты::(''ABC'')''D'' что <tex>\dim{A}= (''AB'')(''CD'') 10 \times 30</tex>, <tex>\dim{B} = ''A''(''BCD'') = ''A''(''BC'')''D'' 30 \times 5</tex>, <tex>\dim{C} = 5 \times 60</tex>....Тогда:

Однако, порядок в котором мы расставим скобки между матрицами повлияет на количество арифметических : Для <tex> (A \times B)\times C</tex> будет <tex>(10\times30\times5) + (10\times5\times60) = 1500 + 3000 = 4500</tex> операций, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''. Например, предположим, что А = : Для <tex> A \times(10 &B \times; 30C), B = </tex> будет <tex>(30 &times; 5\times5\times60), C = + (5 &times; 6010\times30\times60)= 9000 + 18000 = 27000</tex> операций. Тогда:

:(''AB'')''C'' = (10&times;30&times;5) + (10&times;5&times;60) = 1500 + 3000 = 4500 операций:''A''(''BC'') = (30&times;5&times;60) + (10&times;30&times;60) = 9000 + 18000 = 27000 операцийКак мы видим, первый способ гораздо эффективней.

Как мы видим, первый способ гораздо эффективней. Теперь стало понятно, что нам надо найти оптимальную расстановку скобок в нашем выражении из ''n'' матриц. Как бы это сделать? Мы можем перебрать все расстановки скобок (brute force), но время выполнения этого алгоритма будет расти экспоненциально от ''n'' количества матриц. == Решение данной задачи, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидим, что с помощю решения однократного решения подзадачи и повторного использования ответа, мы сможем заметно сократить асимптотику.==

=== Перебор * взять последовательность матриц и разделить её на две части,* найти минимальную стоимость перемножения на каждой подпоследовательности,* сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц,* сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех вариантов (Bruteforce) ===результатов.

СначалаИли другими словами, давайте определимсяобозначим через <tex>f(i, что мы хотим узнать j)</tex> минимальное количество операций скалярных умножений для вычисления матрицы <tex>M_{i..j}</tex>, то получаем следующее рекуррентное соотношение:<tex> f(или минимальную стоимостьi,j)= \left \{ \begin{array}{ll} 0, необходимых для перемножения матриц. Если мы перемножаем только две матрицы& i=j \\ \min\limits_{i \leqslant k < j}{(f(i, то мы можем осуществить это едиственным способомk) + f(k+1, следовательно минимальная стоимость — это стоимость перемножения этих двух матрицj) + p_{i-1}p_kp_j)} & i < j \end{array} \right. В общем, мы можем найти минимальную стоимость используя следующий рекурсивный алгоритм:</tex>

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

ОднакоЧтобы привести пример, если мы применим этот алгоритмдавайте вернемся к нашим матрицам. Если у нас есть четыре матрицы <tex>ABCD</tex>, то мы обнаружимпосчитаем для <tex>(A)(BCD)</tex>, что он работает также медленно<tex>(AB)(CD)</tex>, как и наивный способ перебирания всех скобочных последовательностей! Что пошло не так? Ответом <tex>(ABC)(D)</tex>, делая рекурсивные вызовы на этот вопрос является то фактотрезках <tex>ABC</tex>, что мы делаем значительное количество ненужной работы. Например<tex>AB</tex>, в выше описанном алгоритме<tex>CD</tex>, мы делали рекурсивный вызови <tex>BCD</tex>, чтобы найти наилучшую минимальную стоимость для подсчета ''ABC'' и ''AB''. Но нахождение наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''Потом среди них выбираем лучший вариант. Так как рекурсия растет вглубь все больше же, этот алгоритм дает не только минимальную стоимость, но и большепоказывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, то и число ненужных повторений увеличиваетсякаким дается нам минимальная стоимость.

=== Оптимизации динамическим программированием ===Одно из простых решений — это ''мемоизация''Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех [[Правильные скобочные последовательности | скобочных последовательностей]]. Делается значительное количество ненужной работы. Каждый разНапример, когда мы считаем минимальную в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость перемножения определенной подпоследовательности, давайте мы будем запоминать ответдля подсчета <tex>ABC</tex> и <tex>AB</tex>. Но нахождение наилучшей стоимости для подсчета <tex>ABC</tex> так же требует нахождения лучшей стоимости для <tex>AB</tex>. Если мы когда либо ещё раз захотим посчитать это ещё разТак как рекурсия растет вглубь все больше и больше, то мы уже будет иметь ответ и не будем пересчитыватьчисло ненужных повторений увеличивается. Поскольку существует всего около Итоговая асимптотика, как было сказано выше, равняется <mathtex>n^2/2</mathtex> подотрезков–ому [[Числа Каталана | числу Каталана]], где да плюс вычисление для каждой [[Правильные скобочные последовательности | правильной скобочной последовательности]] ''nзатрат'' — это количество матриц, на перемножение (то память занимаемая программой будет не так велика. Можно сказать, что с помощью этого простого трюка мы уменьшили асимптотику алгоритма есть <tex>O(переборn \cdot C_n)</tex>) с O(. Так как <mathtex>N</tex>­-ое [[Числа Каталана | число Каталана]] равняется <tex dpi="163"> \frac{1}{n+1}{2^n\choose n} </mathtex>) до O(или асимптотически <mathtex dpi="163">\frac{4^n}{n^{3/2}\sqrt{\pi}} </mathtex>), что является достаточно эффективным для реальных приложенийа это быстро возрастающая функциия, нам бы хотелось решение, которое работает быстрее.

'''int''' dp[][] <font color="green">// dp[i][j] — ответ на отрезке [i, j)</font> '''int''' v[] <font color= Литература "green">// Массив v[] — хранит все размеры матриц по порядку // Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно // l — включая в отрезок, r — исключая из отрезка. Изначально l =0, r =n, где n {{---}} длина последовательности</font> '''int''' matrixChainMultiplication('''int''' l, '''int''' r) '''if''' dp[l][r] == -1 <font color="green">// Если значение динамики не посчитано</font> '''if''' l == r - 1 dp[l][r] = 0 <font color="green"> // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font> '''else''' dp[l][r] = <tex>\infty</tex> '''for''' i = l + 1 '''to''' r - 1 dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)) '''return''' dp[l][r] == См. также == *[[Задача о наибольшей общей подпоследовательности ]]*[[Кратчайший путь в ациклическом графе ]]*[[Задача о расстановке знаков в выражении]]*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ]]*[[Правильные скобочные последовательности | Правильные скобочные последовательности ]]== Источники информации == *[http://en.wikipedia.org/wiki/Matrix_chain_multiplication Wikipedia {{---}} Matrix chain multiplication]