树状动态规划幻灯片.ppt-得力文库

资源描述

《树状动态规划幻灯片.ppt》由会员分享，可在线阅读，更多相关《树状动态规划幻灯片.ppt（34页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

2、求解方法千变万化。要面临的实际问题千奇百怪、数据模型千姿百态，求解方法千变万化。要求选手求选手“阵而后战，兵法之常，运用之妙，存乎一心阵而后战，兵法之常，运用之妙，存乎一心”。竞竞赛赛数据数据结构结构数学分数学分析析动态程动态程序设计序设计搜索搜索网络流网络流累计累计NOIP2338NOI21216CSOI121116IOI4116累计累计9763126第2页，共34页，编辑于2022年，星期六知知识识点点回回顾顾|是一个是一个“多阶段最优化决策的过程多阶段最优化决策的过程”。即由初始状态开。即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些始，通过对中间阶段决策的选择，达到结束状

3、态。这些决策形成了一个决策序列，同时确定了完成整个过程的决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线一条最优的活动路线。状态状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。阶段阶段（Stage）：阶段是一些性质相近，可以同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。第3页，共34页，编辑于2022年，星期六知知识识点点回回顾顾决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状

4、态变化的方程，是“动态规划”的中心。设：fk(i)k阶段状态i的最优权值，即初始状态至状态i的最优代价：fk+1(i)=minxk(j)+u(i,j)|DP应该包含状态、阶段、决策、状态转移方程几种基本关系与属性。由于是按照阶段的顺序，直接在子问题最优解的基础上计算的，“不做已经做过的工作”，因此其效率比搜索法好得多。只要问题的计算过程呈阶段性，且可找到状态转移方程，我们宁可摒弃传统的搜索而采用动态程序设计方法。第4页，共34页，编辑于2022年，星期六知知识识点点回回顾顾|是指它要么是一棵空树，要么它的是指它要么是一棵空树，要么它的左子树的所有结点比根结点小，右左子树的所有结点比根结点小，右

5、子树的所有结点比树根结点大，它子树的所有结点比树根结点大，它的左子树和右子树分别是一棵排序的左子树和右子树分别是一棵排序二叉树。二叉树。|最大排序二叉树是指在所有的排序最大排序二叉树是指在所有的排序二叉树中节点最多的一棵树。二叉树中节点最多的一棵树。第5页，共34页，编辑于2022年，星期六知知识识点点回回顾顾根据关健码值直接访问。把关键码映射到表中的一根据关健码值直接访问。把关键码映射到表中的一个位置来访问记录的过程。这个映射函数叫做哈希函数，个位置来访问记录的过程。这个映射函数叫做哈希函数，在存放记录的表叫做哈希表。也就是说，将所有元素存在存放记录的表叫做哈希表。也就是说，将所有元素存储在

6、一张表中，每一个元素具有一个哈希函数，按照如储在一张表中，每一个元素具有一个哈希函数，按照如下两种方式给同一个哈希函数值的所有元素分配多个空下两种方式给同一个哈希函数值的所有元素分配多个空间间哈希表（HashTable）第6页，共34页，编辑于2022年，星期六知知识识点点回回顾顾考虑哈希函数的因素有：考虑哈希函数的因素有：|计算哈希函数所需时间；计算哈希函数所需时间；|关键字的长度；关键字的长度；|哈希表的大小；哈希表的大小；|关键字的分布情况；关键字的分布情况；|记录的查找频率。记录的查找频率。|可以经过较少的次数得到所查的可以经过较少的次数得到所查的元素，提高查询的时间效率。元素，提高

7、查询的时间效率。第7页，共34页，编辑于2022年，星期六知知识识点点回回顾顾|四边形不等式是四边形不等式是DonaldE.Knuth从最优二从最优二叉搜索树的数据结构中提出的。当函数叉搜索树的数据结构中提出的。当函数wi,j满足：满足：时，称时，称w满足四边形不等式。满足四边形不等式。|在动态规划中被运用于证明决策的单调性。在动态规划中被运用于证明决策的单调性。第8页，共34页，编辑于2022年，星期六知知识识点点回回顾顾二叉搜索树可以实现任何一种基二叉搜索树可以实现任何一种基本的动态集合操作，但当树的高度时，本的动态集合操作，但当树的高度时，这些操作性能可能变差，即不能保证这些操作性能可能

