当前位置:首页 >> 学科竞赛 >> 线型动态规划000

线型动态规划000


线型动态规划

带权有向的多段图问题
? 给定一个带权的有向图,要求从点A到点D 的最短路径。

? ? ? ? ? ? ?

设F(i)表示从点A到达点i的最短距离,则有 F(A)=0 F(B1)=5,F(B2)=2 F(C1)=min{F(B1)+3}=8 F(C2)=min{F(B1)+2,F(B2)

+7}=7 F(C3)=min{F(B2)+4}=6 F(D)=min{F(C1)+4,F(C2)+3,F(C3)+5}=10

多阶段最优化决策问题
? 由上例可以看出,整个问题分成了A、B、C、D 四个阶段来做,每个阶段的数值的计算只会跟上 一个阶段的数值相关,这样一直递推下去直到目 标。 ? 即由初始状态开始,通过对中间阶段决策的选择 ,达到结束状态。这些决策形成了一个决策序列 ,同时确定了完成整个过程的一条最优的活动路 线。

概念
? ⑴状态(State):表示事物的性质,是描述“动态规划” 中的“单元”的量。亦是每一阶段求解过程的出发点。 ? ⑵阶段(Stage):阶段是一些性质相近,可以同时处理的 状态集合,或者说,阶段只是标识那些处理方法相同、处 理顺序无关的状态。 ? ⑶决策(Decision):每个阶段做出的某种选择性的行动, 是程序所需要完成的选择。 ? ⑷状态转移方程:是前一个阶段的状态转移到后一个的状 态的演变规律,是关于两个相邻阶段状态变化的方程,是 “动态规划”的中心。设 fk(i)—k阶段状态i的最优权值,即初始状态至状态i的最 优代价 fk+1(i)=min{fk(j)+u(i,j)}

动态规划的基本原理
?最优性原理
作为整个过程的最优策略,它满足:相对前面决策所形成 的状态而言,余下的子策略必然构成“最优子策略”。

?无后效性原则
给定某一阶段的状态,则在这一阶段以后过程的发展不受 这阶段以前各段状态的影响,所有各阶段都确定时,整个 过程也就确定了。这个性质意味着过程的历史只能通过当 前的状态去影响它的未来的发展,这个性质称为无后效性 。

? 拦截导弹问题(NOIP1999) ? 题目简介: ? 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹 能够到达任意的高度,但是以后每一发炮弹都不能高于前 一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该 系统还在试用阶段,所以只有一套系统,因此有可能不能 拦截所有的导弹。 ? 输入导弹依次飞来的高度(雷达给出的高度数据是不 大于30000 的正整数),计算这套系统最多能拦截多少导弹, 和如果要拦截所有导弹最少要配备多少套这种导弹拦截系 统。 ? 样例: ? input ? 389 207 155 300 299 170 158 65 ? output ? 6

? 解题思路: ? 本试题的实质是在一个数列中寻找递减的、未必连续的最 长子序列。对于这个问题,我们可以从n出发,依次反向 计算被拦截的导弹数。我们假设当导弹i作为被拦截导弹之 一时,F[i]为导弹i到导弹n序列中可以被拦截的最多导弹数。 对于F[i]的求解。我们可以这样考虑,对于所有导弹 j(i+1≤j≤n),如果满足导弹j的高度,则判断最大的F[j]值, F[i]就是最大的F[j]加上1,即: ? F[i]:=max(F[j]|导弹j的高度≤导弹i的高度)+1(i+1≤j≤n) ? 而一套系统能够拦截最多的导弹数best就是max(F[i]) (1≤i≤n)。对于这个例子,从动态规划算法的角度看,F[i] 是状态,公式F[i]:=max(F[j]|导弹j的高度≤导弹i的高度)+1 (i+1≤j≤n)就是状态转移方程。

? 部分参考程序段: ? best:=0; ? fillchar(f,sizeof(f),0); ? for i:=n downto 1 do ? begin ? f[i]:=1; ? for j:=i+1 to n do ? if (a[j]<=a[i])and(f[j]+1>f[i]) then ? f[i]:=f[j]+1; {a[i]为第i枚导弹的高度} ? if f[i]>best then best:=f[i]; ? end;

