Алгоритм минимизации суммы диагоналей для триангуляции выпуклого многоугольника?

Question

Определите стоимость триангуляции как сумму длин добавленных диагоналей. Учитывая выпуклый многоугольник, какова стоимость его самой дешевой триангуляции? Если мы рассматриваем многоугольник как набор из n координат: v_1 = x_1, y_1, ..., v_n = x_n, y_n, и решение должно иметь n-3 диагоналей (не перекрывающихся, потому что это триангуляция)

Я был пытаясь получить повторение этой проблемы динамического программирования, но я не могу найти хороший. Я не признаю субоптимальную структуру, чтобы найти повторение. Кто-нибудь может дать мне руку на это?

Answer 1

Простейший способ - перебирать каждую точку, получать расстояние между предыдущей и следующей точками и рекурсивно с полигоном без текущей точки; например для пятиугольника ABCDE, который был бы:

• расстояния ЕВА + рекурсия с четырехугольником BCDE
• расстояние переменного током + рекурсией с четырехугольником cdea
• расстояние о.-д. + Recurse с четырьмя лунками deab
• расстояние с + рекурсия с четырехугольником eabc
• расстояние да + рекурсия с четырехугольником ABCD

Для того, чтобы не вычислять то же решение более чем один раз, вы должны отбрасывать любые решения, в которых точки, которые уже были проверены, не имеют диагонали, входящей в них; например при рекурсии с четырехугольником deab на этапе 3 решение с диагональю eb является дубликатом, поскольку решения, которые используют треугольник abe, уже были проверены на первом этапе. Выполнение дублирующих расчетов вообще может быть затруднено с помощью этого метода.

Другой метод бы выбрать точку (обозначена красным на рисунке), а затем перечислить каждое решение в виде числа цифр, сумма которых составляет п - 2, где п есть число точек. Решение, в котором каждая диагональ проходит через выбранную точку, будет решением 11111. Затем вы выполняете каждую комбинацию, которая суммируется с n - 2: 11111, 1112, 1121, 113, 1211, 122, 131, 14, 2111, 212 , 221, 23, 311, 32, 41 и 5. Число больше 1 означает, что вы объединяете 2 или более сегментов и добавляете диагональ от первой до последней. Когда число больше 2, эта диагональ граничит с левым полигоном (обозначается розовым), с которым вы рекурсивете.

Анимация показывает итерации и рекурсии, которые алгоритм проходит для 7-точечного многоугольника, вплоть до точки, где он повторяется с 6-точечным многоугольником.

Оба эти методы дают возможности запоминания и подведение итогов, но это не будет просто. Пятиугольник, начинающийся в точке b, не обязательно bcdef после того, как вы начали рекурсию; это может быть bdfhj. Поэтому получение сохраненных промежуточных результатов может немного усложниться.