随笔-48  评论-259  文章-1  trackbacks-0

.最优归并模式

    在前面已看到两个分别包含n个和m个记录的已分类文件可以在o(n+m)时间内归并在一起而得到一个分类文件。当要把两个以上的已分类文件归并在一起时,可以通过成对地

重复归并已分类的文件来完成。例如,假定x1x2x3x4是要归并的文件,则可以首先把xl和x2归并成文件yl,然后将yl和x3归并成y2,最后将y2和x4归并,从而得到想要的分类文件;也可以先把x1和x2归并成y1,然后把x3和x4归并成y2,最后归并y1和y2而得到想要的分类文件。给出n个文件,则有许多种把这些文件成对地归并成一个单一分类文件的方法。不同的配对法要求不同的计算时间。现在所要论及的问题是确定一个把n个已分类文件归并在一起的最优方法(即需要最少比较的方法)。

    例`1 xl,x2和x3是各自有30个记录、20个记录和10个记录的三个已分类文件,归并xl和x2需要50次记录移动,再与x3归并则还要60次移动,其所需要的记录移动总量是110。如果首先归并x2和x3(需要30次移动),然后归并x1(需要60次移动),则所要作的记录移动总数仅为90。因此,第二个归并模式比第一个要快些。

    试图得到最优归并模式的贪心方法是容易表达的。由于归并一个具有n个记录的文件和一个具有m个记录的文件可能需要n+m次记录移动,因此对于量度标准的一种明显的选择是:每一步都归并尺寸最小的两个文件。例如,有五个文件(f1,f:),它们的尺寸为(20,30,10,5,30),由以上的贪心策略就会产生以下的归并模式:f4和f3归并成z1( =15);归并zl和f2得到z2( =35);把f2和f5归并成z3( =60);归并z2和z3而得到答案z4。记录移动总量是205。可以证明这是给定问题实例的最优归并模式。

1 表示一个归并模式的二元归并树文件的长度(即记录数)。

 

    像刚才所描述的归并模式称为二路归并模式(每一个归并步包含两个文件的归并)。二路归并模式可以用二元归并树来表示。图1显示了一棵表示上面五个文件所得到的最优归并模式的二元归并树。叶结点被画成方块形,表示这五个已知的文件。这些结点称为外部结点。剩下的结点被画成圆圈,称为内部结点。每个内部结点恰好有两个儿子,它表示把它的两个儿子所表示的文件归并而得到的文件。每个结点中的数字都是那个结点所表示的    外部结点f4在距离根结点z4为3的地方(一个i级结点在距离根为i一1的地方),因此文件f4的记录都要移动三次,一次得到z1,一次得到z2,最后移动一次就得到z4。如果凡是由根到代表文件n的外部结点的距离,qi是fj的长度,则这棵二元归并树的记录移动总量是   

这个和数叫做这棵树的带权外部路径长度   

一个最优二路归并模式与一棵具有最小权外路路径的二元树相对应,算法6的过程tree使用上面所叙述的规则去获得n个文件的二元归并树。,这算法把n个树的表l作为输入。树中的每一个结点有三个信息段,lchld,rchild和weight。起初,l中的每一棵树正好有一个结点。这个结点是一个外部结点,而且其lch丸d和rchild信息段为0·,而weight是要归并的n个文件之一的长度。在这个算法运行期间,对于l中的任何一棵具有根结点t的树,weight(t)表示要归并的文件的长度(weight(t)等于树t中外部结点的长度的和)。过程tree用了三个子算法,getnode(t),least和insert(l,t)。子算法getnode(t)为构造这棵树提供一个新结点。least(l)找出l中一棵其根具有最小的weight 69树,并把这棵树从l中删去。insert(l,t)把根为丁的树插入到表l中。定理3.4将证明贪心过程tree(算法3.6)产生一棵最优的二元归并树。

算法6 生成二元归并树算法   

    line proceduretree (l,n)(动画)

//l是如上所述的n个单结点二元树的表//

 for iß1 to n-1 do    

    call  getnode(t) //用于归并两棵树//   

    lchild (t)<--least(l) //最小的长度/

    rchild (t)<--least(l)

    weight(t)<--weight(lchild(t))+weight(rchild(t))

    call insert(l,t)

repeat    return(least(l))

//留在l中的树是归并树"

   end tree

   (动画演示)

 例2 当l最初表示其长度为2,3,5,7,9,13六个文件时,算法tree是如何工作的。图显示出在for循环的每一次迭代结束时的表l。在算法结束时所产生的二元归并树可以用来确定归并了哪些文件。归并是在这棵树中最低(有最大的深度)的那些文件上进行的。

    现在来分析算法6需要的计算时间。主循环执行n一1次。如果保持l按照这些根中的weight值的非降次序,则least(l)只需要o(1)时间,insert(l,t)在o(n)时间内被执行。因此所花费的时间总量是o(n)。在l被表示成一个min堆的情况下,其中根的值不超过它的儿子们的值,则least(l)和insert(l,t)可以在o(10gn)时间内完成(least(l)和insert(l,t)的算法以及其计算时间分析留作习题)。在这种情况下tree的计算时间是o(nlogn)。将第6行的insert和第4行的least结合起来还可以加快一些速度。   

 定理 若l最初包含n1个单个结点的树,这些树有weight值为(q1,q2,q9),则算法tree对于具有这些长度的n个文件生成一棵最优的二元归并树,

  

 证明: 通过施归纳于n来证明。对于n=1,返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于所有的(q1,q2 qn),1m<n,生成一棵最优二元归并树,现在来证明对于所有的(q1,q2 qn)也生成最优的树。不失一般性,假定qlq2≤…≤qn,且ql和q2是在for循环的第一次迭代期间由第3行和第4行中的算法least所拽到的两棵树的weight信息段的值。于是就生成了图3.4的子树t。设t是一棵对于(q1,q2,qn)的最优二元归并树。设P是距离根最远的一个内部结点。如果P的儿子不是q1和q2,则可以用q1和q2来代换P现在的儿子而不增加t的带权外部路径长度。因此t也是一棵最优归并树中的子树。于是在t中如果甩其权为q1+q2的一个外部结点来代换t,则所产生的树t’’是关于(q1+q2,q3,qn)的一棵最优归并树。由归纳假设,在用其权为ql+q2的那个外部结点代换了t以后,过程tree转化成去求取一棵关于(ql+q2,q3,qn)的最优归并树。因此tree生成一棵关于(q1,q2,qn)的最优归并树。证毕。

    生成归并树的贪心方法也适用于k路归并的情况。在这种情况下,相应的归并树是一棵k元树。由于所有的内部结点的度数必须为k,因此对于n的某些值,就不与k元归并树相对应。例如,当k=3时,就不存在具有n=2个外部结点的k元归并树。所以有必要引进一定量的外部结点.每一个虚结点被赋以0值的qi。这个虚值不会影响所产生的k元树的带权外部路径长度。本章习题11表明其所有内部结点都具有度数为k的k元树的存在性,只有当外部结点数n满足等式n mod(k一1)=1时才成立。因此至多应增加k一2个虚结点。生成最优归并树的贪心规则是:在每一步,选取k棵具有最小长度的子树用于归并。关于它的最优性证明,则留作习题。

  

posted on 2007-06-18 13:44 星梦情缘 阅读(2691) 评论(0)  编辑 收藏 引用 所属分类: 算法分析

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理