8、变差，即不能保证在最坏的情况下动态集合操作的时间在最坏的情况下动态集合操作的时间为为O(lgn)。这样情况是因为二叉树可。这样情况是因为二叉树可能变得不平衡。用一组规则让二叉树能变得不平衡。用一组规则让二叉树平衡起来，例如，红黑树确保了没平衡起来，例如，红黑树确保了没有一条路径会比任何其他路径长到两有一条路径会比任何其他路径长到两倍，因而基本上是平衡的。倍，因而基本上是平衡的。AVL树应树应用平衡化旋转规则来完成指针结构的用平衡化旋转规则来完成指针结构的修改。修改。第9页，共34页，编辑于2022年，星期六知知识识点点回回顾顾如果将初始状态作为根结点，把从初始状如果将初始状态作为根结点，把从初

9、始状态的每一个可能棋步出发，进行一轮游戏后得到态的每一个可能棋步出发，进行一轮游戏后得到的所有子状态作为根结点的孩子结点；然后从这的所有子状态作为根结点的孩子结点；然后从这些新状态出发进行下一轮游戏，得到的又一批子些新状态出发进行下一轮游戏，得到的又一批子状态作为新状态的孩子结点，状态作为新状态的孩子结点，依次类推，就，依次类推，就可以根据游戏规则产生一棵包罗了各种可能状态可以根据游戏规则产生一棵包罗了各种可能状态变化的树，习惯上称为博弈树变化的树，习惯上称为博弈树第10页，共34页，编辑于2022年，星期六知知识识点点回回顾顾|奇数层的状态由先行方进行操作，偶数层的状态由后行方进奇数层的状

10、态由先行方进行操作，偶数层的状态由后行方进行操作；行操作；|从根结点到当前状态的走步序列（路径）表示了双方依次轮流走过从根结点到当前状态的走步序列（路径）表示了双方依次轮流走过的棋步；的棋步；|叶子是游戏的终止状态（即状态数为叶子是游戏的终止状态（即状态数为0或先前确定了取珠的洞口）。或先前确定了取珠的洞口）。若叶子处在奇数层，后行方赢；若叶子处在偶数层，先行方赢；若叶子处在奇数层，后行方赢；若叶子处在偶数层，先行方赢；|在对弈中，双方都想赢，都会采取取胜的策略。在对弈中，双方都想赢，都会采取取胜的策略。|我们在博弈树的每个结点上标一个值我们在博弈树的每个结点上标一个值F，由这个值来确定，由这

11、个值来确定操作方最佳的走法。不妨认为，操作方最佳的走法。不妨认为，F越大对先行方越有利，越大对先行方越有利，奇数层结点总是挑选使得值最大的方案走；而偶数层结奇数层结点总是挑选使得值最大的方案走；而偶数层结点则恰好相反。由于子结点是由父结点推出来的，故父结点则恰好相反。由于子结点是由父结点推出来的，故父结点的值与其所有子结点的值有一定的关系。另一方面，点的值与其所有子结点的值有一定的关系。另一方面，游戏愈接近结束愈便于分析，也便于计算值。我们可从游戏愈接近结束愈便于分析，也便于计算值。我们可从叶子结点出发，往上倒推每个结点的值，直至初始状态叶子结点出发，往上倒推每个结点的值，直至初始状态的值为止

