凸多边形的动态规划问题_凸多边形求最小权

作者：我家小花儿 | 2024-06-04 05:21:17

踩

凸多边形求最小权

问题描述：

用凸（n+1）多边形顶点的逆时针序列表示凸多边形，即p={v0，v1，…..，vn}，如下图所示：

给定凸多边形p={v0，v1，…..，vn-1}，以及定义在由多边形的边和弦组成的三角形上的权函数为w。要求确定该凸多边形的三角剖分中三角形上权之和为最小。

思路：

我们定义一个t[i][j],1<=i<=j<=N,为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值。且t[i][i] = {vi-1,vi}表示相连的两个点，则设置为0，如果j-i>=1，则都能表示成一个子凸多边形。

则：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/670541