Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[100]

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

Теперь надо выразить стоимость оптимального решения задачи через стоимости оптимальных решений её подзадач. Такими подзадачами будут задачи об оптимальной расстановке скобок в произведениях Aj-..j = AjAi+i ... Aj для 1 г j га. Обозначим через m[i,j] минимальное количество умножений, необходимое для вычисления матрицы Aj-..j; в частности, стоимость вычисления всего произведения Ai..n есть га[1,га].

Числа га [г, j] можно вычислить так. Если г = j, то последовательность состоит из одной матрицы Аг-..г- = Аг- и умножения вообще не нужны. Стало быть, га[г, г] = 0 для г = 1,2,..., га. Чтобы посчитать m[i,j] для г < j, мы воспользуемся информацией о строении оптимального решения, полученной на шаге 1. Пусть при оптимальной расстановке скобок в произведении A8A8+i ... Aj последним идет умножение Аг-... А на A+i .. .Aj, где г k < j. Тогда m[i,j] равно сумме минимальных стоимостей вычисления произведений A4-..jt и Ajt+i..j плюс стоимость перемножения этих двух матриц. Поскольку для вычисления произведения A4-..jtAjt+i..j требуется pi-ipkPj умножений,

В этом соотношении подразумевается, что оптимальное значение к нам известно; на деле это не так. Однако число к может принимать всего лишь j - г различных значений: г, г + 1,..., j - 1. Поскольку одно из них оптимально, достаточно перебрать эти значения к и выбрать наилучшее. Получаем рекуррентную формулу:

Числа m[i,j] - стоимости оптимальных решений подзадач. Чтобы проследить за тем, как получается оптимальное решение, обозначим через s[i,j] оптимальное место последнего умножения, то есть такое к, что при оптимальном вычислении произведения АгАг 1 • • • Aj последним идет умножение Аг-.. .Аь на A+i ... Aj. Иными словами, s[i, j] равно числу к, для которого m[i, j] = m[i, к]-\-т[к + + рг 1РкрГ

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

Пользуясь соотношениями (16.2), теперь легко написать рекурсивный алгоритм, определяющий минимальную стоимость вычисления произведения А\А2 .. .Ап (т.е. число га[1,га]). Однако время

m[i,j]

га[г, к] + т[к + 1, j] + рг-Хркрг

)npHZ=j,

min {m[i, к] + т[к + + pi-iPkPj} при i < j.

(16.2)


работы такого алгоритма экспоненциально зависит от га, так что этот алгоритм не лучше полного перебора. Настоящий выигрыш во времени мы получим, если воспользуемся тем, что подзадач относительно немного: по одной задаче для каждой парыдля которой 1 г j га, а всего С2 + га = 0(га2). Экспоненциальное время работы возникает потому, что рекурсивный алгоритм решает каждую из подзадач по многу раз, на разных ветвях дерева рекурсии. Такое «перекрытие подзадач» - характерный признак задач, решаемых методом динамического программирования.

Вместо рекурсии мы вычислим оптимальную стоимость «снизу вверх». В нижеследующей программе предполагается, что матрица А{ имеет размер Pi-\ Xpi при г = 1, 2,..., га. На вход подаётся последовательность р = (ро, pi,..., рп), где length[p] = га + 1. Программа использует вспомогательные таблицы то[1. .га, 1. .га] (для хранения стоимостей m[i,j]) и s[l. .га, 1. .га] (в ней отмечается, при каком к достигается оптимальная стоимость при вычислении m[i,j]).

Matrix-Chain-Order (р)

1га <- length\p] - 1

2for г <- 1 to га

13 return то, s

Заполняя таблицу то, этот алгоритм последовательно решает задачи об оптимальной расстановке скобок для одного, двух, ... , га сомножителей. В самом деле, соотношение (16.2) показывает, что число m[i,j] - стоимость перемножения j - г + 1 матриц - зависит только от стоимостей меньшего (чем j - г + 1) числа матриц. Именно, для к = г, г + 1,..., j - 1 получается, что Аг-.. - произведение к - г + 1 < j - г + 1 матриц, a Ajt+i..j - произведение j - к < j - г + 1 матриц.

Сначала (в строках 2-3) алгоритм выполняет присваивания га [г, г] <- 0 для г = 1, 2,..., га: стоимость перемножения последовательности из одной матрицы равна нулю. При первом исполнении цикла (строки 4-12) вычисляются (с помощью соотношений (16.2)) значения то[г, г+1] для г = 1,2,..., га-1 - это минимальные стоимости для последовательностей длины 2. При втором проходе вычи-

3 4 5 6 7 8 9 10 11 12

for /

if q < то[г, j]


Рис. 16.1 Таблицы шиз, вычисляемые процедурой matrix-chain-order для п = 6 и матриц следующего размера:

матрица размер

Ав 20 х 25

Таблицы повёрнуты так, что главная диагональ горизонтальна. В таблице т используются только клетки, лежащие не ниже главной диагонали, в таблице s - только клетки, лежащие строго выше. Минимальное количество умножений, необходимое для перемножения всех шести матриц, равно то[1, 6] = 15 125. Пары клеточек, заштрихованных одинаковой светлой штриховкой, совместно входят в правую часть формулы в процессе вычисления т[2,5] (строка 9 процедуры Matrix-Chain-Order):

{то[2, 2] + то[3, 5] +pip2p5 = 0 + 2500 + 35 • 15 • 20 = 13000, то[2, 3] + то[4, 5] + pipsps = 2625 + 1000 + 35 • 5 • 20 = 7125, то[2, 4] + то[5, 5] + pipips = 4375 + 0 + 35 • 10 • 20 = 11375.

сляются m[i, г + 2] для г = 1,2,..., га - 2 - минимальные стоимости перемножения последовательностей длины 3, и так далее. На каждом шаге значение m[i,j], вычисляемое в строках 9-12, зависит только от вычисленных ранее значений m[i, к] и т[к +

На рис. 16.1 показано, как это происходит при га = 6. Поскольку мы определяем m[i,j] только для г j, используется часть таблицы, лежащая над главной диагональю. На рисунке таблицы повёрнуты (главная диагональ горизонтальна). Внизу выписана последовательность матриц. Число m[i,j] - минимальная стоимость перемножения подпоследовательности AjAi+\ .. .Aj - находится на пересечении диагоналей, идущих вправо-вверх от матрицы Ai и влево-вверх от матрицы Aj. В каждом горизонтальном ряду собраны стоимости перемножения подпоследовательностей фиксированной длины. Для заполнения клетки m[i,j] нужно знать произведения pi \pkPj для к = i, i + 1,..., j - 1 и содержимое клеток, лежащих слева-внизу и справа-внизу от m[i,j].

Аг А2 А3 А4 А5

30 х 35 35 х 15 15 х 5 5 х 10 10 х 20



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]