您的位置: 首页> 刘羽>日志

相似顾问推荐

刘羽

刘羽
申请指导师

  • 常见问题

我接受并同意 《用户服务条款》《隐私权相关政策》

提交
输入您的意向国家、阶段
免费申请留学资料
  • 意向国家/地区:
  • 意向阶段:
  • 就近城市:
  • 您的姓名:
  • 您的电话:
立即免费申请
首页| 企业文化| 联系我们| 加入我们| English website| 微博:新浪| 投诉建议| 隐私协议
经营许可证编号:京ICP备05067667号-32 | 京ICP证060601号 | 京网文【2019】5257-605号 | 京公网安备11010802021790号
©版权所有:新东方教育科技集团有限公司
留学评估

免费留学评估

免费获取
扫码关注

关注新东方前途出国

新东方前途出国公众号
2022年全新留学评估及费用计算器上线啦 为您定制个性化留学方案
免费获取
点击领取

刘羽申请指导师

分治:怎样拆解问题,逐个击破?
更多详情
 09 分治:怎样拆解问题,逐个击破?

我们上一讲说到,迭代的算法策略可以一步步逼近最终答案,效率非常高。想要提高效率,其实还有另一种完全不同的思路,就是把大问题分拆成很多个小问题,再各个击破。

这就是我们这一讲要说的,算法中的分治策略。

说起分治,你可能会想到战国时期,秦灭六国的故事。

那个时候,七雄割据天下。关东六国都忌惮秦国,进行了合纵联盟。秦国想统一天下,但却不能一下吃掉其他六雄,于是使出连横的外交手段,瓦解了六国的联盟,然后分而治之。

这就是在大问题不能解决的情况下,把它分解成一些小问题,逐个解决的思想。

算法领域,也有这么一些算法,采用了把大问题分解成小问题的策略来进行计算。我们管它们叫分治算法

我们这一讲,就来说说分治算法是怎么提高效率的。

1 分治算法:拆大为小的回溯算法

虽然秦灭六国背后的道理,也是大问题拆成小问题,但请注意,分治算法和我们通常说的分治相比,有很大的区别。要想真正理解这种算法,我们需要先正本清源,看看分治算法和我们平时说的分治有什么本质的不同。

先说答案,分治算法有回溯的过程,而平时说的分治是没有的。

什么是回溯呢?咱们来看一个例子。

假设你是中国网球公开赛的总裁判。今年的比赛,有64位选手参加。而你的任务是执法比赛,决出冠军。

比赛选手很多,两两比赛肯定要很多场。而你想偷个懒,想出了一个外包的办法。

你把64位选手平分成两个半区,每个半区32位选手,每个半区分别外包给另外两个裁判去负责。他们接下来怎么做你不管,只要他们告诉你每个半区的胜者是谁,你接下来,就只执法这两个胜者之间的一场比赛,就能决出冠军了。

办法挺好!

结果这两个裁判也很懒。他们每个人也把工作分成了两份,交给下层的4个裁判去做,自己只负责一场比赛。接下去的4个裁判也很懒,继续分解外包工作。

最后一层的裁判,手里只有两个选手,不用外包了,打一场吧。决出胜者之后,这些裁判再把结果逐层汇报给上级。

这个过程不难理解。而且我猜你一定发现了,这个过程中有一个特点,就是所有裁判面对的问题、执行的操作非常相似。

如果我们要把这个过程写成算法的话,只需要写一小段程序,描述一个裁判要做的操作就行了。

这个程序只有两个功能,一个是分解,把执法比赛的任务外包;另一个是合并,把外包后得到的答案,也就是两个半区各自的胜者,以比赛的方式决出唯一胜者,作为输出。

而在程序把问题分解成两个小一点的子问题的时候,因为子问题和原问题的结构相同,程序会调用它自己。自己循环调用自己,这就形成一个嵌套循环的结构。每个层级中遇到的问题规模,都比上一个层级小,直到规模小到可以直接通过比较得到答案。

这个嵌套循环调用自己的过程,就叫回溯

回溯的好处你可能也听出来了,就是省了好多事儿。如果没有回溯,算法工程师就要把每层拆解的过程都一层层地写出来。有了回溯,你教会计算机做一层拆解,它就会自己进行多层的拆解。

这是算法的分治策略,和我们生活中说分治的本质不同。

分治算法是通过回溯,不断分解同样的问题,直到问题小到可以直接解决,然后再把小问题的解,合并成原来问题解的算法策略。

而秦灭六国呢,里面只有拆大为小,却没有回溯的过程,所以它和算法的分治策略不是一回事。

2 保证分治算法有效的条件

那是不是每个问题都能通过分解、合并的方法,用分治策略解决呢?

当然不是。这个问题里其实包含了两层,一个是能不能用,一个是用了之后求解快不快。

先说说能不能的问题。

