Триангуляция выпуклого многоугольника формируется путем рисования диагоналей между несмежными вершинами (углами) так, что диагонали никогда не пересекаются. Задача состоит в том, чтобы найти стоимость триангуляции с минимальными затратами. Стоимость триангуляции — это сумма весов составляющих ее треугольников. Вес каждого треугольника является его периметром (сумма длин всех сторон)
Смотрите следующий пример, взятый из этого источника.
Две триангуляции одного и того же выпуклого пятиугольника. Триангуляция слева имеет стоимость 8 + 2√2 + 2√5 (примерно 15.30), а справа — 4 + 2√2 + 4√5 (примерно 15.77).
Эта проблема имеет рекурсивную подструктуру. Идея состоит в том, чтобы разделить многоугольник на три части: один треугольник, подполигон слева и подполигон справа. Мы пробуем все возможные деления, подобные этому, и находим тот, который минимизирует стоимость треугольника плюс стоимость триангуляции двух подполигонов.
Let Minimum Cost of triangulation of vertices from i to j be minCost(i, j) If j <= i + 2 Then minCost(i, j) = 0 Else minCost(i, j) = Min { minCost(i, k) + minCost(k, j) + cost(i, k, j) } Here k varies from 'i+1' to 'j-1' Cost of a triangle formed by edges (i, j), (j, k) and (k, i) is cost(i, j, k) = dist(i, j) + dist(j, k) + dist(k, i)
Следующее — реализация C ++ вышеупомянутой наивной рекурсивной формулы.
|
Выход:
15.3006
Вышеуказанная проблема аналогична умножению матрицы . Ниже приведено дерево рекурсии для mTC (points [], 0, 4).
В приведенном выше дереве рекурсии легко увидеть, что проблема имеет много перекрывающихся подзадач. Поскольку проблема имеет оба свойства: оптимальная подструктура и перекрывающиеся подзадачи , ее можно эффективно решить с помощью динамического программирования.
Ниже приводится реализация C ++ решения для динамического программирования.
|
Выход:
15.3006
Временная сложность приведенного выше решения динамического программирования составляет O (n 3 ).
Обратите внимание, что в приведенных выше реализациях предполагается, что точки многоугольника covnvex заданы по порядку (по часовой стрелке или против часовой стрелки)
Упражнение:
Расширьте вышеупомянутое решение для печати триангуляции также. Для приведенного выше примера оптимальной триангуляцией является 0 3 4, 0 1 3 и 1 2 3.
Источники:
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture12.html
http://www.cs.utoronto.ca/~heap/Courses/270F02/A4/chains/node2.html
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме
Рекомендуемые посты:
- Минимальная площадь многоугольника с учетом трех точек
- Минимальная нечетная стоимость пути в матрице
- Минимальная стоимость для заполнения данного веса в сумке
- Минимальная стоимость, чтобы сделать две строки одинаковыми
- Найти минимальную стоимость настройки массива
- Минимальная стоимость разбиения заданной двоичной строки
- Минимальная стоимость для покупки N килограммов сладкого для M человек
- Минимальная стоимость, чтобы сформировать число X, складывая полномочия 2
- Минимальные затраты для достижения точки N от 0 при двух разных разрешенных операциях
- Минимальная стоимость, чтобы подняться по лестнице, поднимаясь по лестнице
- Минимальная стоимость, чтобы сделать две числовые строки одинаковыми
- Минимальная стоимость освобождения строки от подпоследовательности
- Найдите минимальную стоимость, чтобы добраться до места назначения на поезде
- Минимальная стоимость, чтобы сделать две строки идентичными, удалив цифры
- Минимальная стоимость создания самой длинной общей подпоследовательности длины k
0.00 (0%) 0 votes