最长上升序列
? 设 有 整 数 序 列 b1,b2,b3,…,bm , 若 存 在 下 标 i1<i2<i3< …<in , 且 bi1<bi2<bi3< …<bin , 则 称 b1,b2,b3,…,bm 中 有 长 度 为 n 的 上 升 序 列 bi1 , bi2 ,bi3 ,…,bin 。 ? 求序列b1,b2,b3,…,bm中所有长度(n)最大上升子 序列 ? 输入:整数序列。 ? 输出:最大长度n和所有长度为n的序列个数。

分析
? 设f(i)为前i个数中的最长上升序列长度 , 则
? f(i)=max{f(j)+1} ? 边界为F(1)=1 (1<=j<i<=m, bj<bi)

分析
? ? ? ? ? 设t(i)为前i个数中最长序列的个数,则 t(i)=∑t(j) (1<=j<i<=m , bj<bi, f(i)=f(j+1) ) 初始为t(i)=1 当f(i)=n时,将t(i)累加 举例: 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2 答案:f=7时,边界为∑t=4

进一步
(3)求本质不同的最长序列个数有多少个? 如:1 2 3 4 6 5 8 10 9 有, 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8 9 都是本质不同的。 但对于 1 2 2 3 3 5 4 f:1 2 2 3 3 4 4 t: 1 1 1 2 2 4 4 答案有8个,其中4个1 2 3 5 ,4个1 2 3 4

改进算法
? 上例显然对于相个相同的数,重复算了多次因此, 我们对算法进行改进: ? 对原序列按b从小到大(当bi=bj时按F从大到小) 排序,增设Order(i)记录新序列中的i个数在原序 列中的位置。可见, ? 求 t(i) 时 , 当 f(j)=f(j+1),b(j)=b(j+1) 且 Order(j+1)<Order(i)时,便不累加t(j)。这样就 避免了重复。 ? 上述算法的时间复杂度为O(n2)

添括号问题
? 有一个由数字1,2,... ,9组成的数字串(长 度不超过200),问如何将M(M<=20)个加号("+") 插入到这个数字串中,使所形成的算术表达式 的值最小。请编一个程序解决这个问题。 ? 注意: ? 加号不能加在数字串的最前面或最末尾,也不 应有两个或两个以上的加号相邻。 ? M保证小于数字串的长度。 ? 例如:数字串79846,若需要加入两个加号,则 最佳方案为79+8+46,算术表达式的值133。

分 析
? 考虑到数据的规模超过了长整型,我们注意在解题过程中 采用高精度算法. ? 规划方程: ? F[I,J] = MIN { F[I-1,K] + NUM[K+1,J] } (I1<=K<=J-1) ? 边界值:F[0,I] := NUM[1,I] ; ? F[I,J]表示前J个数字中添上I个加号后得到的最小值。 ? NUM[I,J]表示数字串第I位到第J位的数 ? 上述问题的每一步,都只与上一步有关。因此可以采用 滚动数组 ? 程序的时间效率约为 20 * 200 * 200

演唱会
? 一场演唱会即将举行。现有N(O<N<=200)个 歌迷排队买票,一个人买一张,而售票处规定, 一个人每次最多只能买两张票。假设第I位歌迷 买一张票需要时间Ti(1〈=I〈=n),队伍中相 邻的两位歌迷(第j个人和第j+1个人)也可以由 其中一个人买两张票,而另一位就可以不用排 队了,则这两位歌迷买两张票的时间变为Rj, (假如Rj<Tj+Tj+1,则这样做就可以缩短后面歌迷 等待的时间,加快整个售票的进程 )。 ? 现给出N,Ti和Ri,求使每个人都买到票的最短 时间和方法。

分 析
? 设f(i)为前i个人花费最短时间 ? 于是有 f(i)=min{f(i-1)+Ti,f(i-2)+Ri-1}, ? 初始f(0)=0,f(1)=T1

青蛙过河(NOIP2005)
? 在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧 跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石 子上。由于桥的长度和青蛙一次跳过的距离都是正整数, 我们可以把独木桥上青蛙可能到达的点看成数轴上的一串 整点:0,1,……,L(其中L是桥的长度)。坐标为0的点 表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的 起点开始,不停的向终点方向跳跃。一次跳跃的距离是S 到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐 标为L的点时,就算青蛙已经跳出了独木桥。 ? 题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上 石子的位置。你的任务是确定青蛙要想过河,最少需要踩 到的石子数。

