00:00
同学们,我们继续来看迷宫问题的下一个要讨论的点,那刚才我在讲到哈,就是我们这个迷宫问题呢,它存在一个最短路径的问题。就是说在我们没有学专门算法的时候呢,仍然会有一个最短路径的问题,就是说这个小球它怎么走路径是最短的。明白我的意思吧,那你要得到这个最短路径。从目前来看,如果我们没有学更好的优秀的算法,那么。我们有一个方法可以得到最短路径,就是改变这个策略。也就是说,小球得到的路径和程序员设置的找路的策略有关,即找路,我们前面在这走的是下右上左,我们得到的这个路径我们来运行一下。我们得到路径是是不是这样子的。
01:00
诶诶,对,不好意思啊,刚才呢,我们把这一个挡板没有撤掉。把这个挡板撤掉,我们再运行。同学们可以看到,我们得到路径是这样一条线。对不对。因为你的策略是这样定的,那同学们想一想,如果我改变这个策略,是不是他得到的小球出迷宫的路径就会发生变化呢?肯定会变化。因为。你找入的策略会跟会影响到你得到的这个路径,那么我们来做一个修改。来做一个修改,我们来试试啊,那同学们看,我们先前呢是下右向左,现在我们改成上右下左,先是下右向上左,我们改成先往上找,然后再往右边找,再往下边找,再往左边走,我们看看路径有没有这个变化。有没有变化,来我们看一下,那现在呢,我们这样子啊,我们不去。
02:03
在这个原先的方法在改,因为这样改大家以后呢,看代码看起来很累,所以说我们干脆呢,这样子把这段代码拿过来。拿过来我们做一个说明,修改策略,修改找录的策略。策略我们改成什么呢?我们改成这样一个策略。改成刚才老师所说的先上。在右。OK,再怎么样呢,在下在怎么样在左。OK,那这个时候呢,我们看看这个代码应该怎么修改,然后看路径找,然后呢,我把这个改成二。这个传入的参数无需修改,退出的条件无需修改,那大家想,现在我们改的策略是这样子的。对不对,那首先我们先走上面,大家想先走上面,是不是把这个I改成。I减一就可以了,这个就是向上走,因为你向上走的时候,实际上是这个行。
03:07
它是减小。是不是向右走没有变化,向上走改成向下走,那向下走的话,这个I应该改成加。是这个意思吧,改成加,改成加过后呢,向左走不需要变化,不需要变化,因此我们其实改动的地方只有。在调我们这个方法的时候进行修改,当然你这边改成set v2了,你在进行递归的时候,是不是也要改成set v2这个方法,不然的话你还是指的以前的对不对?好,这样改完了以后呢,同学们,我们再来调用一下,我们发现路径发生了变化。那这个时候我修改策略。我调用刚才我们写的方法叫sideway。二传进去的参数呢,跟上面一样,仍然是传着一和一,我们运行之,这个时候我们先不去看执行的结果,我们先分析一下它应该是怎么样子的,来我们简单分析一下,如果是线上上向上。
04:13
啊,先先先先向先,我们现在是先向上走是吧,先向。上走先向上走了上面。走不通,因为改成上右下左嘛,走不通向右。向右这个是不是走通了,于是这个变成二,在这个点是不是也是先上上没有走通,向右走通了又变成二。这个地方来了,先是这个位置先上走不通,向右右走通,又可以向上走走不通,向右走走通,这个向上走走不通,向右走走不通,应该往哪走了,向下向下走通了吗?走通也就是在这地方,他探了两下,但是没探通,在这是不是又向上走,但是这二已经走过了。
05:00
不走了,往右走,走不通,往下走又走通。是不是这一一个逻辑到这儿到这儿。到这儿,也就是说如果我们是上右下左整个策略室。通路是这样子的,明白我们运行这个结果,看一下,证明一下。同学们看,我们得到的这个结果跟我们刚才分析的完全一样。所以说同学们可以看到小球走路这个策略不一样,我们得到的路径就不一样,那么同学们,我给大家出一个题,出一个题请思考如何求出最短路径。就说怎么走,这个路是最短的。那这个题呢,其实也很好解决,在我们没有学更好的算法的时候,你可以通过对这一个策略的一个改变,就是把这个可能的策略,咱们用一个算法设计出来,你可以设计成一个数组嘛。就是你用一个数组来表示它不同的策略,然后用一个for循环把这几个策略走一遍,然后将我们每一个,呃,这个二。
06:05
这个节点保存到一个集合中,看哪个集合的大小是最小的,就是最短路径,那个策略就是最好的。这题留给同学们去思考啊,并不难,再说一遍并不难,刚才我已经讲了,就是把所有的策略用一个数组的方式把它表示出来,然后把每一个策略得到的这个节点进行一个统计,或这个二这个点有多少个进行统计,最少的那一个集合就是最短的路径,明白。好,那现在呢,我们这个迷宫问题就讲到这里,现在我们把刚才讲的代码呢,给大家简单的整理一下来走一个,那刚才我们讲的是递归迷宫问题。对不对,地宫,呃,递归迷宫问题,那迷迷迷宫问题呢,首先我们把这个迷宫问题抛出来了。然后这边有一个小的截图。是不是?那嗯,关于这个迷宫问题,呃,他的这个分析呢,分析其实思路很很清晰的,所以说我们直接就是在代码里边把这一个呃执行的过程做了分析,是吧,最后呢,我们把这个代码拿过来。
07:16
我们直接把这个代码放过来啊,代码实现。呃,代码实现这边我们给它来一个小的箭头。啊,这样子迷宫问题的说明吧,迷宫问题来一个标题三,这样好看一点。代码实现,代码实现其实就是这块没有问题吧,我把代码呢,直接放在一个表格里面去,同学们待会再去理解一下,然后呢,我这里提出了一些问题,引起大家思考。这里对。对。对,迷宫,迷宫。迷宫问题的说明。或者讨论吧讨论。讨论。好,那么我们讨论了哪些问题呢?首先呢,我说了迷宫问题,还有就是迷宫问题,他得到的路径呢。
08:10
他得到这个路径跟我们的。这个策略有关,诶对方是看看啊,再得到再得到好。好。好,这边有个回溯现象思考,我把这几个问题呢,给大家列到这里来,是个问题对不对?呃,首先我们说得到路径呢,跟策略有关。跟我们导入的策略有关,然后呢,我通过改成上右下左,同学们看到了它的变化,呃,回溯现象,其实在上节课已经讲过了,最后留了一个思考题。就是。请大家去思考怎么找出这个最短路径,刚才呢,我们给出了思路啊,思路已经有了。那么同学们要做的就是代码实现。Okay。
09:01
好,这个就是关于我们这一个迷宫问题的一个求解,包括代码,包括我们整个这个思路的分析呢,就跟同学们讲到这里,大家看看,呃,对这个代码呢,再好好的理解一下,尤其要去理解回溯它是怎么产生的。就是什么地方产生回溯的呢?就是当这个路走不通的时候,他回到上一层这个站调动站,然后再往下面走,如果四条线都走不通,把那个二改成三,然后再回到上一层。明白。好,最后呢,我们这个就OK了,如果都走不通,那么整个路他走过的路全部会制成三。至尊三好同学们,那关于迷宫问题先给同学们说到这儿,下面呢,我们准备讲一个八皇后问题,也非常简单啊,当然也不是不是非常简单啊,可能是需要大家思考他的,这个八皇后问题呢,相对来说比迷宫问题要难理解一点,待会儿呢,我们在下一课下节课跟大家再讨论八皇问题,八皇后问题在我们面试和笔试的时候出现的频率是极高的。
10:09
尤其是同学们,在在这个大学里边,呃,学数据结构的时候,一般都会有老师提到八皇后是不是,那到底八皇后怎么做,怎么去解呢?我们在下节课跟大家进行分析和代码实现。好,这一课我们先说到这儿。
我来说两句