Изменения

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

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

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

Однако, порядок в котором мы расставим скобки в нашем выражении повлияет на === Перебор всех вариантов === В данной задаче нужно узнать минимальное количество простых арифметических операций, которые мы потратим на вычисление ответа, (илиминимальную стоимость), другими словами, на ''эффективность''необходимых для перемножения матриц. НапримерЕсли перемножить только две матрицы, предположимто можно осуществить это едиственным способом, что А = (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 операций* найти минимальную стоимость перемножения на каждой подпоследовательности,* сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц,* сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов.

ОчевидноИли другими словами, что первый способ гораздо эффективнейдавайте обозначим через <tex>f(i, j)</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>M_{i.. Теперь мы понялиj}</tex>, что нам надо найти оптимальную расстановку скобок в нашем выражении из ''n'' матриц. то получаем следующее рекуррентное соотношение:Как это сделать? Мы можем перебрать все расстановки скобок <tex> f(brute forcei,j)= \left \{ \begin{array}{ll} 0, но время выполнение этого алгоритма будет эксапаненциально рости от ''n'' количества матриц. Решение данной проблемы& 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>, чтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант.* Найти Так же, этот алгоритм дает не только минимальную стоимость перемножения на каждой подпоследовательности.* Сложить эти две стоимости , но и прибавить к этому стоимость показывает наилучший способ перемножения двух получившихся матриц.* Сделать это для каждой возможной позиции в последовательности: нужно только сгрупировать тем же образом матрицы, в которой она может быть разделена и взять минимум среди всех результатовкаким дается нам минимальная стоимость.

НапримерОднако, если у нас есть четыре матрицы ''ABCD''применить этот алгоритм, мы посчитаем для (''A'')(''BCD'')то обнаружим, (''AB'')(''CD'')что он работает также медленно, как и (''ABC'')(''D'')наивный способ перебирания всех [[Правильные скобочные последовательности | скобочных последовательностей]]. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, делая рекурсивные вызовыосуществляется рекурсивный вызов, чтобы найти минимальную наилучшую стоимость на ''для подсчета <tex>ABC</tex> и <tex>AB</tex>. Но нахождение наилучшей стоимости для подсчета <tex>ABC''</tex> так же требует нахождения лучшей стоимости для <tex>AB</tex>. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, ''AB''как было сказано выше, ''CD''равняется <tex>n</tex>–ому [[Числа Каталана | числу Каталана]], и да плюс вычисление для каждой [[Правильные скобочные последовательности | правильной скобочной последовательности]] ''BCDзатрат''. Потом среди них мы выбираем лучший вариантна перемножение (то есть <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>== Источники информации ==