将一个多边形进行三角剖分,其代价为添加对角线长度的总和。给定一个凸多边形,其最便宜的三角剖分代价是多少?如果我们将该多边形视为n个坐标的集合:v_1=x_1,y_1,...,v_n=x_n,y_n,解决方案必须具有n-3条不重叠的对角线(因为它是三角剖分)。我一直在尝试找到这个动态规划问题的递归公式,但似乎找不到一个好的。我无法识别出次优结构以找到递归。有人能帮我吗?
最简单的方法是迭代每个点,获取前一个点和下一个点之间的距离,并使用不包括当前点的多边形递归;例如对于五边形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。因此,检索存储的中间结果可能会变得有些复杂。