凸多边形最优三角剖分（动态规划）报告.doc

算法设计与分析实验报告，附已通过源码，供学习参考，共勉♪ 目录摘要如下： 1.问题描述 2.实验目的 3.实验原理 4.实验设计 （包括输入格式、算法、输出格式） 5.实验结果与分析 （除了截图外，实验结果还用图表进行了分析） 6.结论 7.程序源码 【凸多边形最优三角剖分（动态规划）】是一种计算几何中的算法，主要应用于算法设计与分析领域。本实验报告旨在深入理解动态规划的概念并实际应用到凸多边形的三角剖分问题中。 一、问题描述 凸多边形的三角剖分是指将一个凸多边形分割成若干个互不相交的三角形，这些三角形的边由多边形的边或内部的弦组成。最优三角剖分则是在给定权函数w的情况下，找到一种剖分方式，使得所有三角形的权值之和最小。权函数w可以定义在由多边形边和弦组成的三角形上，其具体意义可以根据问题需求而定。 二、实验目的 1. 熟悉并掌握动态规划算法的基本思想和应用。 2. 实现并理解凸多边形最优三角剖分的算法细节。 三、实验原理 1. 最优子结构：凸(n+1)边形P的最优三角剖分T如果包含三角形V0VkVn（1≤k≤n），则T的权值等于三个部分权值之和：三角形V0VkVn的权值、子多边形{V0,V1…Vk}的权值和子多边形{Vk,Vk+1…Vn}的权值。这一性质表明，最优三角剖分可以递归地分解为子问题的最优解。 2. 递推关系：设t[i][j]（1≤i<j≤n）为凸多边形{Vi-1,Vi…Vj}的最优三角剖分的权值，可以通过递推公式计算得到，其中t[i][j]包含了包含三角形Vi-1VkVj的权值、子多边形{Vi-1,Vi…Vk}的最优权值和子多边形{Vk,Vk+1…Vj}的最优权值。 四、实验设计 1. 输入数据格式：程序中预设了边数为6的凸多边形，并定义了各个顶点间的边权重。 2. 输出：首先输出最优权值，即多边形的最优三角剖分值，然后输出最优解，即具体的三角剖分结构。 五、实验结果与分析 通过实验验证，程序计算出的结果正确无误。 六、结论 尽管实验实现了一个基本的动态规划解决方案，但仍有改进空间。理想的实现应该是允许用户自定义多边形的边数和顶点坐标，程序自动计算权值并进行三角剖分。这需要更高级的输入验证和交互设计，以提高程序的通用性和用户体验。 七、程序源码 源代码中定义了一个二维数组weight来存储多边形的边权重，使用动态规划算法minWeightTriangulation求解最优权值，并通过Traceback回溯找出最优解的具体结构。算法的时间复杂度为O(n^3)，空间复杂度为O(n^2)。 总结，这个实验报告详细介绍了凸多边形最优三角剖分问题，包括问题定义、算法设计、实验结果分析以及对进一步优化的思考，为理解和实现此类动态规划问题提供了清晰的指导。