Структуры данных и алгоритмы (1021739), страница 74
Текст из файла (страница 74)
Если, например, сле1В дальнейшем предполагается, что все нижние индексы вычисляются по модулю п.м образом, и, и vt+i на рис. 10.5 могли бы быть ve и i>o соответственно, поскольку п = 7.284ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВдующей выбрать вершину и4, то получим треугольник (v0, v3, V+) и подзадачу(и0, i>4, i>5. ve), в которой осталась только одна хорда исходного многоугольника. Еслимы выберем вершину vs, то получим подзадачи (i>3, v4, vs) и (va, vs, ve) с хордами(va, vs) и (u0, vs).абРис.
10.6. Две подзадачи, возникающие после выбора вершины v3Определим подзадачу размера s, начинающуюся с вершины vt и обозначаемую Sjs,как задачу минимальной триангуляции для многоугольника, образованного s вершинами, начинающегося с вершины и, и содержащего вершины vt, ui+1, ... , UH-S-I, перечисляемые в порядке обхода вершин многоугольника по часовой стрелке.
В Sts хордой является замыкающая сторона (и,-, у(+з_!). Например, многоугольник нарис. 10.6,а является подзадачей S04, а на рис. 10.6,6 — подзадачей Sss-1 Чтобы решить подзадачу S,-s, необходимо рассмотреть три следующих варианта.1. Можно выбрать вершину vi+s_2, чтобы составить треугольник с хордами (vt, vi+s-i)и (vit у,-+,_2) и третьей стороной (vi+s-2, iW-i). а затем решить подзадачу Sj,s-i.2. Мы можем выбрать вершину vl+i, чтобы составить треугольник с хордами(и,-, Uj+s-i) и (vi+1, t>j+s-i) и третьей стороной (u f , u i+ i), а затем решить подзадачу S(+i.,_i.3. Для некоторого k из диапазона от 2 до s - 3 можно выбрать вершину vi+k и образовать треугольник со сторонами (vt, 1^+4), (Uj+t, Uj+,,-i) и (vi, vi+s-i), а затем решитьподзадачи Sfjm и Si+k,s-k.Если вспомним, что "решение" любой подзадачи размером не более трех не требует вообще никаких действий, то, рассматривая описанные варианты 1-3, следуетпредпочесть вариант 3, где надо выбрать некоторое k из диапазона от 1 до s - 2 ирешить подзадачи Sj,A+1 и Sj+tiS_A.
Рис. 10.7 иллюстрирует описанное разбиение наподзадачи.Если для решения подзадач размером четыре и более воспользоваться очевиднымрекурсивным алгоритмом, вытекающим из перечисленных выше вариантов, то можно показать, что каждое обращение к подзадаче размером s приводит к общему количеству рекурсивных вызовов, равному 3s"4, если подсчитывать лишь обращения к1Еще раз напомним, что номера вершин вычисляются по модулю га (п — количество вершин исходного многоугольника). Поэтому в подзадаче Sss вершиной u,+»-i является вершинаиз+5-i = vi = v0. — Прим.
ред.10.2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ285подзадачам размером четыре и более. Таким образом, количество подзадач, которыенеобходимо решить, возрастает по экспоненциальному закону в зависимости от s.Поскольку исходная задача имеет размер п, где п — количество вершин в заданноммногоугольнике, общее количество шагов, выполняемых этой рекурсивной процедурой, возрастает экспоненциально по п.Рис.
10.7. Разбиение задачи Sis на подзадачиТем не менее в проведенном нами анализе что-то явно "не так", поскольку известно, что, помимо исходной задачи, существует лишь п(га-4) различных подзадач,которые в любом случае необходимо решить. Их можно представить как подзадачиSis, где 0 < I < п и 4 < s < л. Очевидно, не все подзадачи, решенные с помощью рекурсивной процедуры, различаются между собой.
Если, например, на рис. 10.5 выбрать хорду (и0> ^з). а затем в подзадаче на рис. 10.6,6 выбрать i>4, то придется решить подзадачу S44- Но эту же задачу надо было бы решать, если бы сначала былавыбрана хорда (и0, v4), а затем, решая подзадачу S45, выбрана вершина и0 (чтобызамкнуть треугольник с вершинами иг и i>4).Это подсказывает нам эффективный способ решения задачи триангуляции.Мы составляем таблицу, назначая стоимость С„ триангуляции S(, для всех i и s.Поскольку решение любой данной задачи зависит лишь от решения задач меньшего размера, логическим порядком заполнения такой таблицы является порядок, основанный на размерах подзадач, т.е.
для размеров s = 4, 5,- ..., п - 1 мыуказываем минимальную стоимость задач S(S для всех вершин г. Удобно включить и задачи размеров 0 < s < 4, но при этом нужно помнить, что S,-, имеетстоимость 0, если s < 4.В соответствии с перечисленными выше вариантами действий 1-3 при определении подзадач формула вычисления Cts при s > 4 должна иметь следующий вид:где D(vp,vq) — длина хорды между вершинами vp и и„, если vp и vq не являютсясмежными вершинами многоугольника; D(vp,vq) равняется 0, если vp и vq являютсясмежными вершинами.Пример 10.2. В табл. 10.2 приведены затраты для триангуляции SiiS при 0 < i < 6и 4 < s < 6, причем за основу взят многоугольник и расстояния, показанные нарис.
10.5. Все затраты для строк с s < 3 равны нулю. Мы заполнили элемент С01(столбец 0 и строка для s = 7). Этот элемент, как и все остальные элементы этойстроки, представляет стоимость триангуляции всего многоугольника. Чтобы убедиться в этом, нужно лишь обратить внимание на то, что мы можем рассматриватьсторону (vQ, ve) как хорду большего многоугольника, а многоугольник, показанныйна рис.
10.5, — как подзадачу этого многоугольника, которая включает ряд до286ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВполнительных вершин, располагающихся по часовой стрелке от вершины ив довершины и0- Обратите внимание, что вся строка для s = 7 должна иметь то же значение, что и С07, по крайней мере, в пределах погрешности вычислений.В качестве примера покажем, как заполняется элемент в столбце для i = 6 и встроке для s = 5. В соответствии с (10.5) значение этого элемента (Св5) представляет собой минимальное значение из трех сумм, соответствующих k = 1, 2 или 3. Вотэти суммы:С„2 + С04 + D(ve, va) + D(v0, v3) ,Свз + С,,,vJ + D(vltv3) ,Cei + С22,v2) + D(v2,v3) .Таблица 10.2.
Таблица стоимостей Ch7Со? = 75.436Сое = 53.34Cie = 55.22С2в = 57.54C36 = 59.67С46 = 59.78С56 = 59.78С66 = 63.615Cos = 37.54Cis = 31.81CK = 35.45C35 = 37.74С45 = 45.50С55 = 39.98С65 = 38.094С04 = 16.16Cl4 = 16.16C24 = 15.65Сз4 = 15.65С44 = 22.09С54 = 22.09С64 = 17.89si=0123456Требуемые нам расстояния вычисляются на основе координат вершин следующимобразом: D(v2,v3) = D(ve,v0) = 0 (поскольку это стороны многоугольника, а не хорды,и предоставляются "бесплатно"), далее:D(ue,i>2) = 26.08,-D(i>i,i>3) = 16.16,D(ve,Vl) = 22.36,D(v0,va)= 21.93.Указанными тремя суммами являются 38.09, 38.52 и 43.97 соответственно. Отсюда видно, что минимальная стоимость подзадачи S85 равняется 38.09. Более того,поскольку первая сумма оказалась наименьшей, то теперь мы знаем, что для достижения этого минимума надо использовать подзадачи S62 и S04, т.е.
выбрать хорду(VQ, i>3), а затем найти оптимальное решение для SH4; для этой подзадачи хорда(vi, v3) является предпочтительным вариантом. ПЗаполнять табл. 10.2 удобно приемом, который вытекает из формулы (10.5).Каждое выражение в (10.5) требует пары элементов. В первую пару для k = 1 входит элемент из самого низа таблицы (строка для s = 2)1 в столбце вычисляемогоэлемента и элемент, который находится на одну строку ниже и справа от вычисляемого элемента2.
Первый элемент второй пары находится на один ряд выше"дна" таблицы в столбце вычисляемого элемента, второй отстоит от вычисляемогоэлемента на две позиции вниз и вправо. На рис. 10.8 показаны две линии элементов, следуя за которыми получим все пары элементов, которые будут анализироваться одновременно. Модель продвижения — вверх по столбцу и вниз по диагонали — является общепринятой при заполнении таблиц в методе динамического программирования.1Не забывайте, что табл.
10.2 содержит нулевые строки ниже тех, которые показаны.Говоря "справа", мы подразумеваем таблицу с циклическим возвратом из конца в начало.Таким образом, если мы находимся в крайнем справа столбце, то столбцом "справа" от Hei-oбудет крайний слева столбец.210.2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ287Поиск решений на основе таблицыНесмотря на то что табл. 10.2 позволяет определить стоимость минимальной триангуляции, из нее непосредственно нельзя определить саму минимальную триангуляция, так как для этого надо знать значение k, которое обеспечивает минимум вформуле (10.5). Если мы знаем значение k, тогда решение состоит из хорд (vt, ui+k) и(vl+k, i>j+s-i) (за исключением случая, когда одна из них не является хордой, так какk = 1 или k = s - 2) плюс хорды, указываемые решениями Siik+i и Sj+tiS_t.
При вычислении элементов таблицы полезно включить в нее значения k, при которых получаем минимум в формуле (10.5).Пример 10.3. В табл. 10.2 значение элемента С07 (который представляет решениезадачи триангуляции многоугольника из рис. 10.5) получено как минимум формулы(10.5) при k = 5. Другими словами, задача S07 разбивается на подзадачи S0e и S52:первая из них представляет собой задачу с шестью вершинами v0, иъ ... ,i>5, а втораяявляется тривиальной "задачей" стоимости О. Таким образом, мы имеем хорду(VQ, v&) стоимостью 22.09 и должны решить подзадачу S0eМинимальная стоимость для С0а получается из (10.5) при k = 2, в результате чегозадача S0e разбивается на подзадачи S0s и S24. Первая из них представляет собойтреугольник с вершинами v0, v\ и v2, в т° время как вторая представляет собой четырехугольник, определяемый вершинами v2, v3, i>4 и t>5.
S03 решать не требуется,нужно решить только подзадачу S24. Кроме того, надо включить в стоимость минимальной триангуляции стоимости хорд (i>0, V2) и (u2, u5), равные соответственно 17.89и 19.80. Для С24 минимальное значение в (10.5) получается при k = 1, давая подзадачи С22 и Сзз, причем обе они имеют размер, не больший трех, и, следовательно, ихстоимость равна 0. Вводим хорду (i>3, 1^5) стоимостью 15.65 в минимальную триангуляцию. ПРис. 10.8. Шаблон просмотратаблицы при вычислении одкого элементаРис. 10.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
