《树型动态规划》PPT课件.ppt

《《树型动态规划》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《树型动态规划》PPT课件.ppt（32页珍藏版）》请在三一办公上搜索。

1、树型动态规划,长沙市雅礼中学 朱全民,加分二叉树,给定一个中序遍历为1,2,3,n的二叉树每个结点有一个权值定义二叉树的加分规则为：左子树的加分 右子树的加分根的分数若某个树缺少左子树或右子树，规定缺少的子树加分为1。构造符合条件的二叉树该树加分最大输出其前序遍历序列,样例中序遍历为1,2,3,4,5的二叉树有很多，下图是其中的三棵，其中第三棵加分最大，为145.,分析,性质：中序遍历是按“左-根-右”方式进行遍历二叉树，因此二叉树左孩子遍历序列一定在根结点的左边，右孩子遍历序列一定在根结点的右边！因此，假设二叉树的根结点为k，那么中序遍历为1,2,n的遍历序列，左孩子序列为1,2,k-1，右

2、孩子序列为k+1,k+2,n，如下图,动态规划,设f(i,j)中序遍历为i,i+1,j的二叉树的最大加分，则有：f(i,j)=maxfi,k-1*fk+1,j+dk显然 f(i,i)=di答案为f(1,n)1=i=k=j=n时间复杂度 O(n3)要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为i,i+1,j的二叉树的取最优决策时的根结点为k最后前序遍历这个树即可。,选课,给定M门课程，每门课程有一个学分要从M门课程中选择N门课程，使得学分总和最大其中选择课程必须满足以下条件：每门课程最多只有一门直接先修课要选择某门课程，必须先选修它的先修课M,N=500,分析,每门课程最

3、多只有1门直接先修课，如果我们把课程看成结点，也就是说每个结点最多只一个前驱结点。如果把前驱结点看成父结点，换句话说，每个结点只有一个父结点。显然具有这种结构的模型是树结构，要么是一棵树，要么是一个森林。这样，问题就转化为在一个M个结点的森林中选取N个结点，使得所选结点的权值之和最大。同时满足每次选取时，若选儿子结点，必选根结点的条件。,样例分析,如图1，为两棵树，我们可以虚拟一个结点，将这些树连接起来，那么森林就转会为了1棵树，选取结点时，从每个儿子出发进行选取。显然选M=4时，选3，2，7，6几门课程最优。,动态规划,如果我们单纯从树的角度考虑动态规划，设以i为根结点的树选j门课程所得到的

4、最大学分为f(i,j),设虚拟的树根编号为0，学分设为0，那么，ans=f(0,n+1)如果树根选择1门功课，剩下j-1门功课变成了给他所有儿子如何分配的资源的问题，这显然是背包问题。设前k个儿子选修了x门课程的最优值为g(k,x)，则有其中:0=x=j-1，ans=g(son(0),n+1),构造树结构,readln(n,m);inc(m);for i:=1 to n do 父亲表示法构造树 begin readln(pri,vi);pr是前驱结点，v价值 inc(tpri);t记录结点的儿子个数 nepri,tpri:=i;ne记录树 end;for i:=0 to n do ts记录每个

5、结点后代的个数 tsi:=tsi-1+ti+1;,procedure work(now:longint);inline;var i,j,k,bas:longint;begin for i:=1 to tnow do work(nenow,i);bas:=tsnow-1+1;for i:=bas+1 to bas+tnow do fi,j表示i子树内选j的最大价值 for j:=1 to m do begin gi,j是给每个节点分配的内部背包的空间 gi,j:=gi-1,j;i不选 for k:=1 to j do i选k门 if gi-1,j-k+fnenow,i-bas,kgi,j the

6、n begin gi,j:=gi-1,j-k+fnenow,i-bas,k;fai,j:=k;记录决策点 end;end;for i:=m downto 1 do计算fi,j fnow,i:=gtnow+bas,i-1+vnow;end;,进一步分析,上述状态方程，需要枚举每个结点的x个儿子，而且对每个儿子的选课选择，需要再进行递归处理。当然这样可以解决问题，那么我们还有没有其他方法呢？,转化为二叉树,如果该问题仅仅只是一棵二叉树，我们对儿子的分配就仅仅只需考虑左右孩子即可，问题就变得很简单了。因此我们试着将该问题转化为二叉树求解。图2就是对图1采用孩子兄弟表示法所得到的二叉树,动态规划,仔细

7、理解左右孩子的意义（如右图）：左孩子：原根结点的孩子右孩子：原根结点的兄弟也就是说，左孩子分配选课资源时，根结点必须要选修，而与右孩子无关。因此，我们设f(i,j)表示以i为根结点的二叉树分配j门课程的所获得的最大学分，则有，0=kjn,i(1.m)时间复杂度O(mn2),样例求解过程：初始f(i,0)=0f(6,1)=6,f(5,1)=max1,6=6,f(7,1)=2f(4,1)=max1,2=2,f(1,1)=max1,f(4,1)=2f(3,1)=4,f(2,1)=max1,4=4f(5,2)=7f(7,2)=maxf(5,1)+2=8f(4,2)=maxf(7,2),f(7,1)+1

