Строение оптимальной триангуляции

Докажем последнее утверждение. Пусть Г - оптимальная триангуляция (га + 1)-угольника Р = (vo, v\,..., vn). Ребро vqvu входит в один из треугольников триангуляции. Пусть это треугольник AvoVkVn, где 1 k га - 1. Тогда вес триангуляции Г равен весу AvoVkVn плюс сумма весов триангуляции многоугольников (г>о, v\,..., Vk) и (vk, Vk+i,..., vn). Следовательно, триангуляции указанных многоугольников обязаны быть оптимальными, и если оптимальные стоимости для таких многоугольников (при разных к) уже вычислены, то остаётся выбрать оптимальное значение к.

Рекуррентная формула

Другими словами, имеет место следующая рекуррентная формула. Пусть m[i,j] - вес оптимальной триангуляции многоугольника Vi,..., Vj), где 1 г < j га. Вес оптимальной триангуляции всего многоугольника равен т[1, га]. Будем считать, что «двуугольники» (vi i,Vi) имеют вес 0. Тогда m[i, i] = 0 для г = 1,2,..., га. Если j - г 1, то у многоугольникаvi, , vj) имеется не

менее трёх вершин, и нам необходимо найти минимум (по всем к из промежутка г к j - 1) такой суммы: вес Avj-ivvj, плюс вес оптимальной триангуляцииvi, •, vk), плюс вес оптимальной

триангуляции (v, Vk+i,..., Vj). Поэтому

Единственное отличие этой формулы от формулы (16.2) - более общий вид весовой функции. Стало быть, алгоритм Матшх-Chain-Order с указанными выше изменениями вычисляет вес оптимальной триангуляции; время работы 0(га3), объём используемой памяти 0(га2).

Упражнения

16.4-1 Докажите, что всякая триангуляция выпуклого га-угольника разбивает его на га - 2 треугольника с помощью га - 3 диагоналей.

16.4-2 Профессор предполагает, что для случая, когда вес треугольника равен его площади, алгоритм нахождения оптимальной триангуляции можно упростить. Не обманывает ли его интуиция?

min {m[i, к] + m[k + + w(Avi iVkVj)} при г < j.

при г = j,

(16.7)

16.4-3 Пусть весовая функция определена на множестве диагоналей многоугольника, и триангуляция считается оптимальной, если сумма весов входящих в неё диагоналей минимальна. Как свести эту задачу к разобранной нами (в которой веса приписывались не диагоналям, а треугольникам)?

16.4-4 Найдите оптимальную триангуляцию правильного восьмиугольника на евклидовой плоскости для случая, если весом треугольника считается его периметр.

Задачи

16-1 Битоническая евклидова задача коммивояжёра

Евклидова задача коммивояжёра (euclidean traveling-salesman problem) состоит в нахождении кратчайшего замкнутого пути, соединяющего данные га точек на плоскости (см. пример на рис. 16.6а, где га = 7). Эта задача является NP-полной, так что вряд ли её можно решить за полиномиальное время (см. главу 36).

Дж. Бентли предложил упростить задачу, рассматривая только битонические пути (bitonic tours), т.е. пути, начинающиеся в крайней левой точке, затем идущие слева направо до крайней правой точки, а затем возвращающиеся справа налево в исходную точку. (На рис. 16.66 изображён кратчайший битонический путь через те же семь точек). Эта задача проще: постройте алгоритм решения этой задачи, требующий времени О (га2). Вы можете считать, что абсциссы всех точек различны. (Указание: просматривая точки слева направо, храните для текущей точки X и для всех предыдущих точек У длину кратчайшего пути, битонически соединяющего X с У с проходом через крайнюю левую точку.)

Рис. 16.6 Семь точек на плоскости в узлах единичной решётки, (а) Кратчайший замкнутый путь (длины и 24,88), обходящий эти точки. Этот путь не является битоническим. (б) Кратчайший битонический путь, обходящий те же точки, длина и 25,58.

Задачи к главе 16

329

16-2 Разбиение абзаца на строки

Абзац текста состоит из п слов длиной /i,/2,...,/га (длина слова - число символов в нём). Считая, что все символы имеют равную ширину (как на пишущей машинке), мы хотим оптимальным образом разбить его на строки длиной не более М символов. Оптимальность при этом определяется так: посчитаем число «лишних» пробелов в каждой строке (то есть посмотрим, на сколько длина строки меньше М, если между словами ставить по одному пробелу) и сложим кубы этих чисел для всех строк, кроме последней: чем больше эта сумма, тем хуже абзац. Используя динамическое программирование, разработайте алгоритм оптимального разбиения абзаца на строки; оцените время его работы и требуемый объём памяти.

16-3 Стоимость редактирования

Мы хотим преобразовать строку символов х[1. .то] в новую строку у[1..га] с помощью следующих операций: перенос символа из исходной строки в новую, перенос двух соседних символов из исходной строки в новую с одновременной их перестановкой («транспозиция»), добавление символа (справа) к новой строке, удаление первого символа из старой строки, замена (удаление символа из исходной строки и добавление другого символа в новую строку), наконец, удаление остатка старой строки.

Вот, например, как с помощью этих операций преобразовать строку algorithm в строку altruistic:

ОперацияНовая строка Старая строка

перенос aalgorithm

перенос 1algorithm

замена g на taltorithm

удаление оaltrithm

перенос raltrithm

добавление ualtruithm

добавление ialtruiithm

добавление saltruisithm

транспозиция it в ti altruistihm

добавление сaltruistichm

удаление остаткаaltruistic

Каждой из операций («перенос», «транспозиция», «добавление», «удаление», «замена» и «удаление остатка») приписана стоимость (мы предполагаем, что стоимость замены меньше, чем суммарная стоимость добавления и удаления, иначе замена была бы лишней).