00:00
各位同学,我们来看一个马踏棋盘算法的代码实现。那首先呢,我要给同学们先说一下马踏棋盘问题,也就是我们前面所说的其实都有问题,实际上呢,它是一个图的深度优先搜索的应用。对,它是一个深度搜索的应用,那么我们大体的思路是怎么样子的呢?大家听听我这说啊,如果我们使用回溯,也就是说使用深度优先来进行解决的话呢,假如这个码它的踏了53个点。看了53个图,呃,53个点走到第53个的时候呢,坐标为一,零,这个时候发现已经到了尽头,比如说我们第五三步走到这儿了啊,假如啊。呃,这个时候101,呃,一零,那是这个位置,假如说走到这儿了,发现已经到尽头,没有办法,那么只能回退查看其他的路径,因此它会在棋盘不停的进行回溯。
01:05
也就是说,这里面实际上是一个回溯的过程。那有些同学老师这个,呃,如果只用文字来描述我这个思路的话呢,很难理解,对不对,很难理解,那这样子我们呢,用一个图解的方式来说一下,待会儿我怎么去实现这一个,其实都有问题,那首先呢,我先把这个棋盘先放过来。那同学们可以看到。这里有一个棋盘,待会我怎么来解决呢?好,我把我的思路给同学们先聊一把,然后再用代码实现,我说一下啊,就是我们这个骑士周游问题,或者叫马踏起都一样啊,骑士周游问题。的解决。解决。解决步骤和思路。听我说,首先第一步大家想你这是一个棋盘。
02:03
八乘以八的一个棋盘,是不是你首先应该先把这个棋盘创建起来,这个没有问题吧,所以我们第一步应该先创建棋盘。哎,创建棋盘,那么假如说这个棋盘的名字呢,我们取个名字叫chess。OK ches board b barb。Board就是棋盘,那棋盘肯定是个二维数组了,对不对,是一个二维数组,这个很好理解,那第二步我们做什么事情呢?同学们想第二步是不是我们要这么去玩?我们要怎么去玩呢?大家有没有发现,当我们一个马处在一个位置的时候,它最多有几个地方可以走,我们先说最多,也就说当一,按照这个马走日志的规则,我们一匹马他最多能够走的位置其实就是八个点。
03:01
是不是这样子的,所以说我们第二步应该干什么呢,将。将当前这个位置设置为注意听设置为已经访问。然后。然后根据根据当前位置计算,计算什么呀,计算马儿还还能还能走。走哪些位置?具体走哪些位置?哪些?位置。对那些位置并并放入到一个集合中,比如什么集合呢?比如说我们放到r list里面去。那有些同学为什么要去计算马儿还能走哪些位置呢?因为你现在马在这个位置,你先把它标记为已经这个位置已经走过了,然后你计算这个马他能够走的位置。因为你要进行回溯嘛,对不对,好当我们。
04:03
嗯,当然最多只能有八个,是不是这个地方你要算下一个位置是哪,哪些位置了最多。最多。有几个位置呢?有八个位置。这个大家应该很好理解,好的第三步我们应该怎么办呢,各位朋友。这个时候我们就就在这个当前位置去尝试着走它的八个位置,看哪个能走通,如果走不通,我们就进行回溯就完事了,大致的思路就这样子的,那么干什么呢?就便利,便利这个R历史的所有位置。对,注意听。List中存放的,存放的所有位置,所有位置啊,看看看看哪个可以走通。可以走通,对,就记录这个哪个可以走通,嗯,这是它的一个过程。
05:04
那么有一个地方大家有没有发现,就是我们怎么知道这个马儿他有可能是走不通的呢?有没有一种可能性,就是这个马。你放在一个比较奇怪的位置,它就是不能够完成,其实都有这个问题,也就是他不能把每个位置都走,都走一遍就能把整个棋盘走满,有没有这种可能性?是有可能的,你比如说我举一个非常极端的例子,大家听我说,假如我给的棋盘呢,就是这么一个棋盘,假如啊,我我我我我说的是假如,假如现在我给的棋盘是一个二乘以二的这么一个棋盘,假如我说的是你的马儿呢,比如说放在这儿的。好,请问你给我走一下。你现在一步都走不掉。是不是啊,你因为马走日志你没没法走啊,所以说这里面还涉及到一个情况,有可能。我们这个码是不能够完成这一个,其实都有问题的。
06:04
或者叫马塔启蒙问题是有可能的,因此你还应该有一个规则。就是判断。判断注意听啊,判断判断马儿是否完成了。这个就有问题。对不对,完成了这个歧视,歧视都有问题。呃,完成了任务吧,完成了这个任务。那么你怎么知道这个马儿有没有完成这个任务呢?那只有一个办法,什么办法呢?就是你每走一步,大家看,你每走一步,就用一个计数器把它记录下来,就代表走了一步。呃,比如说我们这里写啊,就是每走一步,我写到这儿。没走,没走通,一步没走。每走一步。一步。
07:00
就使用一个变量,比如说sta。Sleep加加加一。就说呃,我每走一步呢,我就加一,你当然第一个位置初始化就是一嘛,你第一个位置肯定要走一遍的,好,如果我每走一步内部加一过后呢,我判断这个马儿有没有完成任务,我就可以用这个step。Step和整个棋盘和应该应该走的步数比较。比较,那么这个应该走的步数是怎么统计出来呢?也很简单,就是你的整个这个棋盘呢,整个这个棋盘相乘,就是几行几行几列相乘,再减去一个一嘛。对不对,那么就是看这个马的step和和这个完成任务,就是使用什么呢?使用注意听使用STEM写错了。就是使用step和应该走的步数比较。如果。
08:04
如果没有达到,没有达到,对,没有达到。达到这个数量,数量则表示,表示什么呢?没有,没有完成任务,没有完成任务。那如果没有完成任务的话呢,我们就干什么呢,就将将整个诶将整个棋盘。将整个棋盘至零。志玲。那为什么要注,因为你在整个这个便利的过程中,你每走一步,你内加一了,同时是不是还记录了这个位置是第几步走的呀?因为你只有把这个比如说我比打个比方,我我的这个马儿在这个位置,我先第一步走的是七这个位置,那我是不是应该把这个标成二。为什么标成二呢?因为代表我原先这是我第一嘛,第一个位置,下一个就走二,如果这个地方走完了过后,我又走的是这个位置,那我应该把这个。
09:09
这个位置标成我的一个三,就是把这个棋盘元素对应的,嗯,就说这个棋盘对应这个元素的值改成它应该走的是第几步,明白吧,但是因为你呃,发现这个马儿完成不了这个任务怎么办呢?那你就要把整个棋盘置顶代表没有意义就退了。明白吧,也就是说我们整个这个其实都有问题的解决思路大致就是1234,主要是在这里面有一个回溯,就是看看便利,看看哪哪个可以走通,如果走通就继续走,走不通就回溯。二注意听。如果走通。走通。就继续。走不通怎么办呢?OK,走不通就回溯。大家理解我的意思吧,就回溯就回到,哎,比如说我们从这个位置走七,走完七过后再走下面,哎,我发现走不通了。
10:03
打个比方啊,比如说嗯,这个例子怎么举呢?比如说这个马儿,这个马儿先走了一个位置,走了一个,走了一个零,走完这个零过后呢,诶,他又走了一个位置,呃,假如走走完这个零,走完这个零,发现在零这个位置已经没有任何地方可以走了,它相当于回到这个位置,再走的是下一个位置,就就有点像我们原先讲的小老鼠找迷宫,那那那个意思。因为你在往下面走的任何这一步骤,有可能是后面走不通的,走不通我就回到上面,我再选另外的路径再走,其实很像我们原先讲的小老鼠找迷宫。明白吧,因为你这个码儿这个儿选择的不同的走法,会对我们效率是有影响的,比如说你你先走到五,那最后。得到的这个呃,解是一种解,假设你走先走的是六,是不是又是另外一种解呀。
11:05
但也有可能走六可能就走不通,走五才能走得通,是不是你还有回溯呀。明白,大家想一想,我们原先讲小老鼠找迷宫是怎么讲的,对不对?呃,这个例子应该很好理解,说你走一步,诶,走完过后发现下一步不能走,是不是又回到原先的步,再选另外一个方向走,明白吧,好,这就是所说的回溯,因此同学们可以看到,呃,这块地方呢,如果你的算法不合理的话,性能是比较有影响的。对吧,会有影响到后面我们再说怎么去优化。因为这个回溯我说我在这儿加一句话。注意听这句话啊,我先给你们打一个伏笔,就是这边先先给大家先先说一下,注注意注意注意什么呢?就是这个马儿马儿不同的这个走法。他的这个走法。走法会会得到不同的这个结果。
12:04
对吧,效率呢,效率就是这个速度也会有影响,就效率吧,效率也会。也会有影响,那么这一段就涉及到一个优化的问题了。这里是涉及到一个优化的问题,那至于怎么优化,待会儿我们再讲。我们先把。老师刚才说的1234步先实现了再谈优化好不好,就待会说,诶为什么这样子它会比较慢。那么优化了为什么会快?因为他跟你的策略是有关系的,这个走法就是你的策略。就是你这个策略会影响到你的这个结果。就跟我们原先讲的小老鼠走迷宫,你是先上后下。在左在右,还是先左右再上下,都是有,都是有不同结果的,但最终呢,都能完成这个任务,都能走到最后。同样我们这个马踏棋盘或者是骑士周游问题也是一样的,那么这个策略很重要,待会我们再说优化的问题好吗?好,同学们,那关于骑士周游问题的解决步骤和思路,大体就跟同学们介绍到这里,大家看看理能否理解。
13:16
好了,那思路有了,下面自然就是我们的代码实现,代码实现我们放在下个视频为大家讲解。
我来说两句