00:00
同学们,我们继续来学习下一个算法,下一个算法呢,我们称之为分制算法。这个分支算法呢,他在我们这一个解决实际问题的过程中,使用的频率也是非常高的。那刚才我们讲的这个二分搜索,其实它也是属于分支算法的一种。或者说是分支算法的一种具体体现,那么我们看分支算法是一个什么样的东西呢?分字法是一种很重要的算法,从字面上的意思理解就好,就很好,用我们中国的一个词语来说叫分而治之。它是什么样呢?就是把一个比较复杂的问题分解成两个或者更多的相同或相似的子问题,就是把一个复杂的问题呢分解。把这个问题子问题分解成更小的一个子问题,直到最后这个子问题很容易求解,就这个它问题很复杂,但是呢,你把它分解成小问题过后,你会发现这个最小的问题它是很容易把它解解决掉的,然后原问题的这个解集子问题解的一个合并。
01:09
就说打个比方,我们要做一件事情。我们要把一个大象。放到冰箱里面,这是一件很复杂的事情,但如果说我们把它分成三步就很简单了。把冰箱门打开。把大象塞进去,把冰箱门关上是吧,问题解决,那也就是说实际上我们一个复杂的问题呢,你要把它分解成小问题,而这个小问题往往它也是一个循环,第一循环的一个过程,很多问题都是这样子的,当然我们要觉得分支算法的一个最佳时间就体现出这个特点。他就说把原问题的这个子问题的解进行一个合并,它就是最后我们这个分分制算法。的一个结果,这个技巧呢,是很多高效算法的一个基础,比如说同学们在前面我们讲过的快速排序,归并排序,包括傅立叶变化,那么这些呢都会用到这个分支算法。
02:04
分而治之的一种特性。都是把一个。解大呃,复杂的问题,分解分支算法,除了刚才讲的这些呢,它还有一些求解的经,还可以求解一些经典的问题,比如说二分大整数。的一个乘法棋盘覆盖合并排序,快速排序,线性时间选择,最接近点点对,最接近点对问题,还有像循环赛,循环赛的一个日程表也可以用我们分支算法来解决,汉诺塔,待会呢,我们就用汉洛塔来实际的体验一下这个分支算法的特点。关键这里面分支算法最难的地方就是你怎么把一个复杂的问题。OK,把它拆解成一个小的问题,这个分的过程其实是需要动脑筋的。也就说你能够有一种能力,就说你作为一个程序员来讲,你你能够把一个复杂的问题分解成小问题,然后这些小问题有很多,那么把小问题再合并成最后一个结果就是我们的求解。
03:11
这里面还是涉及到自身的一个思想,就是你你在写这个代码的时候,你本身是很清晰这个问题怎么解决的。OK,好,那么我们来看一个公式,关于分支算法的,它的一个基本步骤分成几步呢?呃,它是这样分的,他说分次,分次法呢,在每一层递归上都有三个步骤,基本上都有三个步骤,大会可以看到。分解,即将原问题分解成若干小的、相互独立的,与完原问题形式相同的指纹体。就打个比方,比如说我们汉洛塔要把64个盘。移到另外一个柱子上去,那你先不要考虑64个,你先考虑一个盘怎么放,两个盘怎么放,三个盘怎么放,你就把规律找到了,好解决,将若若子问题规模较小而容易被解决,就直接解决,如果否则的话,就递归解决各个子问题。
04:04
你看这个地方就体现出什么什么特点呢,待会我们去搬这个金字塔,如果只有111个盘,一下就搬过去了,那如果只有三个盘,是不是你要用递归的形式来各个解决啊,诶就这意思,合并呢,就是把各个子问题的解合并成原问题的解。当然这个讲的比较抽象哈,我们来看一下它的分制算法的一个设计模式是怎么。去处理的。那分子算法的它一个模式是上,如果这个P,这个P呢,代表我们问题的一个规模,如果这个规模它小于等于一个N0 N0呢,N0是代表一个这个阈值的。就说当我们这个问题P的规模不超过N0的时候呢,问题就已经很好解了,这个时候就可以把这个结果返回。也就是说,当我们分解到一个比较小的规模的时候,你应该知道这个就怎么解决。
05:00
OK,就好像我们汉洛塔,你最简单就是一个盘吗?把一个比如说我们汉洛塔,把汉洛塔是前面已经讲过,有有三个柱子,这是A柱B柱,这C柱对吧,那你最简单就是把一个盘挪到C盘,这个是不是最简单的呀。是不是这就可以直接返回结果了?呃,那么不必再分解,就是已经最简单了。这个就是它的一个基本的指算法。那么用于直接解决跟小规模P,因此当P的规模小不超过N,直接就求解算法这个merge呢?大家看merge merge y1 Y2 YK是分支算法的一个合并过程。合并的过程,若用于将P的P的子问题P1 p2PK相解的Y1 Y2 YK的进行一个合并,整个合并过后呢,就变成我们这个P的解啊,这个还是说说起来是有点抽象对不对?同学们可能还是不太明白这个东西到底怎么分,我刚才讲过了分制算法其实并不难理解他的思想。
06:07
大家都知道,把一个问题拆解成一个小小的规模,然后求解,拆解到最小的规模就是最最简单的一步嘛,但是大家最觉得最难的过程就是怎么能够把它拆过去,是不是好,待会儿呢?我们就举一个实际的案例给大家实际的演示一下如何分,如何治。好的,那对这个关于分支算法的一个设计模式,先跟大家聊到这里。
我来说两句