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

(7) return (0) else begin

(8) A:= левые nil биты числа X;

(9) В:- правые и/2 биты числа X;

(10) С:= левые л/2 биты числа Г;

(11) D:= правые л/2 биты числа У;

(13) ml:= mult(A, С, п/2) ;

(14) ш2:= mult(/i-B, D-C, п/2);

(15) шЗ: = mult(B, D, п/2);

(16) return (s * {Я11*2" + (ml + ml + тЗ) * г" + тЗ) ) end

end; { mult }

Обратите внимание, что алгоритм, разработанный по методу декомпозиции (листинг 10.1), оказывается асимптотически быстрее, чем метод, которому обучают в средней школе (требует только 0(га®) шагов вместо 0(га)). Таким образом, возникает закономерный вопрос: если этот алгоритм настолько лучше, почему именно его не изучают в средней школе? На этот вопрос можно дать два ответа. Преаде всего, этот алгоритм удобен для реализации на компьютере; если бы мы попытались излагать его в средней школе, учащиеся так и не научились бы умножать целые числа. Более того, мы игнорировали константы пропорциональности. В то время как процедура mult асимптотически превосходит обычный метод, константы таковы, что в случае небольших задач (реально - до 500 бит) метод, излагаемый в средней школе, оказывается лучше.

Составление графика проведения теннисного турнира

Метод декомпозиции получил широкое применение не только при разработке алгоритмов, но и в проектировании электронных схем, построении математических доказательств и в других сферах. В качестве иллюстрации приведем лишь один пример. Рассмотрим составление расписания проведения теннисного турнира по круговой схеме для и = 2* игроков. Каждый игрок должен сыграть со всеми другими игроками, при этом каждый игрок должен играть по одному матчу в день в течение п - 1 дней - минимального количества дней, необходимых для проведения всего турнира.

Расписание проведения турнира, таким образом, представляет собой таблицу, состоящую из л строк и и - 1 столбцов; элементом на пересечении строки / и столбца j является номер игрока, с которым игрок / должен провести матч в У-й день.

Метод декомпозиции позволяет составить расписание для половины игроков. Это расписание составляется на основе рекурсивного применения данного алгоритма для половины этой половины игроков и т.д. Когда количество игроков будет сокращено до двух, возникнет "базовая ситуация", в которой мы просто устанавливаем порядок проведения встреч мевду ними.

Допустим, в турнире участвуют восемь игроков. Расписание для игроков 1 - 4 заполняет верхний левый угол (4 строкихЗ столбца) составляемого расписания. Нижний левый угол (4 строкихЗ столбца) этого расписания должен свести между собой игроков с более высокими номерами (5 - 8). Эта часть расписания получается путем прибавления числа 4 к кавдому элементу в верхнем левом углу.

Итак, нам удалось упростить задачу. Теперь остается свести между собой игроков с низкими и более высокими номерами. Сделать это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 - 4, с игроками 5-8 соответственно, а в последующие дни просто циклически переставлять номера 5-8. Этот процесс показан на рис. 10.3. Надеемся, теперь читатель сможет обобщить описанный алгоритм и составить расписание для 2* игроков при любом значении к.

10.1. АЛГОРИТМЫ "РАЗДЕЛЯЙ И ВЛАСТВУЙ" 279




2 3

3 4

4 3

1 2

2 1


Рис. 10.3. Организация кругового турнира для восьми игроков

Баланс подзадач

При проектировании алгоритмов приходится идти на различные компромиссы. Очевидно, что по мере возможности необходимо сбалансировать вычислительные затраты на выполнение различных частей алгоритма. Например, в главе 5 было показано, что 2-3 дерево позволяет сбалансировать затраты на поиск элементов с затратами на их вставку, в то время как более прямолинейные методы требуют выполнения 0(п) шагов как для каждого поиска, так и для каждой вставки (несмотря на то что другие операции можно выполнить за постоянное число шагов).

Аналогично, при использовании алгоритмов декомпозиции желательно, чтобы подзадачи были примерно одинакового размера. Например, сортировку вставками можно рассматривать как разбиение задачи на две подзадачи - одна размером 1, а другая - и - 1, причем максимальные затраты на выполнение слияния равняются п шагам. В результате приходим к рекуррентному соотношению Т(п) = Т(Х)+ Т(п - 1) -i- п , которое имеет решение О(га). В то же время сортировка слиянием разбивает задачу на две подзадачи, каждая размером п/2, а ее эффективность равняется 0(л logn). Складывается впечатление, что разбиение задачи на равные (или примерно равные) подзадачи является важным фактором обеспечения высокой эффективности алгоритмов.

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