12、。整棵博弈树建立之后，便产生出取胜的策略。的值为止。整棵博弈树建立之后，便产生出取胜的策略。第11页，共34页，编辑于2022年，星期六树树状状动动规规|某公司要举办一次晚会，但是某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在每个参加晚会的人都不希望在晚会中见到他的上司，要不然晚会中见到他的上司，要不然他们会很扫兴。现在已知每个他们会很扫兴。现在已知每个人的活跃指数和上司关系（当人的活跃指数和上司关系（当然不可能存在环），求邀请哪然不可能存在环），求邀请哪些人来能使得晚会的总活跃指些人来能使得晚会的总活跃指数最大。数最大。第12页，

13、共34页，编辑于2022年，星期六树树状状动动规规|按照要求构建一张关系图，可按照要求构建一张关系图，可见这是一棵树。对于这类最值见这是一棵树。对于这类最值问题，向来是用动态规划求解问题，向来是用动态规划求解的。的。|任何一个点的取舍可以看作一任何一个点的取舍可以看作一种决策，那么状态就是在某个种决策，那么状态就是在某个点取的时候或者不取的时候，点取的时候或者不取的时候，以他为根的子树能有的最大活以他为根的子树能有的最大活跃总值。分别可以用跃总值。分别可以用fi,1和和fi,0表示。表示。第13页，共34页，编辑于2022年，星期六树树状状动动规规|当这个点取的时候，他的所有当这个点取的时候，

14、他的所有儿子都不能取，所以儿子都不能取，所以fi,1:=sum(fj,0,j为为i的儿子的儿子)i的权值。的权值。|不取的时候，他的所有儿子取不取的时候，他的所有儿子取不取无所谓，不过当然应该取不取无所谓，不过当然应该取价值最大的一种情况。所以价值最大的一种情况。所以fi,0:=sum(max(fj,1,fj,0),j为为i的的i儿子）。儿子）。|这就是树状动规的基本形态。这就是树状动规的基本形态。第14页，共34页，编辑于2022年，星期六树树状状动动规规|大学里实行学分。每门课程都有一定的学分，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。|

15、每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，数据结构必须在选修了高级语言程序设计之后才能选修。我们称高级语言程序设计是数据结构的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，。第15页，共34页，编辑于2022年，星期六树树状状动动规规|下面举例说明|上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。|学生不可能学完大学所开设的所有课程，因此必须在入学时选定自己要学的课程。每个

16、学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。第16页，共34页，编辑于2022年，星期六树树状状动动规规|输入输入输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1M1000)，N表示学生可以选的课程总数（1NM)。以下M行每行代表一门课，课号依次为1，2M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。|输出输出输出文件第一行只有一个数，即实际所选课程的学分总数。以下

