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

это число равно Sl{2"/\fn), где га = i + Таким образом, Т{п) равняется ii(2"/>/n), и,

по сушеству, мы можем показать, что оно также равняется 0(2"/sfn) • В то время как

2"/Jn растет медленнее, чем 2", разница все же невелика, и Т{п) растет настолько быстро, что использование рекуррентных вычислений P(i, J) является совершенно неоправданным.

Проблема с рекуррентными вычислениями заключается в том, что нам приходится периодически вычислять одно и то же значение P(i, j) несколько раз. Если, например, надо вычислить Р(2, 3), то в соответствии с (10.4) требуется сначала вычислить Р(1, 3) и Р(2, 2). Однако для вычисления Р(1, 3) и Р(2, 2) нужно вычислить Р(1,2), т.е. одно и то же значение Р(1, 2) мы вычисляем дважды.

Более рациональным способом вычисления P(i, J) является заполнение специальной таблицы (табл. 10.1), в нижней строке которой присутствуют одни нули, а крайний правый столбец целиком заполнен единицами (это соответствует первым двум строкам из (10.4)). Что же касается последней строки (10.4), то все остальные элементы таблицы представляют собой средние значения элементов, находяшихся снизу и справа от соответствуюшего элемента. Таким образом, таблицу следует заполнять начиная с ее нижнего правого угла и продвигаться вверх и влево вдоль диагоналей, представляюших элементы с постоянным значением i + j, как показано на рис. 10.4. Соответствуюшая программа приведена в листинге 10.2 (предполагается, что она работает с двумерным массивом Р подходяшего размера).


Рис. 10.4. Шаблон вычислений

Таблица 10.1. Таблица вероятностей

21/32

13/16

15/16

11/32

11/16

3/16

5/16

1/16

Листинг 10.2. Вычисление вероятностей

function odds ( integer ): real;

s, k: integer;

begin

(1) for s:= 1 to i + j do begin

{ вычисление элементов массива P,

сумма индексов которых равняется s }

(2) Р[0, s] := 1.0;

(3) =[5,0] ;= 0.0;



(4) for ;::= 1 to s - 1 do

(5) P[k, s-k-\:= (P(k-l, s-k] + P\k, з-к-\\)12. end;

(6) retum(P[i, у 7 ; end; { odds }

Анализ функции odds (шансы) не представляет особых затруднений. Цикл, включающий строки (4), (5), занимает 0(s) времени, которое превосходит время 0(1) для

строк (2), (3). Таким образом, выполнение внешнего цикла занимает время 0(5" s)

или О(л), где п = i + j. Следовательно, вычисления по методу динамического программирования требуют времени О(л), тогда как в "прямолинейном" подходе к вычислениям необходимо время порядка 0(2"/7л). Поскольку величина 2"/4п растет намного быстрее, чем л, динамическое программирование предпочтительнее как в данном случае, так практически в любых других обстоятельствах.

Задача триан гуляци И

в качестве еще одного примера динамического программирования рассмотрим задачу триангуляции многоугольника. Заданы вершины многоугольника и расстояния между каждой парой вершин. Это расстояние может быть обычным евклидовым расстоянием на плоскости или произвольной функцией стоимости, задаваемой в виде таблицы. Задача заключается в том, чтобы выбрать такую совокупность хорд (линий между несмежными вершинами), что никакие две хорды не будут пересекаться, а весь многоугольник будет поделен на треугольники. Общая длина выбранных хорд должна быть минимальной. Такая совокупность хорд называется минимальной триангуляцией.

Пример 10.1. Па рис. 10.5 показан многоугольник с семью сторонами, (х, у) - координаты его вершин. Расстояния вычисляются как обьиное евклидово расстояние. Триангуляция, оказавшаяся не минимальной, изображена пунктирными линиями. Ее стоимостью является сумма длин хорд (t>o, Пг), (uo, «з), (uq, v) и (ug, 1)5),

или Vs + 16 -Ь Vl5 + 16 + V22" + 2" + V? + 14 = 77.56 . П

(8,26)

(15,26)


( w (27,21)

Is) (22,12)

(10,0)

Рис. 10.5. Многоугольник и его триангуляция



Задача триангуляции, представляющая интерес сама по себе, имеет к тому же ряд полезных применений. Например, в статье [40] использовали обобщение задачи триангуляции для следующей цели. Рассмотрим задачу создания двумерной тени объекта, поверхность которого определяется совокупностью точек в трехмерном пространстве. Свет на объект падает из неподвижного источника, и яркость любой точки на поверхности зависит от углов между направлением света, положением наблюдателя и перпендикуляром (нормалью) к поверхности в этой точке. Чтобы определить нормаль к поверхности в какой-либо точке, надо найти минимальную триангуляцию точек, определяющих эту поверхность.

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

Прежде чем продолжить рещение задачи триангуляции с помощью динамического программирования, необходимо зафиксировать два факта относительно триангуляции. Они помогут разработать требуемый алгоритм. Предполагаем, что нащ многоугольник имеет п верщин Vo, Vy,... i>„ i, перечисленных по часовой стрелке.

Факт 1. В случае триангуляции любого многоугольника, содержащего более трех верщин, с каждой парой смежных верщин связана по крайней мере одна хорда. Чтобы убедиться в этом, допустим, что ни Vi, ни не связаны ни с какой из хорд. В таком случае область, ограничиваемая стороной (vi, n.+i), должна была бы включать стороны (t>( 1, t>,),(t>,4i, t>j+2) и по крайней мере еще одну дополнительную сторону или хорду. В таком случае эта область не была бы треугольником.

Факт 2. Если (t>,> Vj) является хордой в триангуляции, значит, должна найтись такая верщина и*, что каждая из линий {v„ V/,) и (v,,, vj) должна быть либо стороной многоугольника, либо хордой. В противном случае хорда (и, иу)ограничивала бы область, не являющуюся треугольником.

Чтобы приступить к поиску минимальной триангуляции, выберем две смежные верщины, например t>o и Uj. Из указанных выще фактов следует, что в любой триангуляции (и, следовательно, в минимальной триангуляции) должна найтись такая верщина и,, что (di, d) и (dj, vq) являются хордами или сторонами многоугольника. Необходимо рассмотреть, насколько приемлемую триангуляцию можно построить после выбора каждого возможного значения к. Если в многоугольнике п верщин, в нащем распоряжении имеется (л - 2) возможных вариантов.

Каждый вариант выбора к приводит к не более чем двум подзадачам, где мы имеем многоугольники, образованные одной хордой и сторонами исходного многоугольника. Например, на рис. 10.6 показаны две подзадачи, которые возникают в случае, если выбрана верщина 1)3.

Далее нуясно найти минимальную триангуляцию для многоугольников, показанных на рис. 10.6,аи 10.6,6. Можно, например, рассмотреть все хорды, исходящие из двух смежных верщин. Тогда, рещая задачу, показанную на рис. 10.6,6, мы должны, в частности, рассмотреть вариант хорды (1)3, v), которая поролсдает подзадачу с многоугольником (Do, «з, >5> fe). две стороны которого (do, Уз) и (о, 1)5) являются хордами исходного многоугольника. Этот подход приводит к алгоритму с экспоненциальным временем выполнения..

Но, имея треугольник, включающий хорду (do, d,), нам никогда не придется рассматривать многоугольники, у которых более одной стороны являются хордами исходного многоугольника. "Факт 2" говорит о том, что при минимальной триангуляции хорда в подзадаче (например, хорда (dq, «з) на рис. 10.6,6) должна составлять треугольник с одной из остальных верщин многоугольника. Если, например, сле-

В дальнейшем предполагается, что все нижние индексы вычисляются по модулю п. Ти-ким образом, Vj и на рис. 10.5 могли бы бьпь гв и vo соответственно, поскольку п = 7.





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.0278