【输入文件】 ? 输入文件river.in的第一行有一个正整数L(1 <= L <= 109) ,表示独木桥的长度。第二行有三个正整数S,T,M,分 别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子 的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有 M个不同的正整数分别表示这M个石子在数轴上的位置( 数据保证桥的起点和终点处没有石子)。所有相邻的整数 之间用一个空格隔开。 【输出文件】 ? 输出文件river.out只包括一个整数,表示青蛙过河最少需 要踩到的石子数。 【样例输入】
10 235 23567

【样例输出】
2

【数据规模】
对于30%的数据,L <= 10000; 对于全部的数据,L <= 109。

分析
? 由于不能往回跳,很容易想到用动态规划解决这个题目。 ? 设f(i)表示跳到第i个点需要踩到的最少石子数,则很容易 写出动态规划的状态转移方程:

f ( 0) ? 0 ?{f(i - k)} (S ?? k ?? T) 第i点没有石子 f (i ) ? min ? ?{f(i - k)} ? 1 (S ?? k ?? T) 第i点有石子 Ans ? min{f(L), f(L ? 1),..., f(L ? T - 1)}
? 时间复杂度是O(L*(T-S)),但本题的L高达109,根本无 法承受!

进一步分析
? 我们先来考虑这样一个问题:长度为k的一段没有 石子的独木桥,判断是否存在一种跳法从一端正 好跳到另一端。 ? 若S<T,事实上对于某个可跳步长区间[S,T],必然 存在一个MaxK使得任何k>=MaxK,都可以从一端 正好跳到另一端。 ? 题设中1<=S<=T<=10,经过简单推导或者程序验证 就可以发现,取MaxK=100就能满足所有区间。

于是我们可以分两种情况讨论: 1. S=T时: 这时候由于每一步只能按固定步长跳,所以若第i个位置上 有石子并且i mod S=0那么这个石子就一定要被踩到。这是 我们只需要统计石子的位置中哪些是S的倍数即可。复杂 度O(M) 2. S<T时: 首先我们作如下处理:若存在某两个相邻石子之间的空白 区域长度>MaxK+2*T,我们就将这段区域缩短成长度为 MaxK+2*T。可以证明处理之后的最优值和原先的最优值相 同。
a b

如上图所示,白色点表示连续的一长段长度大于MaxK+2*T 的空地,黑色点表示石子。设原先的最优解中,白色段的第 一个被跳到的位置a,最后一个被跳到的位置是b,则在做压 缩处理之后,a和b的距离仍然大于MaxK,由上面的结论可 知,必存在一种跳法从a正好跳到b,而且不经过任何石子。

? 所以原来的最优解必然在处理之后的最优解 解集中。 ? 经过这样的压缩处理,独木桥的长度L’最多 为(M+1)*(MaxK+2*T)+M,大约12000左右。 压缩之后再用先前的动态规划求解,复杂度 就简化成了O(L’*(T-S)),已经可以在时限内出 解了。 ? 这样本题就得到了解决。

背包类动态规划问题

经典的背包问题(01背包)
? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车;

? 问选取装载哪些物品,使得卡车运送的 总价值最大?

搜索法
? 对于每种物品,要么装上卡车,要么不装,因此,N种 物品的装箱方案共有2N种。 ? 按每种物品进行搜索,方法如下: – 对第i种物品进行搜索 – 如果所有的物品都搜索完,则更新最优解 – 如果当前的估计达不到最优解,则回溯 – 如果第i种物品能放,则放,并标记,否则选下一个 物品 – 清除标记 – 回溯

动态规划
? 可以按每个物品进行规划,同样每种物品有选和 不选两种选择 ? 设F(i,j)表示前i件物品载重为j的最大效益,则有
? F (i ? 1, j ? w[i ]) ? C[i ], 第i种物品装载 F (i, j ) ? Max? ? F (i ? 1, j ), 第i种物品不装载

? ? ? ?

1<=i<=N, 0<=j<=N 初值:F(0,j)=0 F(N,M)即答案 显然时间复杂度为O(NM)

主程序如下
for i:=1 to m do f[0,i]:=0; //初始化 for i:=1 to n do f[i,0]:=0; for i:=1 to n do // 动态规划,递推求f for j:=1 to m do begin if j>=w[i] then //背包容量够大 f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j]) else //背包容量不足 f[i,j]:=f[i-1,j]; end;

