Коротко о задаче: дан выпуклый n‑угольник с вершинами пронумерованными по часовой (или против) по кругу $1,\dots ,n$. Требуется выбрать $n-3$ непересекающихся диагоналей (триангуляция), минимизирующих сумму длин выбранных диагоналей $\sum |d|$.
1) Динамическое программирование (точно, корректно, полиномиально)
- Обозначения. Пусть $L(u,v)$ — евклидова длина хорды (или $0$, если $(u,v)$ — сторона исходного многоугольника). Зафиксируем порядок вершин по границе. Для $i<j$ определим $dp[i][j]$ как минимальная суммарная длина диагоналей внутри выпуклого многоугольника, образованного вершинами $i,i+1,\dots ,j$, при условии, что $(i,j)$ считается границей (то есть его длина не включается).
- Базовый случай:
$$dp[i][i+1]=0\text{(отрезок из двух соседних вершин — нет области для диагоналей).}$$
- Рекуррент: для $j\ge i+2$ $$dp[i][j]=\underset{k=i+1,\dots ,j-1}{\min }(dp[i][k]+dp[k][j]+\mathrm{add}(i,k)+\mathrm{add}(k,j)),$$ где
$$\mathrm{add}(u,v)=\{\begin{array}{ll}0,& \text{если}v=u+1(\text{или}(u,v)\text{— сторона исходного n-угольника}),\\ L(u,v),& \text{иначе.}\end{array}$$ (Индексы могут рассматриваться по модулю $n$ при циклической нумерации.)
- Корректность (индуктивное обоснование). В любой оптимальной триангуляции для подсегмента границы $(i,j)$ существует вершина $k$ такая, что треугольник $(i,k,j)$ принадлежит триангуляции. Разрезая триангуляцию по этому треугольнику, задача распадается на две независимые подзадачи для интервалов $[i,k]$ и $[k,j]$, причём суммарная длина диагоналей равна сумме оптимумов подзадач плюс длины новых диагоналей $(i,k)$ и $(k,j)$, если они не сторона. Следовательно, оптимальный выбор $k$ даёт рекуррентную формулу, и DP по индукции даёт оптимальное значение для любого $[i,j]$.
- Сложность: наивная реализация по двум индексам и перебору $k$ даёт $O(n^3)$ времени и $O(n^2)$ памяти. (В практических реализациях можно сократить константы; возможны ускорения при дополнительных свойствах, но общая гарантированная асимптотика — $O(n^3)$.)
2) Жадные алгоритмы
- Идея простейшего жадного алгоритма: последовательно добавлять наименьшую по длине диагональ, которая не пересекает уже выбранные; продолжать, пока не будет добавлено $n-3$ диагоналей.
- Плюсы: очень простые, обычно быстрые (поддержка кандидатов в куче даёт $O(n^2\log n)$ или лучше на практике).
- Минусы и корректность: жадный алгоритм в общем случае НЕ даёт оптимального решения. Существуют простые контрпримеры (минимальная степень контрпримера — $n=6$): жадность может выбрать одну или две очень короткие диагонали, которые перекроют пространство и приведут к необходимости добавить длинные диагонали в дальнейшем, тогда как хорошая (оптимальная) триангуляция могла отказаться от этих коротких диагоналей, заменив их двумя средними, получив меньшую суммарную длину. Следовательно, жадьный алгоритм не обладает общей корректностью для задачи минимизации суммы длин диагоналей.
(Можно продемонстрировать конкретный числовой контрпример для шести вершин — он стандартен в литературе по комб. оптимизации триангуляций.)
3) Геометрические подходы / эвристики
- Триангуляция по одному центру (fan): зафиксировать вершину $v$ и провести диагонали от $v$ ко всем несмежным вершинам; это даёт триангуляцию с суммой длин ${\sum }_{u:u\text{не сосед}v}L(v,u)$. Можно перебрать все $v$ и выбрать лучший фан за $O(n^2)$. Это простой эвристический метод, но он не гарантирует оптимум (иногда оптимум — не фан).
- Delaunay‑триангуляция (по кругам): для заданного множества точек Delaunay оптимизирует углы, но не минимизирует сумму длин диагоналей. На многих наборах точек Delaunay даёт хорошую (иногда близкую к оптимальной) триангуляцию, но нет общей гарантии оптимальности для нашей цели.
- Остальные геометрические эвристики: локальные улучшения (edge‑flip) — начать с любой триангуляции и выполнять операции замены диагонали в выпуклом четырехугольнике, если это улучшает суммарную длину. Алгоритм локального улучшения (hill‑climbing) часто достигает локального минимума; комбинируя с различными начальными триангуляциями можно приближаться к глобальному оптимуму. Эти методы практичны и быстры, но теоретической гарантии на глобальный оптимум нет.
4) Сравнение и рекомендации
- Точность: DP — единственный из перечисленных методов с доказанной оптимальностью для выпуклого n‑угольника. Жадный и геометрические эвристики не гарантируют оптимум (существуют контрпримеры).
- Сложность: DP — $O(n^3)$ время, $O(n^2)$ память. Жадный и большинство геометрических эвристик — как правило быстрее ($O(n^2\log n)$ или лучше на практике), фан — $O(n^2)$, Delaunay можно получить за $O(n\log n)$ (но требует алгоритма для триангуляции по окружностям).
- Практика: если нужен точный оптимум и $n$ до нескольких тысяч (зависит от машинного времени), используйте DP (возможно с оптимизациями/параллелизацией). Если $n$ очень велико и допустима эвристика — используйте Delaunay + локальные улучшения (edge‑flip) или перебор лучших «fan» + локальные улучшения.
5) Доказательство корректности DP (кратко, формально)
- Пусть $T^{\ast }$ — любая оптимальная триангуляция для вершин $i,\dots ,j$ с границей $(i,j)$. Тогда в $T^{\ast }$ существует вершина $k\in \{i+1,\dots ,j-1\}$ такая, что треугольник $(i,k,j)\in T^{\ast }$. Разделив $T^{\ast }$ по этому треугольнику получим две триангуляции оптимальные для подинтервалов $[i,k]$ и $[k,j]$ (иначе можно было бы улучшить $T^{\ast }$). Поэтому сумма длин в $T^{\ast }$ равна
$$dp[i][k]+dp[k][j]+\mathrm{add}(i,k)+\mathrm{add}(k,j).$$ Минимизация по всем возможным $k$ даёт формулу рекуррентного соотношения. По индукции на длину интервала рекуррент даёт оптимальный $dp[i][j]$. Это завершает доказательство корректности.
Итого: для выпуклого n‑угольника точный полиномиальный (и корректный) алгоритм — динамическое программирование с рекуррентом выше ($O(n^3)$). Жадные и многие геометрические методы быстрее на практике, но без общей гарантии оптимальности; их можно использовать как приближённые или начальные решения для дальнейшей локальной оптимизации.