8、=8 f(1,2)=maxf(4,2),f(4,1)+2=8f(2,2)=maxf(1,1)+1,f(3,1)+1)=5f(7,3)=9f(4,3)=maxf(7,2)+1,f(7,3)=9f(1,3)=maxf(4,2)+1,f(4,3)=9 f(2,3)=maxf(1,1)+f(3,1)+1,f(1,2)+1=9f(2,4)=maxf(1,3)+1,f(1,2)+f(3,1)+1=max9+1,8+4+1=13,/读入数据,转化为孩子兄弟表示 fin n m;scoren+1=0;brothern+1=0;/输入数据并转化为左儿子右兄弟表示法 for(int i=1;i a b;if(a=

9、0)a=n+1;scorei=b;brotheri=childa;childa=i;,void dfs(int i,int j)if(visitedij)return;visitedij=1;if(i=0|j=0)return;dfs(brotheri,j);/如果不选i，则转移到状态(brotheri,j)fij=fbrotherij;for(int k=0;k fij)fij=fbrotherik+fchildij-k-1+scorei;,通向自由的钥匙,通向自由的钥匙被放n个房间里这n个房间由n-1条走廊连接。每个房间里都有特别的保护魔法，在它的作用下，我无法通过这个房间，也无法取得其中

10、的钥匙。如果第i件房取消魔法需要耗费cost能量,并取得keys数量的钥匙。如果我拥有的能量为P，从号房间出发，我最多能取得多少钥匙？n=100，p,cost和keys都是整型。,分析样例,P=5可取,三间房的钥匙，消耗为+,获得的钥匙为+,分析,这n个房间由n-1条走廊连接，说明该问题的模型是一棵树也就是说，给出P的资源，如何在树中分配这些资源，得到最大值，即钥匙。这是典型的树型动态规划问题。将树转化为孩子兄弟表示法，由于根的左孩子还是它的孩子，右孩子是它的兄弟，因此：树根获取资源，则左右孩子均可获取资源树根不获取资源，则左孩子不能获取资源，右孩子可获取资源。,动态规划,设f(i,j)表示以

11、i为根结点的二叉树分配分配j的能量所获得的最多钥匙数，则有，初始：f(i,0)=0答案：f(1,P)时间复杂度为O(NP2),软件安装（2010河南省选）,有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。我们现在知道了软件之间的依赖关系：软件i依赖软件Di。一个软件

12、只能被安装一次，如果一个软件没有依赖则Di=0，这时只要这个软件安装了，它就能正常工作。现在请你设计出一种方案，安装价值尽量大的软件。,分析,由于软件存在先后约束关系，因此简单按软件先后顺序进行动态规划，会不符合无后效应原理，因此我们需要在进行动态规划前进行预处理。若安装软件i必须先安装j,则从i向j连一条有向弧，则软件的约束关系就构成了一个有向图。如下图：可以看出如果有k个制约关系，则有k条边，中间会存在环,分析,处理环：由于环为互为前提，要选择环中的一个必须都进行选择，因此可以将环缩成一个点，这个点为权值和价值为其他点的和。孤立点没有与其他点也没有任何关系，可以不管。如果把每个连通分量看成

13、一棵树，则图变成了为一个森林，图2。,树型动态规划,显然这个森林可以采用树型动态规划，先将它儿叉树。设f(i,j)表示以i为根结点的二叉树分配j资源的最大价值,警卫安排,一个有N个区域的树结构上需要安排若干个警卫；每个区域安排警卫所需要的费用是不同的；每个区域的警卫都可以望见其相邻的区域，只要一个区域被一个警卫望见或者是安排有警卫，这个区域就是安全的；任务：在确保所有区域都是安全的情况下，找到安排警卫的最小费用；0n=720；,分析样例该图有6个区域如图1，安排情况如图2，红色点为安排了警卫。2号警卫可以观察1，2，5，6；3号警卫可以观察1，3；4号警卫可以观察1，4；费用：16+5+4=2

14、5,分析,对于每个点i，都有3种状态分别为：要么在父亲结点安排警卫，即被父亲看到要么在儿子结点安排警卫，即被儿子看到要么安排警卫对于ii被父亲看到，这时i没有安排警卫，i的儿子要么安排警卫，要么被它的后代看到。i被儿子看到，即i的某个儿子安排了警卫，其他儿子需要安排警卫或者被它的后代看到。i安排了警卫，i的儿子可能还需要安排警卫，这样可能有更便易的方式照顾到它的后代；所以i的儿子结点被i看到，可能安排警卫，可能被它的后代看到。,动态规划,设f(i,0)表示i结点被父亲看到；f(i,1)表示i被它的儿子看到；f(i,2)表示在i安排警卫；则状态转移方程为：时间复杂度O(N2),procedure

15、 work(now:longint);var i,j,sum,tmp:longint;begin for i:=1 to tnow do work(wnow,i);/对每个儿子进行处理 fnow,0:=0;/以下处理now被父亲看到 for i:=1 to tnow do inc(fnow,0,fwnow,i,1);/now的儿子被儿子看到sum:=0;/以下处理在now被儿子看到的 for i:=1 to tnow do/now的儿子被儿子看到或者或安排警卫；inc(sum,min(fwnow,i,1,fwnow,i,2);fnow,1:=maxlongint;for i:=1 to tno

16、w do/枚举哪个儿子放警卫 begin tmp:=sum-min(fwnow,i,1,fwnow,i,2)+fwnow,i,2;fnow,1:=min(fnow,1,tmp);end;fnow,2:=cnow;/以下处理在now放置警卫 for i:=1 to tnow do Inc(fnow,2,min(min(fwnow,i,0,fwnow,i,1),fwnow,i,2);fnow,1:=min(fnow,1,fnow,2);1包含了2状态，取优值 end;,总结,树型动态规划有一个共性，那就是它的基本模型都是一棵树或者森林，为了考虑方便，一般情况下都将这个树或森林转化为二叉树，如下图，然后整个问题的最优只会涉及到左右孩子的最优，然后考虑根结点的情况，这样化简了问题，最终很容易写出状态转移方程，从而问题得到解决。另外，并不是所有的问题一定要转化为二叉树来解决，要仔细思考的就是每个结点有些什么状态，这些结点的状态与父、子结点的状态有什么联系，也就是如何由子结点的最优值推出父节点的最优值(即状态转移方程)。,