满背包问题(01背包)
? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车;

? 问选取装载哪些物品,使得卡车开车正 好装满时,运送的总价值最大? 若无法装满卡车,则输出无解。

动态规划
? 设F(i,j)表示前i件物品背包为j的最大效益, 则有
? F (i ? 1, j ? w[i ]) ? C[i ], 第i种物品装载 F (i, j ) ? Max? ? F (i ? 1, j ), 第i种物品不装载

? ? ? ?

1<=i<=N, 0<=j<=N 初值:F(0,j)=0, F(1,j)= -∞ F(N,M)即答案 显然时间复杂度为O(NM)

带条件的背包问题(1)
? ? ? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 第i件物品可能带0~2个附件; 若装载附件,必须装载主件,反之没有约束; 现有一辆载重M公斤的卡车;

? 问选取装载哪些物品,使得卡车运送的总价值最 大?

分析
? 假设只有主件的情况 ,显然与经典背包问题完 全相同! ? 现在每个物品有附件,我们可以分成4种方案 – 仅装载主件 – 装载主件+第1个附件 – 装载主件+第2个附件 – 装载主件+2个附件 ? 由于上述4种并列,这是几种不同的决策同时规 划即可

动态规划
? 设F(i,j)表示前i件物品背包为j的最优解,则有,
? F (i ? 1, j ), 不选第i件物品 ? ? F (i ? 1, j ? w[i ]) ? c[i ],只选主件 ? F (i ? 1, j ? w[i ] - w[i1]) ? c[i ] ? c[i1], ? 1 ? // 选主件和第 件附件 F (i, j ) ? Max? ? F (i ? 1, j ? w[i ] - w[i 2]) ? c[i ] ? c[i 2], ? // 选主件和第2件附件 ? ? F (i ? 1, j ? w[i ] - w[i1] - w[i 2]) ? c[i ] ? c[i1] ? c[i 2], ? // 选主件和2件附件 ?

? 1<=i<=N, 0<=j<=M ? 时间复杂度O(NM)

多层背包问题
? ? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车; 第i件物品限制最多只能取Xi个;

? 问选取装载哪些物品,使得卡车运送的总 价值最大?

分析
? 我们可以类似01背包问题,将第i种物品拆分成 x[i]个,这样每个物品只有1件了,如下图:

? 然后对所有的物品采用动态规划即可。 ? F(i,j)=max{ f(i-1,j-k*w[i]) + k*c[i] } ? 0<=k*w[i]<=j

完全背包问题
? ? ? ? ? 有N件物品; 第i件物品Wi公斤; 第i件物品价值Ci元; 现有一辆载重M公斤的卡车; 每次可以选取某种物品的任意多件装载;

? 问选取装载哪些物品,使得卡车运送的总 价值最大?

分析
? 类似多层背包问题将每个物品展开成X[i ]=m/w[i]个,然 后对所有的物品采用动态规划即可。 ? 若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品i去掉, 不用考虑。这个优化的正确性显然:任何情况下都可将 价值小费用高的i换成物美价廉的j,得到至少不会更差的 方案。 ? 由于每种物品有选和不选两种情况,可以将每种物品的 2k个当成一个整体考虑。这样对于某种物品要选取多个 ,都可以由若干个2k个物品进行组合 (即2进制数)。例如 第i种物品要选10个,则10=23+21 。 ? 这样第i种物品的个数为k=㏒2 (m/wi)物品,是一个很大 的改进。 ? 进一步, 在计算k时, K =㏒2 (j/wi), j为当前背包剩余空间。

进一步
for i:=1 to n do // 动态规划,递推求f for j:=1 to m do begin if j>=w[i] then //背包容量够大 f[i,j]:=max(f[i,j-w[i]]+c[i],f[i-1,j]) else //背包容量不足 f[i,j]:=f[i-1,j]; end;

改进程序
? 事实上,我们只关心剩余背包的最大值,也就是 仅仅关心f(j),因此,在对f(j)更新时,只要背包容 量可以,那么可以反复更新。程序如下: for i:=1 to n do // 动态规划,递推求f for j:=0 to m do begin if j>=w[i] then //背包容量够大 f[j]:=max(f[j-w[i]]+c[i],f[j]) end;

思考题1:机器分配
? ? ? ? M台设备,分给N个公司。 若公司i获得j台设备,则能产生Aij效益 问如何分配设备使得总效益最大? M<=15,N<=10。

