6
第4-3课：凸多边形最优三角剖分问题
source link: https://blog.csdn.net/orbit/article/details/108729359
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
凸多边形上的最优三角剖分问题也是动态规划经典题目，此类问题基本上都是在一个给定的凸多边形上规划三角形分割，使得剖分后得到的一系列三角形的某种结果最优，比如三角形的面积之和最大（或最小），或者是三角形的各边权重之和最大（或最小）等。这一课，我们要介绍的题目是要求根据三角形的权重之和最小来剖分多边形，结合这个题目，希望大家能够掌握如何分析此类问题，并用动态规划的方法设计出求解此类问题的算法实现。
子问题的定义
如图（1）所示，把一个凸多边形分割成多个三角形有多种剖分形式，根据题目给出的条件，每种分割方法得到的三角形的权重之和也各不相同。用动态规划方法解决算法问题，首先要确定子问题和各决策阶段状态的定义，然后给出最优子结构的性质。每个决策阶段的状态，实际上就是子问题在这个决策阶段的解，这个阶段的最优解一般是根据最优子结构的性质由之前各阶段的解和当前的最优决策堆叠出来。因此，用动态规划法解决算法问题的关键是识别出子问题并给出决策状态的定义。
图（1）多边形分割示意图
在第4-1课：如何理解动态规划法中介绍了一种分析定义子问题的方法，就是确定问题的规模，通过缩小问题规模的方式确定子问题，这里不妨应用一下。
<Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK