00:00
同学们,我们继续学习下一个算法,下一个算法呢,叫贪心算法,也叫贪婪算法,那我们先来看一个应用场景,叫集合覆盖问题。用贪心算法解决的问题很多,我们这里以集合覆盖问题来为大家讲解这个贪心算法的使用,假定现在存在下面需要付费的。广播台,比如说有K1 K2 K3 K4、K5是有五个广播广播台,那么每一个广播台它可以覆盖的地区呢?在后面也显示出来了,现在的问题是如何选择最小的广播台,就是找一个最小集合的广播台,让所有的地区都可以接收到信号。大家可以看到K1这个广播台呢,它可以覆盖北京,上海,天津,K2可以覆盖这三个城市,K3K4。K5分别可以分呃覆盖这些城市,问题是我们怎么挑出最少的广播台能够把所有的地区都覆盖,大家可以看到有些地区是重复的,你比如说K1这个广播台呢,它可以覆盖覆盖北京,而K2呢,也可以覆盖北京,对不对?所以它有它有重复的问题,这一点大家在写的时候要注意。
01:23
那这个问题呢,其实就是一个经典的使用贪心算法来解决的,我们先来给大家简单的介绍一下何为贪心算法。同学们可以看到,贪心算法呢,也叫贪婪算法,是指在对问题进行求解的时候,在每一步选择中都采取最好或最优的一种选择,就是我在每一步进行这个选择的过程中呢,我都选最好最有利的这种选择,从而希望导致结果是最好的或者最优的一种算法。那这样讲其实大家也很难理解对不对,所以说待会呢,要要记住案例的,不要着急。
02:04
判断算法所得到的结果不一定是最优的结果,这句话有点不好理解。他这个说的最优的结果,并不是说,并不是说嗯不能满足你的需求啊,就说你刚才说我们要选所有的广播站,能够把所有地区覆盖,这个肯定它是要满足的,但是呢,他有可能在满足你说的这个条件下呢,它有好几种组合。也就是说好几种组合里面,你用贪心算法得到的这个组合不一定是最优解,你比如说考虑到成本,它就不一定是最优最优解了,明白吧,好,所以说我们在后面呢,呃,会给大家详细的说明这个这一句话的含义就是为什么说不一定是最优解,但有时候呢,也有可能是最优的明白。啊,这个后面呢,我们通过刚才那一个广播台覆盖地区给大家进行讲解。后面这句话,但是都是相对接近最优解的结果。
03:04
对,就虽然不是最优,但是已经非常的接近这个最优了,OK,这个呢就是贪心算法的一个介绍,下边呢,我们就要准备直接给大家上一个案例,这个案例就是刚才我们讲的。这一个怎么去选择最少的广播台,能够把所有的地区都给它覆盖了,就这个提这个提议大家明白了吧,有五个广播台,然后呢,每个广播台他们覆盖的地区也告诉你了,现在要求你挑选最少的广播台的集合,能够覆盖所有的地区,就是这个题。那现在呢,我们就来开始分析呗,那如果说你要来做,你会怎么来完成这个题呢,同学们。你会怎么做呢?对,最简单的思路,最简单的思路就是穷举法,是不是同学们你最简单嘛,就说如何找出覆盖所有地区的广播台呢?那最好,最简单最直接的就是穷举,列出每个可能的广播台的集合,这个呢就成为密集。
04:13
这里我们有一个简单的公式可以推断出来,假如我们有N个广播站、广播台,则广播台的组合就应该是二的N次方减一。你举个例子,比如说我们有一个。广播台,那么它的组合情况就是二的一次方减一就是一,对不对,这是正确的。假如我们有两个。广播台,那么两个广播台,比如说是A和B,它有几种组合呢?如果我们选一个广播站,那就是A或者是B,这是两种了,然后ABA2B同时选,又是一种。所以说如果你有两个广播台的话,它的是二的N次,二的二次方减一等于三是不是?如果有三个广播台,大家算ABC,假如我有三个广播台,那它的组合就应该是几呢?就应该是七,为什么是七呢?大家看,如果我们选一个。
05:11
是不是有三种选法?选一个广播台出来有三种选法,那就是ABC嘛,分别ABC,如果选两个广播台,有几种选法,是不是AB1种?AC1种,BC1种,是不是又是三种?如果我们选三个广播台,那就一种,是不是一共是三加三再加一等于七,所以说它的组合应该是二的N次方减去一个一,那假定每秒我们可以计算十个子集,那大家想如果我们用穷举法,它的花费的时间是什么样子的呢?大家来看。如果我们广播台的数量有。有N个,有N个,那有N个的话呢,子集我们是二的N次方减一,因为这个一呢,在N很大的情况下,其实就可以忽略了,其实如果说你不减,你也考虑到我什么都不选,是不是也是一种,也是一种选择方式,对不对?什么意思呢?就说假如假如我有ABC,我换一个颜色,各位朋友,假如我有ABC3个广播台,我还有一种选择,就是我一个都不选,是不是也算是一种选择,那这个就是二的N次方,就不用减一了,明白意思吧,如果说你,呃,你说这个零不算一种选择,那就是减一。
06:30
那不管减不减一,随着这个N值变大,其实这个这个产量本身就可以忽略,所以说他这样子也是没有问题的哈,说如果有五个广播广播台,那么有32个这样的集合,那就是假设十秒,我们一秒钟算十个子集,那就3.2秒,大家看假设,假设你有十个广播站,它的组合就是1024。那么就需要102.4秒,假设我们有32个广播台,大家可以看到这个数量就。
07:01
这种组合就非常恐怖了,因为它是秘籍。那这样子的话,就需要多少时间才能算完呢?13.6年,假如我们有100个广播台,好,各位同学,这个数量级就非常的庞大,因为它已经到了二的100次方了,就很大的啊,很大,那这样子如果我们按一秒钟算十个子集,那就需要这么多年,同学们可以通过这个公式大家得出一个什么结论,就是说在这种进行组合的这种情况下。用穷举法,效率其实是很低的。就很低几乎说。你很难把这个算出来,就是如果按照我们这个算的话,100个广播台的话就需要这么多年,这显然效率很低,因此呢,我们就需要用贪心算法来解决。那至于贪心算法是怎么来的呢?各位朋友这样子啊,我们贪心算法的一个思路分析呢,我们。马上再用一个图解的方式给大家进行一个讲解,大家就会就会非常的清晰好了,那关于贪心算法的一个基本介绍先给同学们说到这一会呢,我们用碳心算法来分析怎么去解决集合覆盖。
我来说两句