00:00
也很重要,我们来看一下,我们先给大家来讲一个递归啊,我们来看看递归。递归呢,我们这次讲呢,我们就来讲一个实际的一个迷宫问题,先来把这个立递归简单的回顾一下啊,首先我们看递归的一个应用场景,比如说同学们可以看。这有一个迷宫,这有一个迷宫,这个迷宫要解决一个什么问题呢?大家看这里,待会儿我们小球从这里出发。就这这有个小球,就这个圆球,这个圆球呢,从我们这个三角的位置开始出发,要到达哪里呢?它的目的地在这里。对,在这里,那同学们想,嗯,对于我们人来讲,对于我们人来讲,我们当然知道这条路是可以过来的。但是如果我对这个小球来说的话,他并不知道。他并不知道我能不能到达这里。
01:00
因此呢,这就有一个回溯的问题,就好像同学们去玩这个迷宫游戏,那你到一个迷宫里面去,你怎么知道怎么走才行呢?就好像这个小球是一个人一样,他能找到这个出路。啊,那么我们把这个代码给大家跑一下,让大家体会一下这个东西啊来,那我打开打开给大家分享的一个资料,我们到这里面去看一下。OK,我给同学们跑一个。看一下这个地方啊,走CDCMD好Java。迷迷宫啊迷宫,OK,跑起来。好,同学们看,呃,那假如说现在呢,我们这个小球从这里开始出发,那这个小球它会怎么走,取决于什么呢?大家可以想想,动动脑筋。就这个小球,它到底是这样走。这样也可以到这儿啊,还有一个从这样走。
02:03
也可以呀。对吧,但是他还可以这样走,他说老师我这样走,从这到这是不是也可以也可以,那他他到底就说这个小球,他怎么他怎么知道从哪走。这个取决于什么呢?取决于你的策略。待会儿我会讲这个东西,大家不用着急啊,我先把这个事情取决于你的策略,就说你在进行这个回溯的时候,你告诉这个小球应该怎么去找这个策略,就决定将来这个路径是什么,那就出现了一个新的问题,什么呢?最短路径?最短路径问题。就说你你这个条条道路通罗马这句话是对的,但是一定有一条路是最短的,对吧,所以同学们要走向这个成功,肯定有很多都可以条条道路通了吗?但是有一个最短的。最简最不费时的,那你这个最短路径,你能不能找出来第二个这个地方,这个地方大家看到这个红色呢,代表我们的墙。
03:09
那还有一个问题,假如我这个小球从这里出发。但是我在这儿也堵了一堵墙。我这儿也是一堵墙,这也是一堵墙,那么这个小区他怎么知道我走不出去呢?你还不能让他在这儿进行死循环。那实际上他使劲使劲,他来回这样切,跳来跳去,那不出大问题了,你还得有一个告诉,你还得有一个方法能够判断我这条路是走不通的,他就可能谈一个出说。无路可走。对吧,你这都要考虑运去,这也是要靠我们的策略和回溯来解决好,那同学们现在往前跑一下啊走。大家看我这边这个在走的过程中,其实这里二就是它的一条通路。你看他会这样走。这样走,那这样走的原因是因为我用的策略是什么呢?我用的策略是根据我的代码,我是先走这个下面再走右面。
04:07
啊,如果右面再走不通呢,我走的是,呃,上面和下面,那如果我的策略发生变化,这条路一定不一样,如果我先那个小球先探测往上走,再往这个右边走,它的路应该是这样走的。好,那么这个具体怎么做的,待会儿我们会把这个程序给大家写出来,那再体验体验它的一个回溯,好这是我们的一个入门的介绍啊,入门介绍呃,因为我们SC呢没有界面,但是我怎么讲呢,我就直接模拟一个地图。一个二维的地图,然后呢,这个二就代表一个出路,一就代表一堵墙,待会我会这么去写代码,好,那通过这个案例呢,大家知道,待会我们要讲的就是用这个回递归来解决的一个问题,大家先清楚了哈,OK,这是一个应用场景。
我来说两句