用于凸多边形三角剖分的最小化对角线和算法？

Question

将一个多边形进行三角剖分，其代价为添加对角线长度的总和。给定一个凸多边形，其最便宜的三角剖分代价是多少？如果我们将该多边形视为n个坐标的集合：v_1=x_1,y_1,...,v_n=x_n,y_n，解决方案必须具有n-3条不重叠的对角线（因为它是三角剖分）。

我一直在尝试找到这个动态规划问题的递归公式，但似乎找不到一个好的。我无法识别出次优结构以找到递归。有人能帮我吗？

- John DIT

---

你能解释一下这与C++有什么关系吗？ - Sam Varshavchik

抱歉，我正在尝试使用C++找到解决方案，但我是新手，如果有人想为我尝试一下，C++更熟悉。 - John DIT

这是一个关于算法的问题。无论是用C++、Java、Python、Perl、PHP、Basic还是其他图灵完备的编程语言编写，答案都将是相同的。在你弄清楚算法是什么之后，尝试用C++编写解决方案，如果遇到了某些问题，那么这将成为一个C++问题。但在此之前不是。 - Sam Varshavchik

@SamVarshavchik 抱歉刚刚删除了它，感谢您提供的信息。 - John DIT

Answer 1

最简单的方法是迭代每个点，获取前一个点和下一个点之间的距离，并使用不包括当前点的多边形递归；例如对于五边形abcde，这将是：

• 距离eb + 用四边形bcde递归
• 距离ac + 用四边形cdea递归
• 距离bd + 用四边形deab递归
• 距离ce + 用四边形eabc递归
• 距离da + 用四边形abcd递归

为了避免重复计算相同的解，您应该舍弃任何已经被检查过的点没有对角线到达的解；例如，在第三步递归使用四边形deab时，拥有对角线eb的解是重复的，因为使用三角形abe的解已经在第一步中被检查过了。完全避免重复计算可能会在这种方法中变得复杂。

另一种方法是选择一个点（在下图中用红色表示），然后将每个解枚举为数字，其位数之和为n-2，其中n是点的数量。每条对角线都经过所选点的解决方案将是解决方案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。因此，检索存储的中间结果可能会变得有些复杂。

- m69 ''snarky and unwelcoming''

---

谢谢！我也在考虑第一种方法，但是像你说的那样，我在结果的检索方面遇到了困难。如果我找到解决方案，我会更新的。 - John DIT