00:00
同学们,我们对前面讲的马踏棋盘算法的代码进行一个优化,那优化的原因我们来了解一下。分析第一种方式,我们代码已经实现了,下面呢,我们要用贪心算法来进行优化,大家可以看到我们的问题在哪里。我们的问题是这样一个问题。同学们想。因为目前我们在采用这一个。马儿走下一步的时候是按56701234走的,这样子做呢,他并没有考虑。就是说我们应该走哪一步,其实刚才老师已经讲过了,如果说我们这个马儿在走的时候呢,先走的是这样一步,下一步的下一步,他选择越少的,那么这个效率就会越高,因为你的回溯的这个机会就会越少嘛,可能很快我们就找到了一条一条线。
01:03
就把这个问题解决了,明白我的意思吧,所以说我的思路是这样子的,我先把思路给同学们说一下。就是我写在这儿使用。使用什么呢?使用贪心算法。算法对哪里呢?对原来的这个算法优化。优化怎么优化呢?第一步,第一步首先我们要考虑就是。我们在这里考虑。同学们看。我们在进行马这个马踏棋盘的时候,我们拿到了一个,比如说我们获取到了最听。我们。我们获取到,获取到当前这个位置可以走的所有所有所有可以走的下一个位置的集合。是不是我们这儿已经。
02:01
得到了呀,这是我们前面已经做过的,现在我们要完成一件什么什么事情呢,我们需要注意听,诶,我们。我们需要对这个。它的什么呢?最新的下一步。下一步。的所有就说不是它的,它也是点吗?它是一个点的集合,那中所有的点应该这样说中所有的point。的下。一部的所有。集合的个数个数或者叫数目,数目。进行什么呢?OK,进行非递减,非递减排序。
03:01
大家知道我在说什么吗?就是我们这个下面我们这个S不是有很多的可以走的位置吗?那么我们要对他的每一个位置的下一步可以走的这个位置的数目进行非递减排序。就可以了,就OK。就OK了。明白我意思吧,什么叫非递减?我简单的介绍一下何为非递减,所谓所谓非递减指的是这个意思,大家先看一下递减是怎么写的。三比如说我写个角。七。六。窝。三。二一好,这个我们就称之为递减。这个就称为递减。递减排序。这大家知道为什么叫递减吗?啊。啊,这个叫非递减啊。我们叫。
04:00
就是这个叫递减吗。这是不叫递减,就是你你这个是从大到小就叫递减,我们看递增是怎么写的,一。二三。456。好,十这个就是递增。递增排序。好,我们看看非递减是指的意思,什么意思?非递减指的是这个意思,同学们。非非递减。他是。指的这样一种概念,非递减啊,就是一。二。223,再来一个三。456OK,同学们,这个就是所谓的非递减。什么叫非递减呢?他他就说在这个过程中,他他允允许你有重复的数字。那么非递增也是一样的道理了,非递增就是在递增的过程中,在这个非递减就是说我在这个递,在递增的过程中,我允许有重复的这个值。
05:06
那么非递增呢?我们再来举一个例子,非递增,大家了解一下这个概念就可以了,好吗?非递增?递增非递增,就是说当我在进行这一个。减的时候,比如说。就以这个为例吧。对,这个是不是本身它是一个递减的模式,它是一个递减模式,那么如果这个是非递减,它就意味着在我进行这一个排序过程中,我可能会出现。两个六。或者三个六,然后呢两个五。这个我们就称之为非递增,因为在它递减的过程中,在它递减的过程中,它允许有重复的数字,重复的值,好,这个就叫非递增,上面这个叫非递减,明白了吧。哦,非常简单,你看不是增加吗?它不增加,但是它允许有重复值,好,我们只需要对这个中下所有点的下一步所有集合的数目进行一个非递减排序就可以了,这样呢。
06:11
做了过后,我们这个马儿先走的就是哪一步呢?先走的就是他的下一步的下一步集合最少的,这样从而减少我们回溯的这种可能性,明白了吧,好,代码非常的简单,来各位朋友跟上我的思路,那现在呢,我先写一个方法。大家看这个方法非常简单啊,我写一下根据根据当前这一步。这一步OK,根据当前这一步的所有,对所有的下一步。下一步就是当前这一步的所有的下一步的选择数目,选择位置,选择的位置干什么呢?哎,进行非递减非递减排序。
07:05
好,同学们一看就能看懂,那现在呢,我们这样做哈,Public public static shop,那你给我传一个什么进来呢?同学们,你把这个r list给我,我帮你进行一个排序,明白意思吧,Point PS,怎么排序呢?好,非常的简单。非常简单,我把这个的sot进行一个重写就可以了,大家看,呃,我想想怎么写比较合理啊。就是这样写的PSDSO。好。里面呢,它其实。我们这样写啊。点so,它本身一个so是吧。本身一个so的好,这样写在这里面呢,我们就把这个so重新写一遍,怎么写六一个来跟上我的思路,那六一个什么呢,六。
08:00
一个compar。Comparer就是一个比较器,这里面呢对pointer进行一个比较明白。好,写上写上,完了这边一对大括号。诶,这边我肯定要引一些东西进去了,对吧,我把该引的包引进去。Compar。Comp营销包。点一下诶,它有位时间方法写进去吧,那这里面是不是把compar这个方法,咱们给它进行一个重写就OK了,这地方为什么不行啊,Or point or point这个地方。OK,这地方忘了有一个写返回值了的,我们不需要返回任何东西。那么现在基于这个非递减排序,你怎么来做呢?同学们,首先我们第一步来,同学们一步先获取。
09:02
获取。获取到,获取到什么呀,就是OE这个点的。点的下一步的下一步。的所有位置的个数,能理解我的意思吧?那这个很简单,咱们这样写就行了,Next这个方法不是有了吗?把OE填进去。OE,这个O1到时间,其实就是我们or list里的一个一个一个点,明白了吧,相当于说对于这个or list里面的所有的点位置。在呃,就说对list里面所有的位置,再求它的下一步的位置有哪些,明白了吧,好,然后呢,这边我们有个size。好,因为我要求它个数嘛,所以说我用这个接收一把我写成COUNT1。理解了同样的道理。我们在对O2获取O2。
10:02
对,获取O2下一步的所有位置的个数,那当然这边应该改成o o2这边呢写成COUNTR2就可以了,下面呢,我们就进行一个处理,怎么写呢?如果B要被递减排序,如果COUNT1小于COUNT2。CTRL2,在这种情况下呢,我们就返回一个负数。OK else if else if,如果说我们这个COUNT1,它等于COUNT2。相等的情况下怎么办呢?OK,那这个时候就无所谓对吧,就保持原来顺序就可以了,返回一个0ELSE。就说反过来了,是我们C1大于了CT2,那这个时候我们返回一个证数一就可以了。明白同学们,也就是说这段代码重写了以后呢,我们list里面的。Or里面的这个元素就按照。
11:03
按照什么呢?按照这它的每一个元素的下一个所有可以走的位置的个数非递减排序了。说的再直接一点,就是我们先走的是,呃,走的是哪一步呢?走的是他的下一步的可选性最小的这一步。这样就减少我们。这个回溯的可能,它主要是减少回溯,回溯OK,回溯的次数啊可能。OK,那同学们这个代码写完过后在哪里调呢?其实非常的简单啊,各位朋友,其实我们只需要在这里做一个动作,就是你原先这个PS next的时候,你你就是按照我刚才那个方法里面写的嘛,现在我们把它进行一个排序就行了,对什么呢?对进行排序,排序的规则啊,排序的规则就是。
12:01
就是对的,所有的,嗯,所有的这个元素的的那个什么的那个。呃,元素所有的pointer pointer这个对象。对象的下一步的。而位置位置。的数目的数目进行进行非非递减排序,就这意思。非递减排序。好了,那这样写完以后呢,我们直接调这个sort方法,把这个sort方法里面放这个代码就写完了。代码就选这是好,同学们只需要做这一个动作就行了。那有些同学你这个管用不管用呢,来玩一把,首先呢,我们把这个已经换成了8811。好,瑶瑶,那我跟他说一下啊,因为我这里用了这个不同的顺序,大家问问大家一个问题,因为我现在用的策略不一样了。
13:06
用的策略不一样了,请同学们回答,老师,就是我不同的策略是不是意味着我将来得到的这个解,就是我们最后这个码应该怎么走,可能就不一样了,这个能理解不?就跟我们小老鼠走迷宫一样。你如果是先上。呃,在下在左在右是一个结果,如果你是先左右再上下,可能又是一种又是一条路线了,这个我就不不说了啊,就说你待会儿你待会儿会,如果你看视频的话,你会发现我用这种方式。嗯,他的他得到的跟以前那个可能不一样,但是速度会很快,好同学们我们运行一下,看看效果如何,运行之跑起来。好多一看一下就出来了。108。也也就说是我们是八乘以八的这么一个棋盘,计算也是一秒不到就算出来了,如果同学们看可以看到,假如我把这个short去掉了。
14:06
加,因为这个是贪心算法嘛,贪心算法是什么意思呢?我尽量选少的嘛。诶,以前你是探析算法是尽量选U的,就我在下一步总是选U的这一点进行一个测试,而这个时候最优呢,就是选它的下一步的,下一步的位置是最少的那点来进行测试,如果我把这个去掉,你看速度又变慢了。跑起来,你看。同学们看我没动哦。是不是没有出来呀。你看又得大概30秒才能出结果,但是有时候运气不好的话,可能还要超过30秒呢,你看现在还没出来。看。是不是现在还没出来啊。那出来的时候可能就是30秒或者40秒以后了,你看我把这个再再把这个打开。再把它这个打开,我再运行啪出来了,比刚才还快了,而且这个结果一定是正确的,因为算法我们刚才已经验证过了,没毛病,好同学们,这就是我们算法优化的力量,就说你用不同的方法来进行这个处理,其实其其实这个效率是差异很大的,对不对,我用了。
15:16
贪心算法进行优化,速度啪就出来,如果不用,那你这个39秒相差很大的哦,原先是39秒,现在一秒都不到。好的,同学们,那关于我们用贪心算法的一个优化的解决方案呢,就给同学们讲到这儿,大家应该能理解了。好,现在我们花一点时间把我们讲的这个马踏棋盘的整个思路给各位同学进行一个简单的板书来吧,打开我们的笔记,打开我们的笔记,OK,那么我们看看马踏棋盘我们是怎么讲的。来,首先呢,我们先给同学们提出了马踏马踏棋盘的算法,也叫骑士周游算法啊,骑士周游算法一样的,呃,不管是马踏棋盘算法还是嗯嗯,其实周游算法都是这这么一个意思,不同的地方可能不同叫法,好,那现在呢,我们先把这个写到这里来。
16:12
早。对。我们先把。笔记给大家摆一下,往下拉。好的。放到这儿来。马踏棋盘算法。那么马来棋盘算法,我们首先有一个小游戏引出大家对这一个问题的思考,是不是我们先用了一个游戏引出这个问题?但这个游戏呢,同学们自己也可以去玩一玩,看看你自己能否搞定对吧?好,这是这么一个游戏,这个游戏呢,我把它粘过来啊,有这个游戏引出。我们要思考问题。当我们把这个游戏提出来过后呢,我们就直接比较干脆啊,我们就直接说这这个马踏棋盘算法的一个代码实现是什么样子的,是不是就直接上代码了,但是上代码这个过程中呢,我们实际上是是做了一些分析的。
17:07
来看一下。首先在哪里先分析的呢?就是在这个位置,我们先做了一个思路分析。对,我们第一种方法先做了一个思路分析,就写到这啊对,第。第一种第一种实现实现方式的思路图解,还记得吧?诶,这个图解是不是就在这里,还放这呢,我把它拿过来好吗?好,这是我们的一个思路图解。给同学们放到这儿来。大体来说就是我们这样几个步骤。第一部第二部第三部第四部。啊,OK,这是我们对第一个方案的。思路图景。那当我把这个讲完了过后呢,我们就把代码写了一遍,对不对,我们把代码写上,写完了过后发现有问题,发现有问题呢,我们分析了。
18:01
用贪心算法应该如何优化,我们也把思路呢,写到这个位置的,还记得吧,诶,我们就这样子的这做了。用贪心算法对我们原有算法优化的一个分析,其实说白了就是我们走的下一步呢,尽量让下一步的下一步的选择越少,从而可以减少我们回溯。好,这是我们的。一个思想,当我们把这个思想说完了以后,是不是整整体这个代码就做完了。好,最后代码实现。那代码实现呢,我们就是这个文件拿过来就可以了,朋友们放这。好的同学们,这个就是我们马踏棋盘算法的一个讲解,大家看听懂了没有?好吧,那不管你呃掌握的情况怎么样,我建议同学们多看几遍,多看几遍已经就可以搞定,OK,关于这一讲,我们就说到这里。
我来说两句