Структуры данных и алгоритмы (1021739), страница 73
Текст из файла (страница 73)
Если бывесь алгоритм сводился именно к такой последовательности действий, мы бы получили в результате алгоритм с экспоненциальным временем выполнения.Но зачастую удается получить лишь полиномиальное число подзадач и поэтому туили иную подзадачу приходится решать многократно. Если бы вместо этого мы отслеживали решения каждой решенной подзадачи и просто отыскивали в случае необходимости соответствующее решение, мы бы получили алгоритм с полиномиальным временем выполнения.С точки зрения реализации иногда бывает проще создать таблицу решений всехподзадач, которые нам когда-либо придется решать.
Мы заполняем эту таблицу независимо от того, нужна ли нам на самом деле конкретная подзадача для полученияобщего решения. Заполнение таблицы подзадач для получения решения определен-280ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВной задачи получило название динамического программирования (это название происходит из теории управления).1Формы алгоритма динамического программирования могут быть разными — общей их "темой" является лишь заполняемая таблица и порядок заполнения ее элементов.
Соответствующие методы проиллюстрируем на основе двух примеров: вычисление шансов на победу команд в спортивных турнирах и решение так называемой "задачи триангуляции".Вероятность победы в спортивных турнирахДопустим, две команды Аи В проводят между собой турнир.
Победителем считаетсятот, кто первым выиграет п матчей. Можно предположить, что силы команд А и Б примерно равны, т.е. у каждой из них есть 50% шансов выиграть очередной матч. Допустим,P(i, j) — вероятность того, что если А для победы нужно провести i матчей, а В — j матчей, то в конечном счете победу на турнире одержит А.
Например, если в турнире"Мировой серии" команда Dodgers выиграла два матча, а команда Yankees — один, тоi = 2, j = 3 и оказывается (мы в этом еще убедимся), что Р(2, 3) равняется 11/16.Чтобы вычислить P(i, j), можно воспользоваться рекуррентным уравнением сдвумя переменными. Во-первых, если i = 0 и j > 0, то команда А уже выигралатурнир, поэтому Р(0, j) = 1.
Аналогично, P(i, 0) = 0 для i > 0. Если как i, так и jбольше нуля, командам придется провести по крайней мере еще один матч с равными шансами выиграть эту игру. Таким образом, P(i, j) должно быть среднимзначением P(i - 1, j) и P(l, j - 1), первое из этих выражений представляет собойвероятность того, что команда А выиграет турнир, если победит в следующем матче, а второе — вероятность того, что команда А выиграет турнир, даже если проиграет следующий матч. Итак, получаем, следующие рекуррентные соотношения:P(i,j) = 1, если i = 0 и у > О,P(i,j) = 0, если i > 0 и у = О,P(i,j) = (P(i ~ 1,У) + P(i,j ~ 1))/2, если i > Ои у > 0.(10.4)На основании соотношений (10.4) можно показать, что вычисление P(i, у) требуетвремени не больше, чем О(2'+1). Обозначим через Т(п) максимальное время, котороетребуется для вычисления P(i, j ) , где i + у = п.
Тогда из (10.4) следуетТ(1) = с ,Т(п) = 2Т(п -l) + d,для некоторых констант с и d. Читатель может проверить (воспользовавшись средствами, обсуждавшимися в предыдущей главе), что Т(п) < 2""'с + (2"-1 -l)d, что соответствует О(2") или O(2i+y).Таким образом, мы установили экспоненциальную верхнюю границу времени,требуемого для рекурсивных вычислений P(i, j ) . Но если мы хотим убедиться в том,что рекуррентная формула для P(i, j) — не самый лучший способ вычисления этойвероятности, надо найти нижнюю границу времени вычисления. В качестве упражнения рекомендуем читателям показать, что при вычислении P(i, j) общее количествовычислений вероятностей Р с меньшими значениями i и у, которые приходится выполнять, равняется C'itj, т.е.
числу способов выбрать i элементов из i + j. Если i — j,1Динамическим программированием (в наиболее общей форме) называют процесс пошагового решения задач, когда на каждом шаге выбирается одно решение из множества допустимых (на этом шаге) решений, причем такое, которое оптимизирует заданную целевую функциюили функцию критерия. (В приведенных далее примерах процесс пошагового решения задачисводится к пошаговому заполнению таблиц.) В основе теории динамического программирования лежит принцип оптимальности Бсллмана.
Более подробно о теории динамического программирования см. [7]. — Прим. ред.10.2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ281это число равно П(2"/-7п), где га = i + у. Таким образом, Т(п) равняется Q(2"/Vra), и,по существу, мы можем показать, что оно также равняется О(2"/л/га) • В то время как2"/V/j растет медленнее, чем 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), то все остальные элементы таблицыРис. 10.4.
Шаблон вычисленийпредставляют собой средние значения элементов,находящихся снизу и справа от соответствующегоэлемента. Таким образом, таблицу следует заполнять начиная с ее нижнего правогоугла и продвигаться вверх и влево вдоль диагоналей, представляющих элементы спостоянным значением i + j, как показано на рис. 10.4. Соответствующая программаприведена в листинге 10.2 (предполагается, что она работает с двумерным массивомР подходящего размера).Таблица 10.1. Таблица вероятностей1/221/3213/1615/16111/321/211/167/813/165/161/23/411/161/81/41/21000043210<- JЛистинг 10.2. Вычисление вероятностей,;/,function odds ( i, j: integer ) : real;vars, k: integer;begin(1)for s:= 1 to i + j do begin{ вычисление элементов массива Р,сумма индексов которых равняется s(2)P[0,s]:= 1.0;(3)P[s,0]:= 0.0;282ГЛАВА 10.
МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВfor k:= 1 to s - 1 doP [ k , s-k]:= (P(k-l, s-k] + P ( k , s-k-l])/2.0(4)(5)end;return(P[i, j ] )end; { odds }(6)Анализ функции odds (шансы) не представляет особых затруднений. Цикл, включающий строки (4), (5), занимает O(s) времени, которое превосходит время О(1) длястрок (2), (3). Таким образом, выполнение внешнего цикла занимает время О(]Г" ^s)2или О(п ), где п = i + j. Следовательно, вычисления по методу динамического про2граммирования требуют времени О(п ), тогда как в "прямолинейном" подходе к вычислениям необходимо время порядка О(2"/л/га).
Поскольку величина 2"/Ч/л растет2намного быстрее, чем п , динамическое программирование предпочтительнее как вданном случае, так практически в любых других обстоятельствах..Задача триангуляцииВ качестве еще одного примера динамического программирования рассмотримзадачу триангуляции многоугольника. Заданы вершины многоугольника и расстояния между каждой парой вершин. Это расстояние может быть обычным евклидовым расстоянием на плоскости или произвольной функцией стоимости, задаваемой в виде таблицы. Задача заключается в том, чтобы выбрать такую совокупность хорд (линий между несмежными вершинами), что никакие две хорды небудут пересекаться, а весь многоугольник будет поделен на треугольники.
Общаядлина выбранных хорд должна быть минимальной. Такая совокупность хорд называется минимальной триангуляцией.Пример 10.1. На рис. 10.5 показан многоугольник с семью сторонами, (х, у) —координаты его вершин. Расстояния вычисляются как обычное евклидово расстояние.
Триангуляция, оказавшаяся не минимальной, изображена пунктирными линиями. Ее стоимостью является сумма длин хорд (i>0> v2), (DO. 1>з)> (УО. v5) и (и3, v5),или >/82 + 162 + Vl5 2 +16 2 + л/222 + 22 + >/72 + 142 = 77.56 . П(8,26)(0,20) (i/Лj^(15,26)/\( vA (27,21)(22,12)(10,0)Рис. 10.5. Многоугольник и его триангуляция10.2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ283Задача триангуляции, представляющая интерес сама по себе, имеет к тому же рядполезных применений. Например, в статье [40] использовали обобщение задачи триангуляции для следующей цели. Рассмотрим задачу создания двумерной тени объекта, поверхность которого определяется совокупностью точек в трехмерном пространстве.
Свет на объект падает из неподвижного источника, и яркость любой точки наповерхности зависит от углов между направлением света, положением наблюдателя иперпендикуляром (нормалью) к поверхности в этой точке. Чтобы определить нормальк поверхности в какой-либо точке, надо найти минимальную триангуляцию точек,определяющих эту поверхность.Каждый треугольник определяет некоторую плоскость в трехмерном пространстве, и, поскольку ищется минимальная триангуляция, можно предположить, что этитреугольники будут очень малы.
Нетрудно определить направление нормали к плоскости, что позволяет вычислить интенсивность освещения для точек каждого треугольника. Если эти треугольники недостаточно малы, то, чтобы избежать резкихперепадов в интенсивности освещения, общую картину можно улучшить путем локального усреднения.Прежде чем продолжить решение задачи триангуляции с помощью динамического программирования, необходимо зафиксировать два факта относительно триангуляции. Они помогут разработать требуемый алгоритм. Предполагаем, что наш многоугольник имеет п вершин v0, Vi, ...
UB_I, перечисленных по часовой стрелке.Факт 1. В случае триангуляции любого многоугольника, содержащего более трехвершин, с каждой парой смежных вершин связана по крайней мере одна хорда. Чтобы убедиться в этом, допустим, что ни vt, ни vl+il не связаны ни с какой из хорд. Втаком случае область, ограничиваемая стороной (vit vi+i), должна была бы включатьстороны (t)(_i, Vf), (Vi+i, vi+2) и по крайней мере еще одну дополнительную сторону илихорду.
В таком случае эта область не была бы треугольником.Факт 2. Если (vit vt) является хордой в триангуляции, значит, должна найтисьтакая вершина и*, что каждая из линий (i>,-, vk) и (vk, v,) должна быть либо стороноймногоугольника, либо хордой. В противном случае хорда (u f , Vj) ограничивала бы область, не являющуюся треугольником.Чтобы приступить к поиску минимальной триангуляции, выберем две смежныевершины, например VQ и y t . Из указанных выше фактов следует, что в любой триангуляции (и, следовательно, в минимальной триангуляции) должна найтись такаявершина vk, что (иг, иь) и (vk, v0) являются хордами или сторонами многоугольника.Необходимо рассмотреть, насколько приемлемую триангуляцию можно построитьпосле выбора каждого возможного значения k.
Если в многоугольнике п вершин, внашем распоряжении имеется (л — 2) возможных вариантов.Каждый вариант выбора k приводит к не более чем двум подзадачам, где мы имеем многоугольники, образованные одной хордой и сторонами исходного многоугольника. Например, на рис. 10.6 показаны две подзадачи, которые возникают в случае,если выбрана вершина va.Далее нужно найти минимальную триангуляцию для многоугольников, показанных на рис.
10.6,а и 10.6,6. Можно, например, рассмотреть все хорды, исходящие издвух смежных вершин. Тогда, решая задачу, показанную на рис. 10.6,6, мы должны,в частности, рассмотреть вариант хорды (из, vs), которая порождает подзадачу с многоугольником (VQ, v3, v6, ve), две стороны которого (и0> и3) и (и3, Us) являются хордамиисходного многоугольника. Этот подход приводит к алгоритму с экспоненциальнымвременем выполнения..Но, имея треугольник, включающий хорду (v0, vk), нам никогда не придется рассматривать многоугольники, у которых более одной стороны являются хордами исходного многоугольника. "Факт 2" говорит о том, что при минимальной триангуляции хорда в подзадаче (например, хорда (v0, v3) на рис. 10.6,6) должна составлятьтреугольник с одной из остальных вершин многоугольника.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
