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

дующей выбрать вершину v, то получим треугольник (vq, г>з, t>4) и подзадачу (uo, t>4, t>5, t>e), в которой осталась только одна хорда исходного многоугольника. Если мы выберем вершину 1)5, то получим подзадачи (1)3, V4, 1)5) и (оц, 1)5, ug) с хордами

<f3, Us) и (Do, V).



Рмс. 10.6. Две подзадачи, возникающие после выбора вершины \з

Определим подзадачу размера s, начинающуюся с вершины и, и обозначаемую S, как задачу минимальной триангуляции для многоугольника, образованного s вершинами, начинающегося с вершины t>, и содержащего вершины v„ Vi+i, ... , Vi+s-i, перечисляемые в порядке обхода вершин многоугольника по часовой стрелке. В S.-j хордой является замыкающая сторона (и,, Dj+s-i)- Например, многоугольник на рис. 10.б,а является подзадачей S04. а на рис. 10.6,6- подзадачей 5з5. Чтобы решить подзадачу S,,, необходимо рассмотреть три следующих варианта.

1. Можно выбрать вершину t>,.j 2. чтобы составить треугольник с хордами (Vj, Uj+s-i) и (i>i, 0,45-2) и третьей стороной (и.+з-г» Ii+s-i). а затем решить подзадачу Sj,s-i.

