d森林树算法分析jiaoWord文档下载推荐.doc
《d森林树算法分析jiaoWord文档下载推荐.doc》由会员分享，可在线阅读，更多相关《d森林树算法分析jiaoWord文档下载推荐.doc（4页珍藏版）》请在冰点文库上搜索。
关键字：
贪心算法d森林分离
一、贪心算法：
贪心策略是指从问题的初始状态出发，通过若干次的局部最优选择即贪心选择而得出最优值（或较优解）的一种解题方法。
贪心策略总是做出在当前看来是最优的选择，并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
二、问题描述：
设T是一棵带权树，树的每一条边带一个正权。
设S是T的顶点集，T/S是从树T中将S中的顶点删去后得到的森林。
如果T/S中所有树的根到叶的路长都不超过d，则称T/S是一个d森林。
（1）设计一个算法求T的最小顶点集S，使T/S是d森林。
（提示：
从页向根移动。
）
（2）分析算法的正确性和计算复杂性。
（3）设T中有n个顶点，则算法的时间复杂性应为O（n）。
三、问题分析
编程任务:
对于给定的带权树。
编程计算最小分离集S。
数据输入:
由文件input.txt给出输入数据。
第一行有一个正整数n，表示给定的带权树有n个顶点，编号为1,2,3，·
·
，n。
编号为1的顶点是树根。
接下来的n行中，第i+1行描述与第i个顶点相关联的边的信息。
每行的第一个正整数k表示与该顶点相关的边数。
其后2k个数中，每两个数表示一条边。
第一个数是与该顶点相关联的另一个顶点的编号，第二个数是边权值。
当k=0时表示相应的结点是叶结点。
文件的最后一行是正整数d，表示森林中所有树的从根到叶的路长都不超过d。
结果输出：
将编程计算出的最小分离集S的顶点数输出到文件output.txt。
如果无法得到所要求的d森林则输出NoSolution！
。
输入文件示例
input.txt
4
22331
142
4
输出文件示例
output..txt
1
四、算法解答：
1.用父亲数组parent表示树；
leaf存储叶结点编号。
readin读入初始数据。
publicstaticvoidreading（）
{
ReadStreamkeyboard=newReadstream（）;
n=keyboard.readInt（）;
for（inti=1;
i<
=n;
i++）{
deg[i]=keyboard.readInt（）;
for（intj=0;
j<
deg[i];
j++）{
p=keyboard.readInt（）;
len=keyboard.readInt（）;
parent[p]=i;
parlen[p]=len;
}
If（deg[i]==0）leaf[++leaf[0]]=i;
}
p=keyboard.readInt（）;
}
2.从叶结点向根结点移动。
从根节点到叶节点的路长超过d时，将该子树分离。
publicstaticvoidcount（）
inttotal=0;
=leaf[0];
i++）
if（leaf[i]!
=1）{//非根结点
intplen=parlen[leaf[i]],par=parent[leaf[i]];
if（cut[par]<
1&
&
dist[leaf[i]]+plen>
p）{
total++;
cut[par]=1;
par=parent[par];
}
else
if（cut[par]<
dist[par]<
dist[leaf[i]]+plen）
dist[par]=dist[leaf[i]]+plen;
if（--deg[par]==0）leaf[++leaf[0]]=par;
}
returntotal;
}
五、算法分析
1.数据输入：
（以给出的示例为例）
输入n=4；
i=1时，deg[i]=deg[1]=2（表示与顶点相关的有两条边）
j=0时，p=2,len=3
parent[p]=parent[2]=1（表示结点2的父结点是1号结点）
parlen[p]=parlen[2]=3（权值为3）
j=1时，p=3，len=1
parent[p]=parent[3]=1（表示结点3的父结点是1号结点）
parlen[p]=parlen[3]=1（权值为1）
i=2时，deg[i]=deg[2]=1（表示与2号结点相关的边有1条）
j=0时，p=4，len=2
parent[p]=parent[4]=2（表示结点4的父结点是2号结点）
parlen[p]=parlen[4]=2（权值为2）
i=3时，deg[i]=deg[3]=0
leaf[++leaf[0]]=3（leaf[0]的初始值为0，记录叶子节点的个数，3表示叶结点的编号）
i=4时，deg[i]=deg[4]=0
leaf[++leaf[0]]=4（4表示叶结点的编号）
最后，leaf[0]=2.
最后输入p=4，表示d=4.
时间复杂度为O（n）。
2．cout算法
total表示S集合中节点的个数
算法思想：
从叶结点向根结点移动。
时间复杂度：
f（n）=1/leaf[0]*{（1+leaf[0]）*leaf[0]/2}
=（1+leaf[0]）/2
O（（1+leaf[0]）/2）=O
（1）
升级会员 