太阳000 / c/C++ / 动态规划详解 第三章...

0 0

   

动态规划详解 第三章...

2008-12-10  太阳000
动态规划详解 第三章

这一章,我们来学习树形动态规划。
动态规划一般来说分为四大类:线性动态规划,区间动态规划,树形动态规划和特殊种类动态规划。
因为线性模型和区间类模型紧密相关,所以一般我们将这两种类型放在一起学习。
树形动态规划和以上两种不同,它是在一个树结构中进行的,因此具有一般性,
而特殊种类动态规划则包含比较广,譬如状态压缩,
博弈以及其他各种问题都可以归纳到这个部分,因为问题比较分散,
所以这个部分就请大家自己学习,可以参考历年国家集训队论文,
对这个部分的讨论十分透彻和深入。

下面就让我们来学习树形动态规划。
首先看一道例题:
例:给定一棵树T,树中每个顶点u都有一个权w(u),权可以是负数。
现在要找到树T的一个个连通子图使该子图的权之和最大。
分析一下这道题,我们发现,对于节点A,如果考虑以他为根的一棵子树,
那么它的最优值和他的父节点无关,所以转移方程为:
F[I]=sigma{F[son],当F[son]>0时}+w(u)
最终的答案为F[X]中的最大值。
因为是在一棵树当中进行动态规划,所以不妨用递归的形式来编写。

通过上面的例子,相信大家对树形动态规划有了一个初步的认识,
其实树形动态规划属于动态规划中一个较难的问题,因为约束条件往往比较多,
所以状态的转移并不容易,下面看一个较难的例子:

在一棵树中,每条边都有一个长度值,现要求在树中选择3个点X、Y、Z,
满足X到Y的距离不大于X到Z的距离,且X到Y的距离与Y到Z的距离之和最大,求这个最大值。
其中顶点个数N<=2000000
因为数据规模很大,所以考虑O(N)或者O(NlogN)的算法。
分析问题,我们发现因为在一棵树中,所以x,y,z的路径中必定有一个交点k,
距离S=xk+2*ky+kz,我们发现,若要S达到最大值,
那么只需要ky,xk,kz为以k为根的树中三个不在同一子树中的最大的三个距离就可以了,
但是这样的时间复杂度依然为O(n^2),继续分析发现,
实际上第一次求出以某个节点为根的距离后,
只需要以这个点为根再dfs遍历一遍就可以求出其他的节点距离,所以总的时间复杂度为O(N)。

再次回味一下这道题的解题思路:我们首先从数据规模确定了算法的复杂度,
并通过对模型的初步分析得到了一些性质,然后通过这些性质得到了新的解题思路,
这其实是解树形动态规划乃至其他问题的一个一般性的思路

通过对树模型的特殊性分析,可以大大的降低时间复杂度。

最后让我们来看一个很具有发散性的题目:

奶牛成群、土地众多的FJ有一个地形狭长的农场,农场被分成了n块土地,n不超过1000。
这些土地位于一条直线上,并从左到右编号为1至n。每块土地的面积都相同,
但是高度不一定相同。每块土地都拥有一个海拔高度值,这个值不超过1000000。
如果一段相同高度土地的两边都比它低或者是农场的边界,那么这段土地将被称之为“山顶”。
FJ希望通过搬走泥土来降低某些土地的海拔高度,使“山顶”的数目不超过k,其中1≤k≤25。
在这一前提下,FJ希望搬运的泥土体积最小,也就是所有的土地减少的高度和最小。

初看上去这道题似乎和树形动态规划没有什么关系,根本没有树结构的样子,
分析一下我们发现,所谓的山峰,就是每个层中不连接的部分,所以从层的角度思考,
显然,每个层之与他的上层和他的下层的有关,与层的长度无关,所以不访化层为点,
以地面为基础节点,每一层不连接“块”为一个节点,用边连接不同层的相邻的点,
我们惊讶的发现,这些点构成了一棵树!
进一步分析,发现每次“削平”一个山顶,在树中就是删除一个最叶子节点,
而消除的高度则可以看作是节点的权值,这样,问题就转化到了在树中删除一些节点,
使最终的节点数目不超过k+1,并且剩余权值最大的问题,复杂度为o(nk^2)。

多么巧妙的转化!一道看似复杂的问题就这样解决了,以无限为有限,以无法为有法,这或许就是算法的魅力。

<<<<<<<<<<<<<<<<<<<<<<<<<To be continue>>>>>>>>>>>>>>>>>

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    猜你喜欢

    0条评论

    发表

    请遵守用户 评论公约

    类似文章
    喜欢该文的人也喜欢 更多