算法合集之《浅析树的划分问题》.ppt

《算法合集之《浅析树的划分问题》.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、东北育才学校贝小辉浅析树的划分问题概要树的划分问题：将给定的一棵树划分为若干棵子树，使其能够满足一定的条件或是使得某个特定的函数达到最值。树的最大－最小划分问题。问题的提出草莓（NOI2003Day2-2test6～test9）题目大意：给出一片草莓中每个草莓的重量以及它们的连接情况。令sum(i)表示第i块草莓田中所有草莓重量的和(1≤i≤k),x=min{sum(i)

2、1≤i≤k}。你的任务就是要把一块草莓田分割成k块，且分割方案需要满足如下的条件：每一块中的草莓必然是直接或者间接的和其他草莓相连接的；这种分割方案所对

3、应的x尽可能的大。最后输出你的分割方案和结果。问题的提出这是一道提交答案式的题目，其中test6～test9所给的图是一棵树，若不考虑具体的数据情况，我们可以将原问题抽象成如下问题：给定一棵树以及树中每个顶点的一个非负权值，将树划分为k棵子树，定义：sum(i)表示第i棵子树中所有顶点权值的和，x=min{sum(i)

4、1≤i≤k}，请求出x的最大值并输出一种划分方案。我们把它称作树的最大－最小划分问题。算法1：问题转化考虑新问题：对于一个确定的下界，最多可将树划分为多少棵子树，使得每棵子树的权值和都不小于此下界？新问题＋

5、二分法原问题解决新问题新问题的解决只需要一个以贪心思想为基础的扫描算法。393531264下界：1035124173106解决原问题时间复杂度：O(N)已是理论下界通过二分法来找到最大的下界x，使得划分的最大子树数目不小于k，x即为原问题的解。小结解决问题的途径：问题转化实现简单，运行效果好运行时间依赖于节点的权值范围若节点的权值范围很大或者权值是小数甚至无理数……时间复杂度不依赖于节点权值范围的算法？Perfect新思路：割一条边所连接的两个顶点分属不同的子树，则称在这条边上有一个“割”。每个割对应一棵子树+根节点所在子

6、树划分k棵子树将k-1个割分配到k-1个不同的边上新思路：移动一次移动被定义为将一个割从一条边移到一条与它相邻的边上，并且保证新的边一定是在原来那条边的下一层。新算法:初始状态+移动规则关键点初始状态最简单的方法：·任选一个度为1的顶点为根·将所有割都放在与根相连的唯一的边上可以由初始状态到达任何一个目标状态关键：移动规则的制定移动规则依据的还是一种贪心的思想：1.计算出当前状态下子树权值和的最小值Wmin2.考虑所有可能的移动，找出能使移动后的割所对应的子树权值和Wnow最大的那种移动3.如果Wnow≥Wmin，那么进行

7、这步移动，并转到步骤14.算法结束，Wmin即为所求的最大的最小值，当前划分即为一种最优划分证明？例子79139128当前划分一种最优划分“上方”当前划分总是在某个最优划分的“上方”“上方”的定义划分A在划分A’的上方，也就是存在一种A的割和A’的割的一一对应，使得每个A的割都在它所对应的A’的割的上方。更加实用的性质？定义：部分子树若一棵树T的子树T’包含了顶点v连同v的某一个儿子以及这个儿子的所有后继，则称T’是T在顶点v处的一棵部分子树。与v相连的唯一一条边被称为T’的初始边。v初始边重要性质划分A在划分A’上方AA

8、’#(A)≤#(A’)证明算法(1)在初始状态时的划分A是在任何一个最优划分Q的上方的。(2)若存在一个最优划分Q使得当前的划分A是在Q的上方，且A和Q不相等，则算法一定不会终止。(3)设A在Q的上方且A不等于Q，在算法进行一步后A变为A’，我们一定还能找到一个最优划分Q’使得A’在Q’上方。(4)算法会在有限步内终止，算法终止时的划分一定是一个最优划分。一些说明字母A表示由算法进行而得到的划分。字母Q表示一个最优划分，即使得最小子树最大的划分。用Wmin(A)表示在划分A下的最小子树的权值和对于任意划分A，Wmin(A)

9、≤Wmin(Q)证明算法(2)(2)若存在一个最优划分Q使得当前的划分A是在Q的上方，且A和Q不相等，则算法一定不会终止。当前划分A最优划分Qcsc’c’≥Wmin(Q)≥Wmin(Q)≥Wmin(A)证明算法(3)(3)设A在Q的上方且A不等于Q，在算法进行一步后A变为A’，我们一定还能找到一个最优划分Q’使得A’在Q’上方。ccsse1e2v≥Wmin(Q)当前划分A最优划分Q情况1：对于在顶点v处的每一棵部分子树T’，都有#(A)=#(Q)。证明算法(3)情况2：存在在顶点v处的某棵子树T’，使得#(A)<#(Q)。

10、cce1e2vss≥Wmin(Q)≥Wmin(Q)≥Wmin(Q)e3当前划分A最优划分Q呼，终于证完了……小结新思想，新方向：割，移动贯穿整个证明过程的思想：上方当前划分最优划分上方“序”的概念算法的扩展权函数的扩展子树中所有节点的权值之和子树中节点权值最大值？子树半径？（树的P中心问题）……？权函数