Нередко не удается разбить задачу на небольшое число подзадач, объединение решений которых позволяет получить решение исходной задачи. В таких случаях мы можем попытаться разделить задачу на столько подзадач, сколько необходимо, затем каждую подзадачу разделить на еше более мелкие подзадачи и т.д. Если бы весь алгоритм сводился именно к такой последовательности действий, мы бы получили в результате алгоритм с экспоненциальным временем выполнения.

Но зачастую удается получить лишь полиномиальное число подзадач и поэтому ту или иную подзадачу приходится решать многократно. Если бы вместо этого мы отслеживали решения каждой решенной подзадачи и просто отыскивали в случае необходимости соответствуюшее решение, мы бы получили алгоритм с полиномиальным временем выполнения.

С точки зрения реализации иногда бывает проше создать таблицу решений всех подзадач, которые нам когда-либо придется решать. Мы заполняем эту таблицу независимо от того, нужна ли нам на самом деле конкретная подзадача для получения обшего решения. Заполнение таблицы подзадач для получения решения определен-



ной задачи получило название динамического программирования (это название происходит из теории управления).

Формы алгоритма динамического программирования могут быть разными - общей их "темой" является лишь заполняемая таблица и порядок заполнения ее элементов. Соответствующие методы проиллюстрируем на основе двух примеров: вычисление шансов на победу команд в спортивных турнирах и решение так называемой "задачи триангуляции".

Вероятность победы в спортивных турнирах

Допустим, две команды Аи В проводят между собой турнир. Победителем считается тот, кто первым выиграет п матчей. Можно предположить, что силы команд А и Б примерно равны, т.е. у калсдой из них есть 50% шансов выиграть очередной матч. Допустим, P(i, j) - вероятность того, что если А для победы нужно провести i матчей, а В - j матчей, то в конечном счете победу на турнире одержит А. Например, если в турнире "Мировой серии" команда Dodgers выиграла два матча, а команда Yankees - один, то i = 2, j = 3 я оказывается (мы в этом еще убедимся), что Р(2, 3) равняется 11/16.

Чтобы вычислить P(i, j), можно воспользоваться рекуррентным уравнением с двумя переменными. Во-первых, если / = О и ; > О, то команда А уже выиграла турнир, поэтому Р(0. j) = 1. Аналогично, P(i, 0) = О для i > 0. Если как i, так и j больше нуля, командам придется провести по крайней мере еще один матч с равными шансами выиграть эту игру. Таким образом, P(i, j) должно быть средним значением P(i - I, j) и Р(1, j - 1), первое из этих выражений представляет собой вероятность того, что команда выиграет турнир, если победит в следующем матче, а второе - вероятность того, что команда выиграет турнир, даже если проиграет следующий матч. Итак, получаем следующие рекуррентные соотношения:

PiiJ)= 1, если i = О и / > О, /"(/j;) = О, если i > О и у = О,

Р(г. /) = (P(i - 1. j) + P(iJ - 1 ))/2, если i > Ои у > 0. (10.4)

На основании соотношений (10.4) можно показать, что вычисление P(i, у) требует времени не больше, чем 0{2*). Обозначим через Г(ге) максимальное время, которое требуется для вычисления P(i,j), тле i + у = п. Тогда из (10.4) следует

т=с,

Т(п) = 2Т{п-1) +d,

для некоторых констант end. Читатель может проверить (воспользовавшись средствами, обсулсдавшимися в предыдущей главе), что Т(п)< 2"с+ {2" - l)d, что соответствует 0(2") или О(2"0.

Таким образом, мы установили экспоненциальную верхнюю границу времени, требуемого для рекурсивных вычислений P(i,j). Но если мы хотим убедиться в том, что рекуррентная формула для P(i, j) - не самый лучший способ вычисления этой вероятности, надо найти нилснюю границу времени вычисления. В качестве упралс-нения рекомендуем читателям показать, что при вычислении P(i, j) общее количество вычислений вероятностей Р с меньшими значениями 1 и у, которые приходится выполнять, равняется С,,,т.е. числу способов выбрать / элементов из i + j. Если / - j,

Динамическим программированием (в наиболее общей форме) называют процесс пошагового рещения задач, когда на каждом щаге выбирается одно рещение из множества допустимых (на этом щаге) рещении, причем такое, которое оптимизирует заданную целевую функцию или функцию критерия. (В приведенных далее примерах процесс пощагового рещения задачи сводится к пощаговому заполнению таблиц.) В основе теории динамического программирования лежит принцип оптимальности Беллмана. Более подробно о теории динамического программирования см. [7]. - Прим. ред.

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





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

0.0037