分析
? 用机器数来做状态,数组f(i,j)表示前i个公 司分配j台机器的最大盈利。则状态转移方 程为: ? f(i,j) =Max{f[i-1,k] + a[i,j-j]} (1<=i<=N,1<=j<=M,0<=k<=j ) ? 初始值: f(0,0)=0 ? 时间复杂度O(N*M2)

思考题2:硬币找零
?给定N枚硬币 ?给定T元钱 ?用这N枚硬币找这T元钱,使得剩下的钱最 少。
?剩下钱数最少的找零方案中的所需的最少 硬币数。 ?N<=500,T<=10000.

分析
?设F[i]表示需要找的钱数为i时所需要的最少 钱币数。显然有: ?F[i]=Min{F[ i - A[j] ] + 1} { i≤ T,1≤j≤N} ?初始值:F[0]=0。 ?A[j]表示其中 第j种钱币的面值。 ?时间复杂度为O(N*T)。

思考题3:系统可靠性
? 一个系统由若干部件串联而成,只要有一个部件 故障,系统就不能正常运行,为提高系统的可靠 性,每一部件都装有备用件,一旦原部件故障, 备用件就自动进入系统。显然备用件越多,系统 可靠性越高,但费用也越大,那么在一定总费用 限制下,系统的最高可靠性等于多少? ? 给定一些系统备用件的单价Ck,以及当用Mk个此 备用件时部件的正常工作概率Pk(Mk),总费用 上限C。求系统可能的最高可靠性。

样例
输入文件格式:
第一行:n C 第二行:C1 P1(0) ) … 第n 行:Cn Pn(0) )

