凸多边形的三角形剖分

凸多边形的三角形剖分是将凸多边形分割成互不相交的三角形的弦的集合。最优三角剖分是指根据定义在三角形上的权函数，确定凸多边形的三角剖分，使得诸三角形的权值和最小。这里的权值和指的是将多边形划分成多个三角形后，所有三角形的边权值之和。

通过将凸多边形划分成不同的两部分和一个三角形，凸多边形的三角形剖分可以类比矩阵链的递推方程。将凸多边形划分成两个不同的子链，这两个子链所构成的矩阵乘法次数可以对应到三角剖分中的权值和。

给定一个n边的凸多边形P，我们需要确定该凸多边形的三角剖分，使得诸三角形的权值和最小。输入数据中给出了各边弦的权值，以无向图的形式表示。三角形的权值等于三条边的权值之和。因此，我们需要根据这些权值来计算最优的三角剖分。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [凸多边形的最优三角划分最详细求解步骤演示[动态规划]](https://blog.csdn.net/liuweiyuxiang/article/details/78827474)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [7-3 凸多边形最优三角剖分 (10 分)(思路+详解+分析题意+动态规划)Come Baby！！！！！！！！！](https://blog.csdn.net/qq_48508278/article/details/120457414)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]