WikiSort.ru - Программирование

Перебор всех вариантов расстановки скобок

Оценим, сколько же нужно перебрать вариантов расстановки. Обозначим через ${\displaystyle P(n)}$ количество способов расстановки скобок в последовательности, состоящей из n матриц. Когда матрица одна, то расставлять нечего, вариант один. Если ${\displaystyle n\geq 2}$ , то количество вариантов, которым можно расставить скобки является произведением количества вариантов, которым можно расставить скобки в составляющих результирующую матрицу произведениях (т.е. если ${\displaystyle A_{3}=A_{1}*A_{2}}$ , то количество вариантов, которым мы можем получить матрицу ${\displaystyle A_{3}}$ равно произведению количества способов получить матрицу ${\displaystyle A_{1}}$ на количество способов получить ${\displaystyle A_{2}}$ ). Разбиение на матрицы, ${\displaystyle A_{1}}$ и ${\displaystyle A_{2}}$ может производиться на границе k-й и (k + 1)-й матриц для ${\displaystyle k=1,2,\dots ,n-1}$ . Получаем рекуррентное соотношение: ${\displaystyle P(n)=\left\{{\begin{array}{ll}1,\ n=1\\\sum _{k=1}^{n-1}P(k)P(n-k),\ n>=2\end{array}}\right.}$

Решением аналогичного рекуррентного соотношения является последовательность чисел Каталана, возрастающая как ${\displaystyle \Omega \left({\frac {4^{n}}{n^{1.5}}}\right)}$ . Зависимость получается экспоненциальная, непригодная для практического применения в программах. Разберём более перспективный способ.

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

Обозначим результат перемножения матриц ${\displaystyle A_{i}A_{(i+1)}...A_{j}}$ через ${\displaystyle A_{i..j}}$ , где i<=j. Если i<j, то существует такое k, которое разбивает ${\displaystyle A_{i..j}}$ между матрицами ${\displaystyle A_{k}}$ и ${\displaystyle A_{k+1}}$ , i<=k<j. То есть для вычисления ${\displaystyle A_{i..j}}$ надо сначала вычислить ${\displaystyle A_{i..k}}$ , потом ${\displaystyle A_{k+1..j}}$ и затем их перемножить. Выбор k является аналогом расстановки скобок между матрицами. Выбрав некоторое k мы свели задачу к двум аналогичным подзадачам для матриц ${\displaystyle A_{i..k}}$ и ${\displaystyle A_{k+1..j}}$ .

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

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

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

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

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