P1(1) … P1(X1) (0<=X1<=[C/Ck] Pn(1) … Pn(Xn) (0<=Xn<=[C/Cn]

输入:2 20 3 0.6 0.65 0.7 0.75 0.8 5 0.7 0.75 0.8 0.9 0.95 输出:0.6375=0.75*0.85

0.85

0.9

分析
? 设f(i,j)表示将j的资金用到前i项备用件 中去的最大可靠性,则有 F(i,j)= max{F(i-1,j–k*Cost[i])*P[i,k]} ? 0<=i<=n, 0<=j<=C,0<=k<j div Cost(i) ? 初始: F(0,0)=1 ? 目标: F(n,C) ? 时间复杂度:O(k*n*C),这里k是常数因子 ,与数据相关

总结
? 对于资源类动态规划问题,我们可以看出,问题描述必须 有一个基本要素:资源,有时这种资源可能是金钱、空间 或者时间,问题就是要对这些资源如何分配,一种基本的 想法是将资源应用于前i个阶段,然后考虑第i个阶段和前i1个阶段之间的关系。 ? 设前i个点的消耗j的资源得到的最优值,研究前i-1个点消 耗的资源的最优值,利用第i个点决策转移,如下图。

? 状态转移方程一般可写成: fi(j) = min{ fi-1 ( k) + ui (j,k)}

区间类动态规划

整数划分
? ? ? ? ? 给出一个长度为n的数 要在其中加m-1个乘号,分成m段 这m段的乘积之和最大 m<n<=20 有T组数据,T<=10000

贪心法
? 尽可能平均分配各段,这样最终的数值将会尽可能大。但 有反例。如191919分成3段 19*19*19=6859 但191*91*9=156429,显然乘积更大。

? 将一个数分成若干段乘积后比该数小,因为输入数不超过 20位,因此不需高精度运算。 ? 证明: – 假设AB分成A和B,且A,B<10,则有 – AB=10*A+B>A*B(相当于B个A相加) – 同理可证明A,B为任意位也成立

动态规划
? 可以先预处理出原数第i到j段的数值A[i,j]是多少, 这样转移就方便了,预处理也要尽量降低复杂度。 ? F[i,j]表示把这个数前i位分成j段得到的最大乘积。 ? F[i,j]=max{F[k,j-1]*A[k+1,i]} ? 1<k<i<=n, j<=m ? 时间复杂度为O[m2n] ? 由于有10000组数据,因此估计时间复杂度为 10000*203=8*107 ? 至于说输出,记录转移的父亲就可以了。

石子合并
? 在一园形操场四周摆放N堆石子(N≤100); ? 现要将石子有次序地合并成一堆; ? 规定每次只能选相临的两堆合并成一堆,并将新的 一堆的石子数,记为该次合并的得分。 1. 选择一种合并石子的方案,使得做N-1次合并, 得分的总和最少 2. 选择一种合并石子的方案,使得做N-1次合并, 得分的总和最大

示例

贪心法
N=5 石子数分别为3 4 6 5 4 2。
用贪心法的合并过程如下: 第一次 3 4 6 5 4 2得分 5 第二次 5 4 6 5 4得分9 第三次 9 6 5 4得分9 第四次 9 6 9得分15 第五次 15 9得分24 第六次24 总分:62 显然,贪心法是错误的。 然而有更好的方案: 第一次3 4 6 5 4 2得分 7 第二次7 6 5 4 2得分13 第三次13 5 4 2得分6 第四次13 5 6得分11 第五次 13 11得分24 第六次24 总分:61

分析
? ? ? ? 假设只有2堆石子,显然只有1种合并方案 如果有3堆石子,则有2种合并方案,((1,2),3)和(1,(2,3)) 如果有k堆石子呢? 不管怎么合并,总之最后总会归结为2堆,如果我们把最 后两堆分开,左边和右边无论怎么合并,都必须满足最优 合并方案,整个问题才能得到最优解。如下图:

动态规划
? 设t[i,j]表示从第i堆到第j堆石子数总和。 Fmax(i,j)表示将从第i堆石子合并到第j堆石子的最大的得分 Fmin(i,j)表示将从第i堆石子合并到第j堆石子的最小的得分
F max( i, j ) ? max {F max( i, k ) ? F max( k ? 1, j ) ? t[i, j ]}

同理,

i ? k ? j ?1

F min( i, j ) ? min {F min( i, k ) ? F min( k ? 1, j ) ? t[i, j ]}
i ?k ? j ?1

? Fmax[i,i] = 0,Fmin[i,i] = 0 ? 时间复杂度为O(n3)

优化
? 由于石子堆是一个圈,因此我们可以枚举分开的位置,首 先将这个圈转化为链,因此总的时间复杂度为O(n4)。 ? 这样显然很高,其实我们可以将这条链延长2倍,扩展成 2n-1堆,其中第1堆与n+1堆完全相同,第i堆与n+i堆完全 相同,这样我们只要对这2n堆动态规划后,枚举 f(1,n),f(2,n+1),…,f(n,2n-1)取最优值即可即可。 ? 时间复杂度为O(8n3),如下图:

凸多边形的三角剖分
? ? ? ? 给定由N顶点组成的凸多边形 每个顶点具有权值 将凸N边形剖分成N-2个三角形 求N-2个三角形顶点权值乘积之和最小?

? 样例

上述凸五边形分成△123 , △135, △345 三角形顶点权值乘积之和为: 121*122*123+121*123*231+123*245*231= 12214884

分析
? 性质:一个凸多边形剖分一个三角形后,可以将 凸多边形剖分成三个部分: ?一个三角形 ?二个凸多边形(图2可以看成另一个凸多边形 为0)

动态规划
? 如果我们按顺时针将顶点编号,则可以相邻两个顶点描 述一个凸多边形。 ? 设f(i,j)表示i~j这一段连续顶点的多边形划分后最小乘积 ? 枚举点k,i、j和k相连成基本三角形,并把原多边形划分 成两个子多边形,则有 ? f(i,j)=min{f(i,k)+f(k,j)+a[i]*a[j]*a[k]} ? 1<=i<k<j<=n ? 时间复杂度O(n3)

讨论
?为什么可以不考虑这种情况?

? 可以看出图1和图2是等价的,也就是说如果 存在图1的剖分方案,则可以转化成图2的剖 分方案,因此可以不考虑图1的这种情形。

总结
? 该类问题的基本特征是能将问题分解成为两两合并的形式 。解决方法是对整个问题设最优值,枚举合并点,将问题 分解成为左右两个部分,最后将左右两个部分的最优值进 行合并得到原问题的最优值。有点类似分治的解题思想。 ? 设前i到j的最优值,枚举剖分(合并)点,将(i,j)分成左右 两区间,分别求左右两边最优值,如下图。

? 状态转移方程的一般形式如下: F(i,j)=Max{F(i,k)+F(k+1,j)+决策,k为划分点


更多相关文档:
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com