17、N行每行有一个数，表示学生所选课程的课号。第17页，共34页，编辑于2022年，星期六树树状状动动规规7 42 20 10 42 17 17 62 2表12157346图202157346图1样例分析样例分析第18页，共34页，编辑于2022年，星期六树树状状动动规规|们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如(何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？|我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：|可是如此规划，其效率与搜索毫无差别，虽然

18、我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。分析分析第19页，共34页，编辑于2022年，星期六树树状状动动规规|转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为节点a的左节点。树改造完成后如图3。|我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前一个函数表示的意义是一致的，但方程有了很大的改变：023014765图3第20页，共34页，编辑于2022年，星期六树树状状动动规规1=i=m,1=j=n,0=kj|这个方程的时间复杂度最大为n3，十分优秀了。|在具体实现这道题时，我们可以自顶而下

19、，用递归进行树的遍历求解转移方程第21页，共34页，编辑于2022年，星期六问问题题研研究究例例1、货物储运问题、货物储运问题单调性的确定第22页，共34页，编辑于2022年，星期六在一个铁路沿线顺序存放着n堆装满货物的集装箱。货物储运公司要将集装箱有次序地集中成一堆。规定每次只能选相邻的2堆集装箱合并成新的一堆，所需的运输费用与新的一堆中集装箱数成正比。给定各堆的集装箱数，试制定一个运输方案，使总运输费用最少。设合并ai:j，1ijn，所需的最少费用为mi,j，则原问题的最优值为m1，n。由最优子结构性质可知，根据递归式，按通常方法可设计计算m(i,j)的O(n3)动态规划算法第23页，共

20、34页，编辑于2022年，星期六货物储运问题的动态规划递归式是下面更一般的递归计算式的特殊情形。对于 ,当函数w(i,j)满足时称w满足四边形不等式。当函数w(i,j)满足时称W关于区间包含关系单调对于满足四边形不等式的单调函数w，可推知由递归式定义的函数m(i,j)也满足四边形不等式，即四边形不等式第24页，共34页，编辑于2022年，星期六四边形不等式定义由函数m(i,j)的四边形不等式性质可推出函数s(i,j)的单调性，即根据前面的讨论，当w是满足四边形不等式的单调函数时，函数s(i,j)单调，从而 s(i,j)s(i,j+1)s(i+1,j+1)，i j改进后算法所需的计算时间为

21、第25页，共34页，编辑于2022年，星期六问问题题研研究究例例2LOSTCITY用哈希表、检索树优化DP第26页，共34页，编辑于2022年，星期六问问题题研研究究例例3、排序二叉树、排序二叉树状态的存储第27页，共34页，编辑于2022年，星期六问问题题研研究究例例4、取分（博弈树与、取分（博弈树与DP）博弈树与DP第28页，共34页，编辑于2022年，星期六总总结结|动态规划有很多东西还需要我们动态规划有很多东西还需要我们更加努力地去探索和学习更加努力地去探索和学习.总体总体上说来上说来,动态规划是个既简单又动态规划是个既简单又不简单的算法不简单的算法,熟练地掌握了动熟练地掌握了动态规划

22、态规划,也就熟练地控制了比赛也就熟练地控制了比赛.第29页，共34页，编辑于2022年，星期六练练习习题题|垃圾陷阱（垃圾陷阱（USACO&TJU1087）|卡门卡门农夫约翰极其珍视的一条农夫约翰极其珍视的一条Holsteins奶牛奶牛已经落了到已经落了到“垃圾井垃圾井”中。中。“垃圾井垃圾井”是农夫们扔垃圾的地方，它是农夫们扔垃圾的地方，它的深度为的深度为D(2=D=100)英尺。卡英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可一些垃圾来

23、维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔门的时间。假设卡门预先知道了每个垃圾扔下的时间下的时间t(0 t=1000)，以及每个垃，以及每个垃圾堆放的高度圾堆放的高度h(1=h=25)和吃进该和吃进该垃圾能维持生命的时间垃圾能维持生命的时间f(1=f=30)，要求出卡门最早能逃出井外的时间，假设，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续卡门当前体内有足够持续10小时的能量，如小时的能量，如果卡门果卡门10小时内没有进食，卡门就将饿死。小时内没有进食，卡门就将饿死。第30页，共3

24、4页，编辑于2022年，星期六练练习习题题|字符串距离（字符串距离（TJU1086）|设有字符串设有字符串X，我们称在，我们称在X的头尾及中间插入任意多个空格后的头尾及中间插入任意多个空格后构成的新字符串为构成的新字符串为X的扩展串，如字符串的扩展串，如字符串X为为“abcbcd”，则字符串，则字符串“abcbcd”，“abcbcd”和和“abcbcd”都是都是X的扩展串，这里的扩展串，这里“”代表空格字符。代表空格字符。如果如果A1是字符串是字符串A的扩展串，的扩展串，B1是字符串是字符串B的扩展串，的扩展串，A1与与B1具有相同的长度，那么我们定义字符串具有相同的长度，那么我们定义字符串A

25、1与与B1的距离的距离为相应位置上的字符的距离总和，而两个非空格字符的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的定义为它们的ASCII码的差的绝对值，而空格字符与其它任码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值意字符之间的距离为已知的定值K，空格字符与空格字符的距，空格字符与空格字符的距离为离为O。在字符串。在字符串A、B的所有扩展串中，必定存在两个等长的所有扩展串中，必定存在两个等长的扩展串的扩展串A1、B1，使得，使得A1与与B1之间的距离达到最小，我们之间的距离达到最小，我们将这一距离定义为字符串将这一距离定义为字符串A、B的距离。的距离。请

26、你写一个程序，求请你写一个程序，求出字符串出字符串A、B的距离。的距离。第31页，共34页，编辑于2022年，星期六练练习习题题|二叉苹果树（二叉苹果树（Ural1018Ural1018）|有一棵苹果树，如果树枝有分叉，一定是分有一棵苹果树，如果树枝有分叉，一定是分2 2叉叉（就是说没有只有（就是说没有只有1 1个儿子的结点）个儿子的结点）这棵树共有这棵树共有N N个结点（叶子点或者树枝分叉点），个结点（叶子点或者树枝分叉点），编号为编号为1-N,1-N,树根编号一定是树根编号一定是1 1。我们用一根树枝两端连接的结点的编号来描述我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一

27、颗有一根树枝的位置。下面是一颗有4 4个树枝的树个树枝的树2 2 5 5/3 3 4 4/1 1现在这颗树枝条太多了，需要剪枝。但是一现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住给定需要保留的树枝数量，求出最多能留住多少苹果。多少苹果。第32页，共34页，编辑于2022年，星期六练练习习题题|最最长长前前缀缀IOI96&USACO1.4.3）|在生物学中，一些生物的在生物学中，一些生物的结结构是用包含其要素的构是用包含其要素的大写字母序列来表示的。生物学家大写字母序列来表示的。生物学家对对于把于把长长的序的序列分解成列分解成较

28、较短的（称之短的（称之为为元素的）序列很感元素的）序列很感兴兴趣。趣。如果一个集合如果一个集合P中的元素可以通中的元素可以通过过串串联组联组成一个成一个序列序列S，那么我，那么我们认为们认为序列序列S可以分解可以分解为为P中的中的元素。并不是所有的元素都必元素。并不是所有的元素都必须须出出现现。举举个例子，个例子，序列序列ABABACABAAB可以分解可以分解为为下面集合中的下面集合中的元素：元素：A,AB,BA,CA,BBC序列序列S的前面的前面K个个字符称作字符称作S中中长长度度为为K的前的前缀缀。设计设计一个程序，一个程序，输输入一个元素集合以及一个大写字母序列，入一个元素集合以及一个大

29、写字母序列，计计算算这这个序列最个序列最长长的前的前缀缀的的长长度。度。第33页，共34页，编辑于2022年，星期六练练习习题题|祝福（祝福（TJU1078）|得知得知Atlantis即将沉没的消息以后，即将沉没的消息以后，King决定把他的人决定把他的人民送到安全的国外去。但是码头已经废弃很多很多年了。民送到安全的国外去。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了这个迷宫码头前有一个迷宫，国王的骑士只身闯入了这个迷宫骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所以很快便招架不住了，他的大马被打得奄奄一

30、独作战，所以很快便招架不住了，他的大马被打得奄奄一息（。）这个时候，迷宫中的两座石像息（。）这个时候，迷宫中的两座石像(一个是猫老一个是猫老大，一个是天使。（！大，一个是天使。（！)里放出了无数锋利的刀里放出了无数锋利的刀片，把不明生物全部杀死，骑士当场晕倒在地。等他醒来，片，把不明生物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒指，上面写着：发现马已经死了，手上多了一个戒指，上面写着：“这这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要次移动如果是只要|x-x1|+|y-y1|(x1,y1)的移动！的移动！”(Angel暗自想：还有这么心黑的暗自想：还有这么心黑的)迷宫为迷宫为n*m的矩阵。骑士从的矩阵。骑士从(n,m)到到(1,1)。问：在戒指的帮助下，骑士最少要多少步才能回到问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提下，总共有多少种办法到入口？在步数最少的前提下，总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。达入口？注意，骑士不会傻到一直停留在原地不动。第34页，共34页，编辑于2022年，星期六

展开阅读全文