Главная Промышленная автоматика.

Кроме того, применяется процедура COPT(i, /) (рис. 2.14), сортирующая подпоследовательность Xi, x+j, ... , Xj в предположении, что она имеет длину 2* для некоторого АО.

Для сортировки данной последовательности Xi, х......Хп вызывается процедура С0РТ(1, п). □

Подсчет числа сравнений в алгоритме 2.4 приводит к рекуррентным уравнениям

j О при л= 1,

7(n)=J2r(rt/2) + n-l прил>1,

решением которых по теореме 2.1 является Т{п)=0(п log л). Для больших п сбалансированность размеров подзадач дала значительную выгоду. Аналогичный анализ показывает, что общее время работы процедуры СОРТ, затрачиваемое не только на сравнения, также есть О (п. log п).

2.8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Рекурсивная техника полезна, если задачу можно разбить на подзадачи за разумное время, а суммарный размер подзадач будет небольшим. Из теоремы 2.1 вытекает, что если сумма размеров подзадач равна an для некоторой постоянной а>1, то рекурсивный алгоритм, вероятно, имеет полиномиальную временную сложность. Но если очевидное разбиение задачи размера п сводит ее к л задачам размера п-1, то рекурсивный алгоритм, вероятно, имеет экспоненциальную сложность. В этом случае часто можно получить более эффективные алгоритмы с помощью табличной техники, называемой динамическим программированием.

Динамическое программирование, в сущности, вычисляет решение для всех подзадач. Вычисление идет от малых подзадач к большим, и ответы запоминаются в таблице. Преимущество этого метода состоит в том, что раз уж подзадача решена, ее ответ где-то хранится и никогда не вычисляется заново. Эту технику легко понять на простом примере.

Рассмотрим вычисление произведения п матриц

M = MiXM,X ... хМ„,

где Mi - матрица с ri-i строками и rj столбцами. Порядок, в котором эти матрицы перемножаются, может существенно сказаться на общем числе операций, требуемых для вычисления М, независимо от алгоритма, применяемого для умножения матриц.

Пример 2.7. Предположим, что умножение (р X (7)-матрицы на (9Хг)-матрицу требует pqr операций, как это и бывает в "обычном"



алгоритме, и рассмотрим произведение

М= Мх X М, X Ms xMt , (2.8)

[10x20] Г20х50] [50x1] [1X100]

где размеры каждой матрицы Mt указаны в скобках. Если вычислять М в порядке

MXiMxiMxM,)), то потребуется 125 ООО операций, тогда как вычисление М в порядке

(МхХ{М,хМ,))хМ

занимает лишь 2 200 операций. □

Процесс перебора всех порядков, в которых можно вычислить рассматриваемое произведение п матриц, с целью минимизировать число операций имеет экспоненциальную сложность (упр. 2.31), что при больших п практически неприемлемо. Однако динамическое программирование приводит к алгоритму сложности О (л*). Пусть niij - минимальная сложность вычисления MiXMt+iX. . .xMj, Очевидно, что

= = (2 9)

ч IMIN (m,ft + m;i+,.; + r, iV/), если / > t. »<*</

Здесь ffiih - минимальная сложность вычисления М=М,х xMi+iX. . .X/Wft, а mft+i J - минимальная сложность вычисления

Третье слагаемое равно сложности умножения М на М". Заметим, что М - матрица размера rj-jXrft, а М" - матрица размера гХ

begin

1. for t-<-1 until n do m,,-<-0;

2. for /1 until n-l do

3. for /•<-1 until n-l do

begin

4. ii+i;

5. m,.y MIN {mi-\-mk+i,f + ri-i*r*rj)

<<*</

end;

6. write nii„ end

Рие. 2.15. Алгоритм динамического программирования для определения порядка

умножения матриц.



Л7„= 0

Я7И=0

%з=0

т„=0

= 10000

/77„= 1000

Л7з4= 5000

Л7„ =: 1200

%45=3000

m„= 2200

Рис. 2.16. Сложности вычисления произведений MiXMi+iX...XM/.

ХГ]. В (2.9) утверждается, что гпц (j>i) - наименьшая из сумм этих трех членов по всем возможным значениям к, лежащим между i и /-1.

При динамическом программировании вычисляются в порядке возрастания разностей нижних индексов. Начинают с вычисления Шц для всех 1, затем /п, j+i для всех г, потом т,-, , + 2 и т. д. При этом /"ih и m+ij в (2.9) будут уже вычислены, когда мы приступим к вычислению mj;. Это следует из того, что при t<A</ разность ]-i должна быть больше к-i, а также и /-(A-fl). Приведем теперь алгоритм.

Алгоритм 2.5. Алгоритм динамического программирования для вычисления порядка, минимизирующего сложность умножения цепочки из п матриц AfiXAaX- -ХЛя

Вход. Го, п, . . . , г„, где rj i и Г - числа строк и столбцов матрицы Mi.

Выход. Минимальная сложность умножения матриц Mj в предположении, что для умножения (рХ9)-матрицы на (9Хг)-матрицу требуется pgr операций.

Метод. Алгоритм, приведенный на рис. 2.15. □

Пример 2.8. Если применить этот алгоритм к цепочке из четырех матриц (2.8), где Го, . . . , и равны соответственно 10, 20, 50, 1, 100, то в результате вычислений получатся значения т, приведенные на рис. 2.16. Таким образом, минимальное число операций, требуемых для вычисления этого произведения, равно 2 200. Порядок, в котором можно произвести эти умножения, легко определить, приписав каждой клетке таблицы то значение к, на котором достигается минимум в (2.9). □

2.9. ЭПИЛОГ

В этой главе мы изложили ряд основных методов, которыми пользуются при разработке эффективных алгоритмов. Было показано, как структуры высокого уровня - списки, очереди и стеки - избавляют разработчика алгоритмов от скучной работы (например.





0 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

0.0021