(a) (b)
图1 一个凸多边形的2个不同的三角剖分
在凸多边形P的一个三角剖分T中，各弦互不相交且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角刮分中，恰好有n-3条弦和n-2个三角形。
凸多边形最优三角剖分的问题是：给定一个凸多边形P=<v0，v1，…，vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数ω。例如：定义ω(△vivjvk)=| vivj |+| vivk |+| vkvj |，其中，| vivj |是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。
（1）最优子结构性质
凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸（n+1）边形P=<v0，v1 ，…，vn>的一个最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和，即三角形v0vkvn的权，子多边形<v0，v1，…，vk>的权和<vk，vk+1，…，vn>的权之和。可以断言由T所确定的这两个子多边形的三角剖分也是最优的，因为若有<v0，v1，…，vk>或<vk，vk+1，…，vn>的更小权的三角剖分，将会导致T不是最优三角剖分的矛盾。
（2）最优三角剖分对应的权的递归结构
首先，定义t[i，j]（1≤i<j≤n）为凸子多边形<vi-1，vi，…，vj>的最优三角剖分所对应的权值，即最优值。为方便起见，设退化的多边形<vi-1，vi>具有权值0。据此定义，要计算的凸（n+1）边多边形P对应的权的最优值为t[1，n]。
t[i，j]的值可以利用最优子结构性质递归地计算。由于退化的2顶点多边形的权值为0，所以t[i，i]=0，i=1，2，…，n 。当j一i≥1时，子多边形<vi-1，vi，…，vj>至少有3个顶点。由最优于结构性质，t[i，j]的值应为t[i，k]的值加上t[k+1，j]的值，再加上△vi-1vkvj的权值，并在i≤k≤j-1的范围内取最小。由此，t[i，j]可递归地定义为：

（3）计算最优值
下面描述的计算凸（n+1）边形P=<v0，v1，…，vn>的三角剖分最优权值的动态规划算法MINIMUM_WEIGHT，输入是凸多边形P=<v0，v1，…，vn>的权函数ω，输出是最优值t[i，j]和使得t[i，k]+t[k+1，j]+ω（△vi-1vkvj）达到最优的位置（k=）s[i，j]，1≤i≤j≤n 。
Procedure MINIMUM_WEIGHT(P，w)；
Begin
n=length[p]-1;
for i=1 to n do t[i,i]:=0;
for ll=2 to n do
for i=1 to n-ll+1 do
begin
j=i+ll-1;
t[i,j]=∞;
for k=i to j-1 do
begin
q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
if q<t[i,j] then
begin
t[i,j]=q;
s[i,j]=k;
end;
end;
end;
return(t,s);
end;
算法MINIMUM_WEIGHT_占用θ(n2)空间，耗时θ(n3)。
（4）构造最优三角剖分
如我们所看到的，对于任意的1≤i≤j≤n ，算法MINIMUM_WEIGHT在计算每一个子多边形<vi-1，vi，…，vj>的最优三角剖分所对应的权值t[i，j]的同时，还在s[i，j]中记录了此最优三角剖分中与边（或弦）vi-1vj构成的三角形的第三个顶点的位置。因此，利用最优子结构性质并借助于s[i，j]，1≤i≤j≤n ，凸（n+l）边形P=<v0，v1，…，vn>的最优三角剖分可容易地在Ο(n)时间内构造出来。

习题：
1、汽车加油问题：
设有路程长度为L公里的公路上，分布着m个加油站，它们的位置分别为p[i]（i=1，2，……，m），而汽车油箱加满油后（油箱最多可以加油k升），可以行驶n公里。设计一个方案，使汽车经过此公路的加油次数尽量少（汽车出发时是加满油的）。
2、最短路径：
设有一个网络，要求从某个顶点出发到其他顶点的最短路径
3、跳马问题：
在8*8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
4、二叉树的遍历
5、背包问题
6、用分治法实现两个大整数相乘
7、设x1，x2，…，xn是直线上的n个点，若要用单位长度的闭区间去覆盖这n个点，至少需要多少个这样的单位闭区间？
8、用关系“＜”和“＝”将3个数A、B和C依次排列时，有13种不同的序关系：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要将n个数依序进行排列，试设计一个动态规划算法，计算出有多少钟不同的序关系。
9、有一种单人玩的游戏：设有n(2<=n<=200)堆薄片，各堆顺序用0至 n-1编号，极端情况，有的堆可能没有薄片。在游戏过程中，一次移动只能取某堆上的若干张薄片，移到该堆的相邻堆上。如指定
I堆k张 k 移到I-1(I>0)堆，和将k 张薄片移至I+1(I<n-1)堆。所以当有两个堆与 I 堆相邻 时，I堆原先至少有2k 张薄片；只有一个堆与 I 堆相邻 时， I 堆原先至少有k张薄片。
游戏的目标是对给定的堆数，和各堆上的薄片数，按上述规则移动薄片，最终使 各堆的薄片数相同。为了使移动次数较少些，移动哪一堆薄片，和移多少薄片先作以下估算：
设
ci:I堆的薄片数(0<=I<n,0<=ci<=200);
v：每堆 的平均薄片数；
ai:I堆的相邻堆可以从I堆得到的薄片数。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
这里并不希望准确地求出A0 至an-1，而是作以下处理：若令 a0 为0，能按上述算式计算出 A1至 an-1。程序找出 a 中的最小值，并让全部a值减去这最小值，使每堆移去的薄片数大于等于0。
实际操作采用以下贪心策略：
（1）每次从第一堆出发顺序搜索每一堆，若发现可从 I堆移走薄片，就完成一次移动。即， I堆的相邻堆从 I堆取走 ai片薄片。可从I 堆移薄片到相邻堆取于 I堆薄片数：若I 堆是处于两端位置( I=0 I=n-1), 要求 ci>=ai ；若 I堆是中间堆，则要求ci>=2ai。
（2）因在ai>0的所有堆中，薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数也最多。在用策略（1）搜索移动时，当发生没有满足条

此新闻共有11页 上一页 1 2 3 4 5 6 7 8 9 10 11 下一页