00:00
同学们,我们来debug一下我们这一个贪心算法的。代码,那大家看到我们直接把代码呢,先定位到这里,我们来看一看到底它是怎么实现。探寻算法的一个选择。我第八个一半。走一个。好,我们先看此时此刻,此时此刻我们代码定位到了第。56行我们往下走,这个时候里面一个都没有,一个都没选到,现在呢,Temp赛也是一个空。Max max k呢,也是一个空好。现在all always里面有。八有八个城市没有问题吧,往下走,往下走过后呢,我们便利第一次先清空。然后呢,这个地方得到第一个k as里面有三个城市看清楚了,上海,天津和北京,把它加到他赛里面去了。那也也就是说他赛里面也有这三个城市,呃,三个地区,然后呢。
01:05
Temp set和这个all orange进行一个取交集,往下一走,你会发现呢,Temp set现在就已经有三个了,有三个过后同学们可以看到,现在呢,它大于零,并且max k等于空,于是max k呢,就指向我们的哪一个呢?这个时候就应该是8K,就应该是K1了。大家看mak现在已经是K1了,K1过后继续往下走选又清空,清空过后再选择我们下一个K,下一个K呢,就是K2是吧?K2呢,它有又加进这个temp side,再往里面去求交集,这时term side呢。Top里面也有三个城市,但是它并不满足大于的情况,因因此这个mak呢,不会不会进来。啊,这个就跳过去,又到下次,依此类推,好经过它的第一次循环,我们可以看到啊,往下走,第一次循环这个ma k就应该是K1。
02:06
往下走。走。走,注意看现在ma k确实是K1没问题,然后它把这个K1加入到select,同学们可以看到目前S是个空的,往下走一步,它就有一个K1了,看到没有,然后这个时候RORS里面呢,也有八个城市,现在我往下面一走,同学们看到此时此刻只有五个城市了,因为刚才有三个已经被处理掉了,下面继续像这样这样一个流程走,我们再走一个就可以了,好吧,这个时候它仍然是从K1去走,但是这个时候K1。K1,他得到这个or过后,又把它放到了temp temp set,这时他求一个交集的时候,这个temp set里面一个都没有。因为你原先是选了三个出来,但是一求交集。
03:00
就一个都没有了,明白吧,这个时候往下走肯定是不进来,好,第二个来了,第二个是K2 K2里面呢,加进去过后,里面有几个,有几个城市,现在有三个,广州,北京和上海。对,现在澳所有的这个地区里面有五个城市,这个时候它一求交集。这个set里面有几个,有两个,就是刚才我们分析的有两个,现在满足条件吗?大于零肯定是成立的。这个max k呢,还等于空了,现在ma k一个都还没指向任何一个K,所以后面就不用再去判断了,就直接把K2给到这个max k。好给到max k进去了,再接着挑选下一个KK3 K3往下走,K3呢,求一个交集里面也有两个,但是这个时候呢,它并不满足。他这个是不等于空的语音,同时也不满足这个条件,因此呢,并不会去更新我们这个mak仍然保存保存刚才那个K2。
04:00
进来没有进去是吧?好,接着往下走,下面也是一样的,也就是说经过这第二次的大的负循环,你会看到mark markx k呢,就应该是几是K2是不是刚才我们分析的K2,好,K2,然后把K2又加入到我们3SELECT里面去,往下走,现在sex里面有两个了,K1和K2,并且把。这一个MASK2包含的地区再从瑞里删除,那这个时候他应该再删除成都和广州,对不对,因为北京已经删除掉了嘛,这个时候在下一次我们的奥二里面只剩下了大连,杭州和深圳,看是不是这样子的。同学们看是不是?大连。大大连成成都大连和广州,呃,那刚才那个我们看,因为刚才我这个地方说的是有些问题,因为K2里面是这个啊是广州北京,那就去掉广州和深圳对吧,去掉广州和深圳,去掉广州和深圳过后呢,现在留下来的就应该是。
05:07
哪一个呢,就是。我们刚才说的成都,大连和杭州正确的啊,正确的没有任何问题,没有任何问题,好下面就一步步走,就按照刚才我们分析的流程,一步步的清,最后会出现一个什么情况呢?就是all orange里面size等于零,就整个退出,好关于它的一个第八个我们就分析到这里,分析到这里过后呢,我们把刚才的代码讲的贪心算法的一个思路给各位同学整理到笔记中,好我们来看看贪心算法我们讲的是什么内容,捋捋。我们怎么讲的贪心算法呢?首先先给同学们提出贪心算法的一个应用场景,是这样子的吧。来,走一个贪心算法。怎么讲的呢?首先提出了一个集合覆盖问题。
06:01
对,我们先提出了一个集合覆盖问题说。有这么五个广播台对不对?然后呢,我们要选取一个最小的集合,能够干什么呢?能够覆盖所有的地区,这是我们提出的第一个问题,提出来过后呢,我们就给大家说了一下贪心算法的特点。是不是那贪心算法的特点呢?主要有这么两个。有这么两个对,我给他捋了一下。尤其是这一点大家要知道,就是他在每一步选择都会采取一个最好或最优的选择,他每次都很贪心,他每次都想选最好的对不对,好,这就是他的一个特点,然后这边讲完了过后呢,我们就来实际的解决这个问题了。那么我们怎么解决这个问题的呢?先把这个问题再复述了一遍。对,我们先复述了这个问题。好,这边把问题复述了一下,复述完了过后呢,我们就讲了他的一个思路,是不是同学们。
07:06
诶,我们就讲他思路了,把这个王学面挪一下。这是问题的再次复出,然后我们怎么解决的呢?我们先用的是第一个最笨的一种思路,也是最直接,直接的叫做穷举法。叫做穷举法,那穷举法它虽然虽然也能解决,但是我们可以看到穷举法它存在的问题是比较麻烦的,就是什么呢?它会耗费大量的时间,大家可以看到当我们电台有100个的时候,这个需要的时间就已经是这么长了,因此穷句法效率是很低的,对效率是很低的,所以说我们就没有用穷聚法,那紧接着呢,我们就给大家分析了第二个思路,就是用贪婪这个算法来解决,对不对,那贪婪算法的具体的方案是这样子的,来给大家捋到这儿。这是我们的思路分析。呃,这是我们先用的是第一种,给大家来一个这个箭头,好吧,这第一种,那第二个思路呢,我们就用的是贪婪算法。
08:08
他人算法。放到这,那具体来说,我们思路就变成这样子的了。有这么三部。啊四部四部曲就123,第一步干什么,第二步干什么,第三步第四步,第四步就是把123这个步骤步骤反复的。进行操作,直到覆盖了所有的全部地区,我就可以退出了,即我们的一个集合赛制变成零。好的,当这个,那这边我们应该还有一个图解,我把这个对应的图解也拿过来。就是图解思路分析到一个图解,把图解给大家放过这放过来就是这块。对不对,我们这里呢,一边讲一边分析,最后我们得到的结果就是这样子的,是不是K1K2K3K5。我们分析出来的。好,放到这。
09:00
然后把这个分析完了过后呢,我们就用代码实现,具体来说代码在哪里呢?代码就是我们。在eclips里写的great organism这一个代码。把代码呢,给大家放在我们的第一中就OK了。好,同学们,那贪心算法我们就讲到这儿,贪心算法最后呢,还有一个小结,大家说一下注意事项,贪心算法得到的结果不一定是最优结果,现在我给大家解释一下,为什么呢?大家看,就以我们刚才集合覆盖问题,我们选择的结果是K1 K2 K3 K5,它覆盖了全部地区,但是你们有没有发现?K2K3K4K5其实也是可以的。就说我们K2K3 K4K5也可以覆盖全部地区,你们相信可以自己去试一下。那虽然你这个贪心算法算出来结果确实满足需求,但是人家这个也满足需求,那就出现一个新的问题了,什么呢?
10:02
那哪个更好呢?哪一个更好呢?好这个地方就不好说了,假如我们说K2使用的成本比K1低,比如说K2。我们考虑成本,K2这个广播电台我们要我们要去使用的话呢,它需要一个月100块钱,而K1它需要多少钱呢?K1比如说需要一个月200块钱,这个时候如果从更优的角度来来看的话,那K2 K3 K4 K5这种选择应该更好,因为它便宜嘛。对不对,所以说如果在这种情况下,如果说K2的使用成本比K低,那么我们K1 K2 K3 K5虽然满足条件,但并不是最优的,他说的最优和不是最优主要是取决于这点,因为你他的算法得到结果虽然满足条件,但不一定最优,当然也有可能是最优,为什么呢?假如你这个K1的使用成本高于K1,呃,K2使用成本高于K1,那我们。这个用贪心算法得到的结果反而就是最优的,因此他说的是有可有时候会最优,明白就是这么一点,同学们知道这个就可以了,好吧,OK,那现在呢,我把这一个注意事项也给各位朋友板书到我们的笔记中。
11:17
OK,那写到这里。那具体来说,我们这儿总结了。这么几点是不是同学们?各位,那关于贪心算法的小结和注意事项就给大家聊到这里。
我来说两句