00:00
各位,我们现在呢,换另外一种思路来分析刚才的集合覆盖问题,我们用什么算法呢?我们用贪婪或者叫贪心算法,这种算法呢,效率就比较高了,我们来先来看思路同学们。目前并没有算法可以快速的计算得到准备的值,我们现在使用贪婪算法,也叫贪心算法,则可以得到非常接近的减,并且效率较高。选择策略上呢,因为需要覆盖全部地区的最小集合,所以说我的这个步骤是这样子的。注意听哦,这个文字讲完了过后呢,我们再给大家图解一把,大家不用着急,这个肯定要让大家听懂的,对不对?第一步便利所有的广播电台,找到一个覆盖了最多未覆盖地区的电台,这句话什么意思啊?找到一个覆盖了最多未覆盖地区的电台,也就是说你现在找一个电台,这个电台可以覆盖你现在还没有覆盖地区。的这种电台就是我们要选的,那么这个这个电台有可能它覆盖的地区,你在前面已经覆盖过了,这是有可能的,但是这个没有关系,重复这是有可能的,也就是说我们在选电台的时候,你选K1 K2 K3,有可能有有两个或者三个电台,或者是多个电台,他们有重复覆盖地区,这个是没有办法避免的,明白吧,这个是在探析算法,是没有办法避免的,而且在实际情况下呢,如果你给的这个电台情况。
01:29
嗯,不同的话也基本上无法避免,第二个呢,第二步我们将这个电台就是刚才第一步选选到的电台加入到一个集合中,比如比如说是a list,然后想办法把该电台覆盖的地区在下一次比较时去掉,因为为什么要去掉呢?因为你你刚才选的这个电台已经覆盖了这些地区,所以说在下次再找的时候呢,就要把这个已经覆盖的地区从。从这个选择的这个地区里面去掉才有意义,第三第三步就是重复第一步知道覆盖了所有的地区,大家听懂了吗?
02:06
我估计啊,大部分同学也不太知道老师在说什么,因为这个文字它特别的不形象,那这样子吧,同学们,我给大家画一个图,帮助同学们理解,打开我们的Excel。来给同学们讲讲我们这一个叫做集合覆盖问题的贪婪解法的思路,叫集合覆盖问题。使用。使用什么呢?OK,使用贪婪贪婪算法。解决的思路图解,OK,同学们跟上我的思路好吧,嗯,首先呢,同学们可以看到在我们,诶博士这边啊,再打开我们的幻灯片。我们首先要看一下,目前你的这一个电台呢,一共有五个,他们分别覆盖的地区是这样子的。
03:00
是不是好?第一步我要做的事情就来了,我要做什么事情呢?我要先挑选出,注意听这句话。我要先选选,我要先选出到底有一共有哪些地区,也就是现在还没有覆盖地区,我写一个变量叫all。Ors?这个里面的集合应该是什么呢?就是这个表示,表示需要覆盖的所有地区。这个能理解,那我们一共有几个地区,我们可以看一下。前面这三个北京、上海和天津,注意听讲好同学们。这是我们需要去覆盖的。这是三个。对吧,那紧接着呢,我们再来看广州,北京和深圳,这又是三个城市。这是不是三个城市啊,同学们放进去,但是这三个城市里边呢,有一个北京已经是前面。
04:00
已经选出来的,所以北京呢就先去掉。紧接着我们再来看,往下看下面成都上海和杭州成都上海和杭州,那么我们也把这三个城市拿过来。好,我把这三个城市放到我们的这边,注意听好,但是这里面呢,上海在前面已经出现过了,所以说把上海去掉。没问题啊,同学们好。往下看。往下看,接着再往下看上海和天津,上海天津在前面已经我们已经挑出来了,杭州和大连好多大连没有挑出来,把大连也加进去,各位同学注意听。待会主要看思路,思路有了代码其实并不难,同学们帮着老师数一数,我们一共有几个城市,一个两个,三个,四个,五个,六个,七个,八个,OK,这是我们将来要去选的电台,要把这八个城市都覆盖掉是不是好?现在呢,根据刚才老师的思路。
05:03
我呢,需要去根据刚才我们的思路是这样定的,对不对。我需要定义一个集合。到时候要把。要把这个选中的电台加到一个list里面,所以说我呢可以先在这定义一个变量,比如说这里面有个集合叫select。就是将来呢?Select,这是我将来要选择的一个集合,它是一个list。Or released?好,为了让大家看的比较形象一点呢,我用一个这样的把它标出来,大家明白这意思吧,好,这是待会呢,我们我们这个呢,就就这个集合。好的,现在呢,我们就可以开始来玩了,现在我们就可以开始来玩了,怎么走呢?注意听啊,首先我们便利这个广播电台,你有多少我们就便利,我用一个绿色的线表示,大家可以看到。
06:01
我遍历K1的这个电台的时候,我去看当前我这个K1覆盖了你这个奥list哪些城市。是不是刚才我我说的这个步骤,先去遍利所有电台找到一个,找到一个覆盖了最多未覆盖地区的电点电台,然后把它加到我们里面去,比如现在我要便利这个电台,把这个找到一个覆盖了最多未覆盖地区的电台,明白我的意思吧,好,我的思路呢,就是这样子的,那就老师那你那你接着说吧,那么看啊,K11它应该覆盖了几个。北京上海和天津,说他K1,它应该覆盖了有三个。我先寄到这里好吧。我先接到这里,紧接着往下移动,我看K2覆盖了几个城市呢?广州,北京、上海,它也覆盖了三个城市。它也覆盖了三个城市,是这样子吧,同学们你想你现在你现在这个K2这个广播电台呢,它也覆盖了三个城市,北广州北京上海,因为你上面有八个嘛。
07:06
那一数,这个一比较就能比较出来。K3K3B覆盖了几个城市呢?各位同学,K3这个电台呢,它也覆盖了,注意听啊,它也覆盖了三个城市,没有问题吧,往下继续移动,K4覆盖了几个城市呢?各位同学。K4,它覆盖了两个城市。它覆盖了两个城市。好的,那接着往下,我把这个换一下,这个就是覆盖了两个城市,接着看K5 K5覆盖了几个城市呢,同学们。K5呢,它也覆盖了两个城市,好,我想罗同学们想一想,此时此刻你能不能挑选出哪一个是最大的,因为待会你你你在这个进行遍历的时候,这应该也有个指针在跟你进行比较嘛,或者说进行一个一个一个探探测。那现在呢,我们通过这个比较,我们发现K1它有三个,K2也有三个,K3有三个,那也就是说其实第一个K1选中的其实就已经是这一次便利的最大的,明白我的意思吧,好,那也就是说待会儿呢,我会用一个指针或者一个索引指向这个K1,这个K1呢,我们给它取个名字,我用一个这个颜色表示,取个名字叫什么呢?叫做max k。
08:26
诶,这。这某。怎么写成这个样子了?那也就是说我在这个地方呢,会有一个标有有一个索引,这个索引我们取个名叫max。注意听啊,Max k,那也就是说经过第一轮循环,我们发现K1就是这一次循环里面最大的。是吧,那这个是什么呢?这个绿色的在移动过程中,我们也可以给它取个名字,就叫K啊,它它是指向这个当前这个K的,好了,那这次完了过后,我们就发现max k max k是几呢?K1,于是我就把K1放进去。
09:04
放到我这个select集合里边去,明白好,放完了以后呢,这个max k呢,我就把它制空,让它布置向任何地方,紧接着进行下一轮,在进行下一轮之前,同学们是不是你当然北京上海和天津就已经。已经有一个电台把它覆盖了,这时注意听这句话,要想办法把该电台覆盖的地区在下次B中去去掉,也就是说你下次做的过程中呢,要把这几个去掉。注意怎么去掉,用代码是可以很容易实现的。就完了,是不是现在我们再次比较的时候就只剩下了这几个好,现在呢,我们接着往下走。好,又进行一的比较,又进行KE1比较,其实这个K1呢,其实可以把它把它抛,把它想办法把它把它去掉啊,但是你不去掉也无所谓,因为这一次比较这个并不会花费太多的时间,因为它是一个常量级的嘛,对不对,常量级的他是个常数,这个无所谓,好那K1现在能覆盖几个呢,同学们。
10:10
K1现在只能覆盖几个了,零个了,能理解吧,为什么呢?你想想你刚才把北京上海天津已经去掉了,你让这个KK1。它覆盖的地区跟当前这个凹。Or errors比较它肯定一个都不覆盖了嘛,紧接着呢,我们让这个K继续往下移动,K2能覆盖几个呢?广州北京上海是不是它能覆盖两个呀,广州和上海,广州和深圳它是可以覆盖的,于是这一次它覆盖了两个,明白,好,紧接着往下继续移动,K3 K3它能移动,它能覆盖几个呢?成都上海杭州,成都有上海没有了,杭州也有两个,所以说他呢,也能覆盖两个,能理解,好,紧接着各位朋友接着往下继续走。
11:00
继续走,那K4能覆盖几个?上海没有了,天津也没有了,这个哥们只能覆盖零个,明白我的意思吧。好,紧接着这个K继续往下移动,杭州。和大连,杭州和大连是不是两个还是两个好?同学们想,这一次我们最大的是哪一个呢?K2是不是也就是说这次max k呢,就可以指向这个K2了。因为K2在这里面是二,没有哪个比他更大,说老师下一个跟他一样大,一样大,也没有比他大嘛,你这是跟他一样大,但是你没超过他呀,所以说这次呢,我们把K2又扔到我们这里面去明白。K2放进去,K2放进去以后好,然后呢,我把这个max开又吃空。自自空,自空以后,同学们在下一轮比较的时候,我们这个K呢,又要开始比较,从K1比较。我说了啊,你可以去掉,但是因为一次比较并不会说浪费太多时间,这个问题不大对吧,你去掉也可以,你不去掉呢,对你效率也没什么太大影响,好,那这个时候你在进行下一轮比较的时候,你要把谁去掉,是不是要把K2覆盖的地区又要去掉,K2覆盖的地区刚才已经算出来是广州和深圳,你刚才K2是不是覆盖是北广州和深圳,因为北京上一次人家就已经去掉过了吗?现在你在进行下次比较的时候,你要把广州和深圳拿掉,广州和深圳拿掉。
12:28
拿掉了,各位朋友。OK了,好,这个时候。K1覆盖肯定还是零,往下继续移动。K2现在覆盖显然肯肯定也是零的,这个没有什么可说的对不对,接着继续往下移动,K3呢。K3有成都哦,OK,你看这个时候K3它是两个。因为现在他成都和杭州是不是能覆盖,紧接着往下继续移动。K4肯定那一找他上一次都已经覆盖零个了,这次必然也是零个,继续往下移动,K5覆盖几个呢?它也能覆盖两个,对吧,但是大家想想一想,因为K3能覆盖两个,你也能覆盖两个,那显然我。
13:13
让max指向谁呢?指向K3,这个很好理解,为什么呢?诶原因很简单嘛,就是你你虽然是两个,我也是两个,你没有比我大呀,所以说我这个max k呢,就指向第一个就行了,这时我们把谁又放进去呢?各位同学,这时我们把K3又放入了我们这里面。好了,K3放进去过后呢,这个ma自空自空过,这个又来开始一轮循环,在进行专轮循环之前呢,把K3覆盖的地区又拿掉K3 K3刚才覆盖的是成都和杭州,所以拿掉了,明白。拿掉了啊,各位朋友拿掉了,拿掉以后这时K0显然是零。K1也是零,K3显然也是零了,对不对,K4。
14:02
K4,显然这个他一个也覆盖不到。然后K5 K5能覆盖一个。K覆盖一个,K5覆盖一个的时候呢,显然这时我们就把K5又装到我们这个select集合里边去理解。好的,现在。那当然我这还有个动作啊,肯定也指向它了,指向它过后把它放进去过,让它滞空,滞空过后呢,再去移动,再移动的时候,是不是我们又把这个大连从这边去掉,大家想这时还需要再便利吗?还需要再便利吗?没有必要再便利了,因为我这个ALL2ALL已经是你的,也就是说经过我刚才的一系列这个贪心算法的一个操作,我的select这个集合里面选中的电台已然覆盖了所有地区,因为你这个r r all r已经没有任何的电台了,呃,没有任何的地区了,最后结果就是K1 K2 K3 K4,答案就这样子得到的。
15:02
大家看这个流程理解了吗?这就是我们所说的用贪婪算法来解决集合的一个经典的使用,其实大家有没有看到它总是他在这里面,每次总是选一个能够覆盖到最大未覆盖地区的这个电台,这就是贪婪算法的一种体现,就是我每次去选,就是我每次就选一个最优的,就这句话的理解。哪句话的理解呢?各位同学,就是这句话,就是他们在每一步选择。中都是采取最好或者最优的选择,就是我我便利一次,在整个便利一大轮的时候,我选的是一个最好的,能够覆盖最大的一个地区的,对。就是这句话的一个理解,OK,好的,那同学们现在呢,我的这一个关于用贪心算法去解决集合覆盖问题的一个图解的思路就给同学们聊到这里,大家看理解了没有。
16:03
一会儿呢,我们就用代码把这个实现一把。其实你理解这个思想以后,用代码实现应该说并不是很难,是不是并不是很难?OK,那关于判断算法的思路图解就给同学们聊到这里。
我来说两句