Изменения

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

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

=== Постановка Решение задачи ===У нас есть множество способов перемножить, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке мы расставим скобки между множителями, результат будет один и тот же. Например, если у нас есть четыре матрицы ''A'', ''B'', ''C'' и ''D'', то существуют следующие варианты::(''ABC'')''D'' = (''AB'')(''CD'') = ''A''(''BCD'') = ''A''(''BC'')''D'' = ....

Однако, порядок в котором мы расставим скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''. Например, предположим, что А = (10 &times; 30), B = (30 &times; 5), C = (5 &times; 60). Тогда:Перебор всех вариантов ===

:В данной задаче нужно узнать минимальное количество операций (''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'' количества матриц. Решение данной задачи, как мы увидим — это разбить нашу задачу на подзадачи. Так же мы увидимдля каждой возможной позиции в последовательности, что с помощю решения однократного решения подзадачи в которой она может быть разделена и повторного использования ответа, мы сможем заметно сократить асимптотикувзять минимум среди всех результатов.

Или другими словами, давайте обозначим через <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>, чтобы найти минимальную стоимость. Потом среди них мы выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость.

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

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

Одно из простых решений '''int''' dp[][] <font color="green">// dp[i][j] — это меморизация. Каждый раз, когда мы считаем минимальную стоимость перемножения определенной подпоследовательности, давайте мы будем запоминать ответ. Если мы когда либо ещё раз захотим посчитать это ещё разна отрезке [i, то мы уже будет иметь ответ и не будем пересчитывать. Поскольку существует всего около <math>n^2/2j)</mathfont>, где '''int'n'' v[] <font color="green">// Массив v[] — это количество хранит все размеры матриц по порядку // Так как у нас размеры соседних матрицпо вертикали и горизонтали совпадают, то память занимаемая программой будет не так великаони занесены в этот массив однократно // l — включая в отрезок, r — исключая из отрезка. Можно сказатьИзначально l = 0, что с помощью этого простого трюка мы уменьшили асимптотику алгоритма с Or = n, где n {{---}} длина последовательности</font> '''int''' matrixChainMultiplication('''int''' l, '''int''' r) '''if''' dp[l][r] == -1 <mathfont color="green">2n// Если значение динамики не посчитано</mathfont>) до O( '''if''' l == r - 1 dp[l][r] = 0 <font color="green"> // Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю</font> '''else''' dp[l][r] = <mathtex>n^3\infty</mathtex> '''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]

int dp*[1000][1000Задача о наибольшей общей подпоследовательности ];vector<pair<int, int> > v;// v[i].first — размер i-той матрицы по горизонтали // v*[i].second — размер i-той матрицы по вертикали// dp[iКратчайший путь в ациклическом графе ][j] — меморизация на отрезке [i, j)int matrixChainMultiplication(int l, int r){ //l — включая в отрезок //r — исключая из отрезка if dp*[l][r] == -1 if l == r - 1 dp[lЗадача о расстановке знаков в выражении][r] = 0; else dp[l][r] = 1000 * 1000 * 1000; for (int i = l + 1; i < r; i++) dp[l][r] = min(dp[l][r]Задача о выводе в контекстно-свободной грамматике, v[lалгоритм Кока-Янгера-Касами | Aлгоритм Кока-Янгера-Касами ].first * v[i].first * v[r - 1].second + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r)); return dp[lПравильные скобочные последовательности | Правильные скобочные последовательности ][r];}</pre>== Источники информации ==