内蒙古大学《算法与数据结构》讲义14分而治之算法
33页1、下载第1 4章分而治之算法君主和殖民者们所成功运用的分而治之策略也可以运用到高效率的计算机算法的设计过程中。本章将首先介绍怎样在算法设计领域应用这一古老的策略,然后将利用这一策略解决如下问题:最小最大问题、矩阵乘法、残缺棋盘、排序、选择和一个计算几何问题找出二维空间中距离最近的两个点。本章给出了用来分析分而治之算法复杂性的数学方法,并通过推导最小最大问题和排序问题的复杂性下限来证明分而治之算法对于求解这两种问题是最优的(因为算法的复杂性与下限一致) 。14.1 算法思想分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题,可以: 1) 把它分成两个或多个更小的问题; 2) 分别解决每个小问题;3) 把各小问题的解答组合起来,即可得到原问题的解答。小问题通常与原问题相似,可以递归地使用分而治之策略来解决。例14-1 找出伪币 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的,并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。比较硬币1与硬
2、币2的重量。假如硬币1比硬币2轻,则硬币1是伪造的;假如硬币2比硬币1轻,则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等,则比较硬币 3和硬币4。同样,假如有一个硬币轻一些,则寻找伪币的任务完成。假如两硬币重量相等,则继续比较硬币5和硬币6。按照这种方式,可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把 1 6硬币的例子看成一个大的问题。第一步,把这一问题分成两个小问题。随机选择 8个硬币作为第一组称为A组,剩下的8个硬币作为第二组称为B组。这样,就把1 6个硬币的问题分成两个 8硬币的问题来解决。第二步,判断 A和B组中是否有伪币。可以利用仪器来比较 A组硬币和B组硬币的重量。假如两组硬币重量相等,则可以判断伪币不存在。假如两组硬币重量不相等,则存在伪币,并且可以判断它位于较轻的那一组硬币中。最后,在第三步中,用第二步的结果得出原先 1 6个硬币问题的答案。若仅仅判断硬币是否存在,则第三步非常简单。无论 A组还是B组中有伪币,都可以推断这 1 6个硬币中存在伪币。因此,仅仅通过一次重量的比较,就可以判断伪币是否存在。现在假设需要识别
3、出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币,那么不能判断出它是否就是伪币。在一个小问题中,通过将一个硬币分别与其他两个硬币比较,最多比较两次就可以找到伪币。这样,1 6硬币的问题就被分为两个8硬币(A组和B组)的问题。通过比较这两组硬币的重量,可以判断伪币是否存在。如果没有伪币,则算法终止。否则,继续划分这两组硬币来寻找伪币。假设B是轻的那一组,因此再把它分成两组,每组有 4个硬币。称其中一组为 B1,另一组为B2。比较这两组,肯定有一组轻一些。如果 B1轻,则伪币在B1中,再将B1又分成两组,每组有两个硬币,称其中一组为 B1a,另一组为B1b。比较这两组,可以得到一个较轻的组。由于这个组只有两个硬币,因此不必再细分。比较组中两个硬币的重量,可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。例14-2 金块问题 有一个老板有一袋金块。每个月将有两名雇员会因其优异的表现分别被奖励一个金块。按规矩,排名第一的雇员将得到袋中最重的金块,排名第二的雇员将得到袋中最轻的金块。根据这种方式,除非有新的金块加入袋中,否则第一名雇员所得到的金块总是比第二名雇
4、员所得到的金块重。如果有新的金块周期性的加入袋中,则每个月都必须找出最轻和最重的金块。假设有一台比较重量的仪器,我们希望用最少的比较次数找出最轻和最重的金块。假设袋中有n 个金块。可以用函数M a x(程序1 - 3 1)通过n-1次比较找到最重的金块 。找到最重的金块后,可以从余下的 n-1个金块中用类似的方法通过 n-2次比较找出最轻的金块。这样,比较的总次数为2n-3。程序2 - 2 6和2 - 2 7是另外两种方法,前者需要进行2n-2次比较,后者最多需要进行2n-2次比较。下面用分而治之方法对这个问题进行求解。当 n很小时,比如说,n2,识别出最重和最轻的金块,一次比较就足够了。当n 较大时(n2) ,第一步,把这袋金块平分成两个小袋A和B。第二步,分别找出在 A和B中最重和最轻的金块。设 A中最重和最轻的金块分别为 HA 与LA,以此类推,B中最重和最轻的金块分别为HB 和LB。第三步,通过比较HA 和HB,可以找到所有金块中最重的;通过比较LA 和LB,可以找到所有金块中最轻的。在第二步中,若 n2,则递归地应用分而治之方法。假设n= 8。这个袋子被平分为各有4个金块的两
5、个袋子A和B。为了在A中找出最重和最轻的金块,A中的4个金块被分成两组A1和A2。每一组有两个金块,可以用一次比较在A中找出较重的金块HA1和较轻的金块LA1。经过另外一次比较,又能找出 HA2和LA2。现在通过比较HA1和HA2,能找出HA;通过LA 1和LA2的比较找出LA。这样,通过4次比较可以找到HA 和LA。同样需要另外4次比较来确定HB 和LB。通过比较HA 和HB(LA 和LB) ,就能找出所有金块中最重和最轻的。因此,当n= 8时,这种分而治之的方法需要 1 0次比较。如果使用程序1 - 3 1,则需要1 3次比较。如果使用程序2 - 2 6和2 - 2 7,则最多需要1 4次比较。设c(n)为使用分而治之方法所需要的比较次数。为了简便,假设n是2的幂。当 n= 2时,c(n) = 1。对于较大的 n,c(n) = 2c(n/ 2 ) + 2。当n是2的幂时,使用迭代方法(见例 2 - 2 0)可知c(n) = 3n/ 2 - 2。在本例中,使用分而治之方法比逐个比较的方法少用了2 5的比较次数。例14-3 矩阵乘法 两个nn 阶的矩阵A与B的乘积是另一个nn 阶矩阵C
《内蒙古大学《算法与数据结构》讲义14分而治之算法》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义14分而治之算法》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页