algorithm - 最小化凸多边形三角剖分的对角线总和的算法？

Question

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

我一直试图让这个动态编程问题再次出现，但我似乎找不到一个好的问题。我并没有真正认识到次优结构来找到复发。任何人都可以帮我解决这个问题吗？

Answer 1

最简单的方法是遍历每个点，获取前一个点和下一个点之间的距离，并在没有当前点的情况下使用多边形进行递归；例如，对于五边形abcde，它将是：

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

为了不重复计算相同的解决方案，您应该丢弃已经检查的点没有对角线到达的任何解决方案；例如，在步骤 3 中使用四边形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。所以检索存储的中间结果可能会有点复杂。