2. Мы можем выбрать вершину чтобы составить треугольник с хордами {Vj, t>i+3 1) И (t>i+i, Uiis-i) И третьей стороной (и, а затем решить подзадачу S,i,,i.

3. Для некоторого k из диапазона от 2 до s - 3 можно выбрать вершину t>,+(, и образовать треугольник со сторонами (и,, У;,»), (и,+», Uits-i) и (vi, Dj+s 1). а затем решить подзадачи S,j6+iH S,+i,.s-f

Если вспомним, что "решение" любой подзадачи размером не более трех не требует вообще никаких действий, то, рассматривая описанные варианты 1-3, следует предпочесть вариант 3, где надо выбрать некоторое к из диапазона от 1 до s - 2 и решить подзадачи S/+i и Рис. 10.7 иллюстрирует описанное разбиение на

подзадачи.

Если для решения подзадач размером четыре и более воспользоваться очевидным рекурсивным алгоритмом, вытекающим из перечисленных выше вариантов, то можно показать, что каждое обращение к подзадаче размером s приводит к общему количеству рекурсивных вызовов, равному 3", если подсчитывать лишь обращения к

Еще раз напомним, что номера вершин вычисляются по модулю га (л - количество вершин исходного многоугольника). Поэтому в подзадаче Sa.s вершиной Ui+s-i является вершина W3+5-1 = и? = fo. - Прим. ред.



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


Рис. 10.7. Разбиение задачи Sj на подзадачи

Тем не менее в проведенном нами анализе что-то явно "не так", поскольку известно, что, помимо исходной задачи, сушествует лишь п(п-4) различных подзадач, которые в любом случае необходимо решить. Их можно представить как подзадачи Sis, где 0<1<яи4<8<л. Очевидно, не все подзадачи, решенные с помошью рекурсивной процедуры, различаются между собой. Если, например, на рис. 10.5 выбрать хорду (vv, 1)3), а затем в подзадаче на рис. 10.6,6 выбрать V4, то придется решить подзадачу S44. Но эту же задачу надо было бы решать, если бы сначала была выбрана хорда (dq, V4), а затем, решая подзадачу S45, выбрана вершина dq (чтобы замкнуть треугольник с вершинами Di и V4).

Это подсказывает нам эффективный способ решения задачи триангуляции. Мы составляем таблицу, назначая стоимость С,з триангуляции S,-s для всех i и s. Поскольку решение любой данной задачи зависит лишь от решения задач меньшего размера, логическим порядком заполнения такой таблицы является порядок, основанный на размерах подзадач, т.е. для размеров s = 4, 5,- п - 1 мы указываем минимальную стоимость задач S,, для всех вершин г. Удобно включить и задачи размеров О < s < 4, но при этом нужно помнить, что S,s имеет стоимость О, если s < 4.

В соответствии с перечисленными выше вариантами действий 1-3 при определении подзадач формула вычисления C/s при s > 4 должна иметь следующий вид:

С„ = mm [С,,.„ + С,,,,., + D(u,,l.,.J + D(v,,.l,, ,)]. (10.5)

где D(vp,Vg) - длина хорды между вершинами Dp и Vg, если Vp и и, не являются смежными вершинами многоугольника; D(Vp,Vg) равняется О, если Vp и являются смежными вершинами.

Пример 10.2. В табл. 10.2 приведены затраты для триангуляции Sj,s при О < / < 6 и 4 < S < 6, причем за основу взят многоугольник и расстояния, показанные на рис. 10.5. Все затраты для строк с s<3 равны нулю. Мы заполнили элемент Сот (столбец О и строка для s = 7). Этот элемент, как и все остальные элементы этой строки, представляет стоимость триангуляции всего многоугольника. Чтобы убедиться в этом, нужно лишь обратить внимание на то, что мы можем рассматривать сторону (vo, Ve) как хорду большего многоугольника, а многоугольник, показанный на рис. 10.5, - как подзадачу этого многоугольника, которая включает ряд до-



полнительных вершин, располагающихся по часовой стрелке от верщины vg до верщины Vq. Обратите внимание, что вся строка для s = 7 должна иметь то же значение, что и Со7, по крайней мере, в пределах погрещности вычислений.

В качестве примера покажем, как заполняется элемент в столбце для г = 6 и в строке для S = 5. В соответствии с (10.5) значение этого элемента (Cgs) представляет собой минимальное значение из трех сумм, соответствующих k = 1, 2 или 3. Вот эти суммы:

Таблица 10.2. Таблица стоимостей Q

Со7 = 75.43

Соб = 53.34

Ci6 =

55.22

= 57.54

= 59.67

= 59.78

= 59.78

= 63.61

Со5 = 37.54

Cl5 =

31.81

= 35.45

= 37.74

= 45.50

= 39.98

= 38.09

Сол = Г6.Г6

См =

= Г6.Г6

= 15.65

= 15.65

С44 =

= 22.09

= 22.09

= 17.89

1 = 0

Требуемые нам расстояния вычисляются на основе координат верщин следующим образом: Div.v) = D{Vg,v„) = О (поскольку это стороны многоугольника, а не хорды, и предоставляются "бесплатно"), далее:

D(v,.v,)= 26.08,

D(vi,v,) = 16.16,

D(t>e,i>i)= 22.36 ,

£>(D„. Уз) = 21.93.

Указанными тремя суммами являются 38.09, 38.52 и 43.97 соответственно. Отсюда видно, что минимальная стоимость подзадачи See равняется 38.09. Более того, поскольку первая сумма оказалась наименьщей, то теперь мы знаем, что для достижения этого минимума надо использовать подзадачи 82 и S04, т.е. выбрать хорду (vo, V3), а затем найти оптимальное рещение для 5в4; для этой подзадачи хорда (Vi, V3) является предпочтительным вариантом. □

Заполнять табл. 10.2 удобно приемом, который вытекает из формулы (10.5). Каждое выражение в (10.5) требует пары элементов. В первую пару для к = 1 входит элемент из самого низа таблицы (строка для s = 2) в столбце вычисляемого элемента и элемент, который находится на одну строку ниже и справа от вычисляемого элемента. Первый элемент второй пары находится на один ряд выще "дна" таблицы в столбце вычисляемого элемента, второй отстоит от вычисляемого элемента на две позиции вниз и вправо. На рис. 10.8 показаны две линии элементов, следуя за которыми получим все пары элементов, которые будут анализироваться одновременно. Модель продвижения - вверх по столбцу и вниз по диагонали - является общепринятой при заполнении таблиц в методе динамического программирования.

* Не забывайте, что табл. 10.2 содержит нулевые строки ниже тех, которые показаны.

Говоря "справа", мы подразумеваем таблицу с циклическим возвратом из конца в начало. Таким образом, если мы находимся в крайнем справа столбце, то столбцом "справа" от него будет крайний слева столбец.





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