Шаг 2: рекуррентное соотношение

Выразим стоимость оптимального решения задачи через стоимости оптимальных решений её подзадач. Обозначим через m[i][j] минимальное количество умножений, необходимое для вычисления матрицы А_i…j, в частности, стоимость вычисления всего произведения А_1…n есть m[1][n].

Числа m[i][j] можно вычислить так. Если i=j, то последовательность состоит из одной матрицы и умножения вообще не нужны. Если i<j, воспользуемся информацией полученной на шаге 1. Стоимость оптимальной расстановки равна стоимости вычисления матрицы А_i…k (это m[i][k]) плюс стоимость вычисления матрицы А_k+1…j (это m[k+1][j]) плюс стоимость перемножения этих двух матриц (это p_i-1p_kp_j). И нам ещё нужно найти такое k, при котором вся эта сумма будет минимальной. Получаем рекуррентную формулу

Обозначим через s[i][j] оптимальное значение k для последовательности А_i…j, т.е. то k при котором значение суммы будет минимальным.

Шаг 3: вычисление оптимальной стоимости

Теперь легко написать рекурсивный алгоритм, определяющий минимальную стоимость вычисления произведения матриц (т.е. число m[1][n]). Однако, время работы такого алгоритма экспоненциально зависит от n, так что этот алгоритм ничуть не лучше полного перебора. Настоящий выигрыш по времени мы получим, если воспользуемся тем, что подзадач относительно немного: по одной задаче для каждой пары (i,j), для которой 1  i  j  n, а всего . Экспоненциальное время возникает потому, что рекурсивный алгоритм решает каждую из подзадач помногу раз, на разных ветвях дерева рекурсии.

Такое «перекрытие задач» – характерный признак задач, решаемых методом динамического программирования.

Вместо рекурсии мы вычислим оптимальную стоимость «снизу вверх».

Void MatrixChainOrder(int n, // кол-во матриц

long **m, // вспом. таблица для

// хранения стоимостей

Int p[], // размеры матриц

Int **s) // оптимальное k

{

int i, j, k, u;

long q;

for( i=1; i<=n; i++)

m[i][i]=0; // стоимость перемножения одной матрицы

// равна 0

for(u=2; u<=n; u++)

{

for(i=1; i<= n – u + 1; i++)

{

j=i+u-1;

m[i][j]= 1e10;// очень большое число

for(k=i;k<j;k++)

{

q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

if (q < m[i][j])

{

m[i][j] = q;

s[i][j] = k; // запоминаем место умножения

} // if

} // for k

} // for i

} // for u

} // окончание функции

Сначала алгоритм заполняет диагональные элементы матрицы m нулями, так как стоимость перемножения последовательности из одной матрицы равна 0. При первом исполнении цикла по u вычисляются значения для m[i][i+1] для i=1,2,…,n-1 – это минимальные стоимости для последовательностей длины 2. При втором проходе вычисляются m[i][i+2] для i=1,2,…,n-2 – минимальные стоимости перемножения последовательностей длины 3, и т.д. На каждом шаге значение m[i][j] зависит только от вычисленных ранее значений m[i][k] и m[k+1][j].

Вот как это происходит для n=6. Матрицы m и s:

A1	A2	A3	A4	A5	A6			2	3	4	5	6
0	15759	7875	9375	11875	15125	A1		1	1	3	3	3	1
	0	2625	4375	7125	10500	A2			2	3	3	3	2
		0	750	2500	5375	A3				3	3	3	3
			0	1000	3500	A4					4	5	4
				0	5000	A5						5	5
					0	A6

Поскольку мы определяем m[i][j] только для i<=j, используется часть таблицы, лежащая над главной диагональю. m[i][j] – минимальная стоимость перемножения последовательности А_i*А_i+1*…*А_j.

Простая оценка показывает, что время работы алгоритма есть О(n³). Тем самым этот алгоритм значительно эффективнее, чем требующий экспоненциального времени перебор всех расстановок.