凸多边形最优三角剖分
一凸8边形P的顶点顺时针为{v1,v2,… ,v8},任意两顶点间的线段的权重由矩阵D给出。
若vi与vj是P上不相邻的两个顶点,则线段vivj 称为P的一条弦。求P的一个弦的集合T,使得T中所有的弦恰好将P 分割成互不重迭的三角形,且各三角形的权重之和为最小(一个三角形的权重是其各边的权重之和)。
/*
int graph[][]={
{0, 14, 25, 27, 10, 11, 24, 16},
{14, 0, 18, 15, 27, 28, 16, 14},
{25, 18, 0, 19, 14, 19, 16, 10},
{27, 15, 19, 0, 22, 23, 15, 14},
{10, 27, 14, 22, 0, 14, 13, 20},
{11, 28, 19, 23, 14, 0, 15, 18},
{24, 16, 16, 15, 13, 15, 0, 27},
{16, 14, 10, 14, 20, 18, 27, 0}
};*/
解答:题目中顶点坐标编号从1开始,为了方便编程,将顶点从0开始,顶点的编号变为0到7。定义t[i][j],0=<i<j<n为凸多边形{Vi,Vi,…Vj}的最优三角剖分所对应的权函数值,退化的两点多边形{Vi,Vi+1}的权值为0。要计算凸n边形的最优权值为t[0][n-1]。
由于退化的两点多边形{Vi,Vi+1}的权值为0,t[i][i]=0。最优子结构的性质,t[i][j]的值是t[i][k]的值加上t[k][j]的值,再加上三角形ViVkVj的权值,其中,i<k<=j-1。K的位置有j-i-1个。因此可以在这j-i-1个未知中选出使t[i][j]值达到最小的位置,递归式为: t[i][j]=0 (j-i<=1)
t[i][j]=t[i][k]+t[k][j]+w(i,k,j) (j-i>=2)
public class TestTriangulation{
int t[][];
int s[][];
int graph[][];
int n;
public TestTriangulation(int n,int[][] graph){
this.n=n;
this.graph=graph;
t=new int[n][n];
s=new int[n][n];
}
private int w(int m, int n, int p){
return graph[m][n] + graph[m][p] + graph[n][p];
}
private void sp(int m, int n)//输出最优剖分需要添加的线段
{
if (n-m<=2)
return;
if(s[m][n]-m>=2){
System.out.printf("V%d-V%d\n", m, s[m][n]);
sp(m, s[m][n]);
}
if (n-s[m][n]>=2){
System.out.printf("V%d-V%d\n", s[m][n], n);
sp(s[m][n], n);
}
}
public int minWeight(){
int j, u;
for (int r=2; r<=n-1; r++)
for (int i=0; i<n-r; i++){
j = i + r;
t[i][j] =t[i][i+1] + t[i+1][j] +w(i, i+1, j);
s[i][j] = i+1;
for (int k=i+2; k<i+r; k++){
u = t[i][k] + t[k][j] + w(i, k, j);
if (u<t[i][j]){
t[i][j] = u;
s[i][j] = k;
}
}
}
return t[0][n-1];
}
public static void main(String args[]){
/*
int graph[][]={
{0, 14, 25, 27, 10, 11, 24, 16},
{14, 0, 18, 15, 27, 28, 16, 14},
{25, 18, 0, 19, 14, 19, 16, 10},
{27, 15, 19, 0, 22, 23, 15, 14},
{10, 27, 14, 22, 0, 14, 13, 20},
{11, 28, 19, 23, 14, 0, 15, 18},
{24, 16, 16, 15, 13, 15, 0, 27},
{16, 14, 10, 14, 20, 18, 27, 0}
};*/
int[][] graph = { { 0, 2, 2, 3, 1, 4 }, { 2, 0, 1, 5, 2, 3 }, { 2, 1, 0, 2, 1, 4 },
{ 3, 5, 2, 0, 6, 2 }, { 1, 2, 1, 6, 0, 1 }, { 4, 3, 4, 2, 1, 0 } };
TestTriangulation tri=new TestTriangulation(6,graph);
System.out.printf("最优剖分总权值\n");
System.out.printf("%d\n",tri.minWeight());
System.out.printf("剖分时添加的线段\n");
tri.sp(0,5);
}
}
运行:
C:\java>java TestTriangulation
最优剖分总权值
24
剖分时添加的线段
V0-V4
V1-V4
V2-V4
- 大小: 5.7 KB
- 大小: 7.5 KB
分享到:
相关推荐
标题 "动态规划算法学习十例之八" 暗示了我们将探讨动态规划这一重要的算法概念,特别是通过一个具体的例子——Matrix Chain Multiplication(矩阵链乘法)来深入理解。动态规划是一种解决复杂问题的有效方法,它...
在这个“动态规划算法学习十例之七”的主题中,我们将聚焦于一个具体的动态规划问题——最长公共子序列(Longest Common Subsequence,简称LCS)。这个问题在计算机科学中具有很高的实用价值,尤其是在比较和分析...
在这个“动态规划算法学习十例之九”的主题中,我们将聚焦于如何通过DP来解决实际问题。尽管描述部分没有提供具体的实例,但从标题来看,我们可以推测这是一个关于动态规划应用的系列教程的第九个例子。 动态规划的...
在这个主题“动态规划算法学习十例之六”中,我们将探讨如何利用动态规划方法来解决实际问题。博文链接虽然未提供具体内容,但我们可以根据提供的文件名推测讨论的是一个具体的编程实例。 `Main.java`通常是一个...
标题中的“动态规划算法学习十例之五”表明这篇内容主要关注的是计算机科学中的动态规划算法,这是一种在解决复杂问题时非常有效的优化方法。动态规划通常用于处理具有重叠子问题和最优子结构的问题,通过将大问题...
在这个“动态规划算法学习十例之四”的主题中,我们将专注于背包问题的解决方案。背包问题是一个经典的计算机科学问题,它通常涉及在给定容量的背包中选择物品以最大化总价值。 首先,我们来了解动态规划的基本思想...
在这个"动态规划算法学习十例之二"中,我们很可能会探讨两个具体的动态规划应用:一个可能涉及二项式系数计算,另一个可能是斐波那契数列的求解。下面,我们将深入这两个主题,理解它们背后的动态规划策略。 首先,...
在这个“动态规划算法学习十例之一”的主题中,我们将会探讨动态规划的基本概念和一个具体的实例,通过分析`Test.java`源码来深入理解。 首先,动态规划的核心思想是将一个大问题分解为相互重叠的小问题,并通过...
动态规划是一种重要的算法思想,广泛应用于解决复杂问题的优化,如最短路径、背包问题、最长公共子序列等。在本篇文章中,我们将探讨动态规划的精髓,并通过具体实例进行深入学习。博客链接提供了详细的解析,虽然...
在压缩包中的"近似串匹配问题"文件可能包含了这样的C语言实现,可以作为学习和理解近似串匹配动态规划算法的一个实例。 总结一下,近似串匹配的动态规划算法是一种高效的方法,通过Levenshtein距离或Hamming距离...
三:图论、动态规划算法、综合题专集》是一本专门针对编程竞赛中的重要算法与问题解决策略的书籍。它涵盖了图论、动态规划以及综合题型,这些都是在竞赛中经常遇到并且至关重要的主题。下面将对这三个方面进行详细的...
在课程设计过程中,学生还将学习如何分析动态规划算法的时间复杂度和空间复杂度。例如,大多数动态规划解决方案的时间复杂度为O(n*W),其中n是物品数量,W是背包容量,而空间复杂度通常是O(n*W)或者更优,取决于是否...
在实际编程中,理解和掌握动态规划算法对于提高问题解决能力至关重要,因为它能够优雅地处理复杂度高且具有结构重叠的优化问题。在学习动态规划时,推荐阅读如《Introduction to Algorithms》等经典教材,它们深入浅...
标题中提到的是“算法参考资料国际大学生程序设计竞赛例题解3 图论·动态规划算法·综合题专集”。这份资料集中的标题揭示了内容的几个关键点,即它是一份专门为解决算法问题而编写的参考资料,特别针对国际大学生...
动态规划算法是一种强大的工具,常用于解决多阶段决策过程中的最优化问题。它通过将复杂问题分解成相互关联的子问题来求解,避免了贪婪算法或分治算法可能遇到的局限。动态规划的核心思想是备忘录法,即保存子问题的...
**算法动态规划专题** 动态规划(Dynamic Programming,简称DP)是一种在计算机科学中解决最优化问题的算法技术,尤其在解决复杂度较高的多阶段决策问题时表现得尤为出色。它通过将大问题分解为小问题,并存储子...
动态规划算法通常包含以下几个步骤: 1. 定义状态:识别问题中的关键状态,它们通常是问题的某个阶段的特性描述。 2. 状态转移方程:建立从一个状态到下一个状态的转换规则,这个方程描述了如何根据先前的状态计算...
"基于岭回归机器学习算法的项目成本预测研究——以A风景园林规划研究院规划设计项目为例.pdf" 本文研究主要集中在基于岭回归机器学习算法的项目成本预测研究,以A风景园林规划研究院规划设计项目为例。该研究的目的...
本资源包含的100例算法涵盖了排序、搜索、图论、动态规划、递归等多个重要类别。 1. **排序算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法是数据处理的基础,用于将一组无序的...