最小化凸多边形三角剖分对角线总和的算法？
Algorithm to minimize sum of diagonals for triangulation of convex polygon?
将三角剖分的成本定义为已添加的对角线长度之和。给定一个凸多边形，其最便宜的三角剖分的成本是多少？如果我们把多边形看成一组n个坐标：v_1=x_1,y_1,...,v_n=x_n,y_n 并且解必须有 n-3 条对角线（不重叠，因为它是三角剖分）
我一直在尝试重现这个动态规划问题，但我似乎找不到一个好的问题。我真的不承认找到复发的次优结构。任何人都可以帮我解决这个问题吗？
最简单的方法就是遍历每个点，获取上一个点和下一个点之间的距离，并在没有当前点的情况下递归多边形；例如对于五边形 abcde 那将是：
- distance eb + 四边形递归 bcde
- distance ac + 四边形递归 cdea
- distance bd + 四边形递归 deab
- distance 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。所以检索存储的中间结果可能会有点复杂。
将三角剖分的成本定义为已添加的对角线长度之和。给定一个凸多边形，其最便宜的三角剖分的成本是多少？如果我们把多边形看成一组n个坐标：v_1=x_1,y_1,...,v_n=x_n,y_n 并且解必须有 n-3 条对角线（不重叠，因为它是三角剖分）
我一直在尝试重现这个动态规划问题，但我似乎找不到一个好的问题。我真的不承认找到复发的次优结构。任何人都可以帮我解决这个问题吗？
最简单的方法就是遍历每个点，获取上一个点和下一个点之间的距离，并在没有当前点的情况下递归多边形；例如对于五边形 abcde 那将是：
- distance eb + 四边形递归 bcde
- distance ac + 四边形递归 cdea
- distance bd + 四边形递归 deab
- distance 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。所以检索存储的中间结果可能会有点复杂。