还记得之前说过的背包模型吗?一个背包有固定承重,比如只能装64公斤的东西。现在有64件物品,每件重量和价值都不同,我们该带哪些物品能把总价值最大化呢?

假设咱们还用跟网球赛类似的分治策略,把32件物品分配到上半区,32件物品放到下半区,每个半区背包的承受重量,也不断平均分配。

那么最后的子问题就成了:有一个载重1公斤的背包,和1件物品,放还是不放?这样一来,问题就出现了。可能有物品价值连城,但重量是2公斤,背包放不了,很多物品就这么被放弃了。你最后选出来的那些物品,并不是价值最大的组合。

为什么分治策略不好使了呢?因为这个问题不可以简单分解。所有的物品共享同样的背包空间,每个子问题本质上并不独立。这样强行分解成子问题,得到的答案合在一起,也不是原问题的答案。

也就是说,我们要确保问题可以分解成和原问题类似的子问题,并且这些子问题之间还相互独立,这时分治策略才能奏效。

说完能不能的问题,再说快不快的问题。

秦灭六国之所以要分治,是因为大问题解决不了。而算法分治策略的目的,不是要把一个不能解决的问题解决掉,而是要解决得更快。

咱举个例子,在计算机图形学中有个问题叫碰撞检测。就是说在一个计算机模拟的空间中,有很多物体。我们要判定任何两个物体有没有碰到。

说得通俗一点,就是在你玩电子游戏的时候,计算机要判定敌人的子弹有没有打到你头上。

解决这个问题可不容易,尤其是模拟的空间中物体很多的时候。

假设空间中有100个圆球在运动,咱们想知道它们之间哪些撞在了一起,就需要计算它们两两之间的距离。100个球总共的计算次数是4950次。如果物体的个数更大些,计算次数会以平方的形式上升。

平方的形式,复杂度就挺高了。如果用这种算法,游戏在进行得枪林弹雨时,你的画面肯定会卡。

采用分治的策略,就能让算法运行得更快些。

你可以想象一下。空间中的这100个球,不一定总是聚在一起。没准50个在左边,50个在右边。

咱们可以在中间画一条线,把空间分成两部分。这样两个空间相互分开,独立检测两个空间就好了。这么做,计算的次数可以从我们刚刚说的4950次,降低到2450次。再分割一次的话,计算次数还能下降到1200次。

但这不一定总能奏效。比如说我们在画线分割空间的时候,可能确定不了在哪里画线最好。我们想找到的位置,需要让两个空间里面球的数量尽量相同。那找到这个位置就需要额外的计算,这就是分解的时候计算成本的问题。

合并的时候,也有类似的问题。比如说你在分割空间的时候,可能会正好把某些球从中间割断。合并的时候,你发现这些球不属于任何一个子空间,要判断它们有没有发生碰撞,还得额外计算。这是合并结果的成本。

你看,分治中的两个重要操作,分解和合并,不是免费的。如果它们自身就要耗费很多次计算,那很可能分治策略提升不了效率,也不算是奏效了。

3 分治算法能更快的特殊之处

分治算法还有一个特殊的地方,我一定要跟你说说。

刚刚说的,减少基本操作的个数,这属于在软件上对算法效率进行提升。分治算法,还可以通过巧妙地利用硬件,让效率进一步提升。这就是并行计算

什么意思呢?咱们回到网球比赛的问题里。如果每个裁判员是一个CPU的话。多个CPU可以共同协作,我们就能用更短的时间完成任务。这就是并行计算。

并行计算能让多个计算机的CPU同时为解决一个问题出力,但并不能减少总的操作数量。一个裁判要执法63场比赛。两个裁判也要执法63场比赛,总的复杂度没有变。但把任务分摊在两个CPU上,它们可以同时独立工作,完成任务的时间就可以减半。

为什么说这是分治算法特殊的地方呢?其他算法,比如我们上一讲说的迭代算法,能不能也并行在多个CPU上进行呢?

很可惜,不行。并不是所有算法都可以用并行计算的。

迭代算法要求每一步以前一步的结果作为出发点,按步骤、按顺序进行计算。如果让一个CPU计算前面的步骤,第二个CPU计算后面的步骤,两个CPU不能同时工作,就不是并行计算。

这里你就看到了,顺序计算和并行计算有本质上的差异。分治算法因为能把问题分解成独立的部分,所以和并行计算是天然的好朋友。

最近这些年,大数据在高科技领域掀起浪潮。数据量越大,处理起来的所花的步骤也就多。那为了能快速地对数据进行分析处理,就必须用分治算法。

分治的算法需要先分解问题,再合并。但如果问题不能被分解,那又该怎么办呢?下一讲我们要讲到的算法动态规划,就能应对这个状况。我们下一讲详细来说。

 

分享
请刘羽老师帮我评估
  • 您的姓名:
  • 手机号码:
提交

京ICP备05067667号
新东方教育科技集团有限公司

电脑版 | 隐私协议