00:00
好,同学们,那代码呢,咱们就写这个核心代码,就写完了,我们来把它进行一个试用,看看我们这个代码是否能够真正的工作,就是这一段核心代码是否能够工作,其实也并不是很难,就是把老师说的一个思路捋了一遍,仅此而已。仅此而已,好,那现在我们来测一下。我们来完成这个测试工作。测试测试我们的骑士。周游算法。算法是否正确?OK,是否正确?那我们首先把这个X置为一个八。把Y呢,我们自为也置为一个八,就是我是八行乘八列了吧。好的,那么若我们假设设为一个一啊,就是我从第一行开始走,就是马儿马走的。哎,走的行,呃,初始位置,初始初始位置的行,这个地方我们是从一开始编号。
01:10
开始编号。开始编号。那待会你再传的时候,那这个若减一传给他就行了,明白吧,因为我我们在从代码来看,若等于一呢,比较容易知道是是从第一行,同样道理,我们列也写一下column。Culu mn,那么我们也把它设设成一个一,就是马儿的初始位置的行列。这个大家看看能能否理解对吧,我指定它的行和它的这个列。一个是行,一个是列。重新开始编号,那有了这个方法过后呢,我们就可以创建我们这一个棋盘。棋盘是不是现在还没创建起来啊,啊,你光有了这些初始化还没创建起来,那么我们把棋盘创建起来走。
02:03
叫chess。Board board等于什么呢?661个int,就是刚才大写的X和大写的Y。没问题吧,同学们。好,那这个写完了以后,我们上来过后,是不是还要把这个VZT的也创建起来,VZT的是记录。呃,有没有被访问过,但是你这要初始化才行哦六。一个玻璃。玻璃那多大呢?大家想应该有多大,咱们这个V里面有多少,是不是就是X乘以Y这么多个元素?初始化就是初始的,初始值都是。都是force,这点我就不说明了。这点大家应该很清楚,就是你boing数组在你没有做任何处理的时候,它初始值都是falses。那么现在呢,我们其实现在就可以来玩一把了,那么玩的时候呢,我们看测试一下,就是测试一下花费时间耗时吧。
03:11
耗时,那我在执行之前先拿一个时间,我用system。点current。OK,把它的毫秒数拿到。把它毫秒数拿到。那这个地方我们取个名字就叫什么呢?Star就是开始时间。好,现在有了这个时间过后呢,我们调用我开始实验,我想想啊,嗯,现在我们就调用这个方法了,可以travel cheboard。那么我们这地方传的是什么呢?首先把这个棋盘传进去,再把这个RA传进去,但是RA呢,我们在这里面实现的时候是从零开始的,因此你要在这个基础上减一才是正确的,千万要记住哦,要减一列呢,我们仍然减1STEP。
04:04
Step,那第一个肯定就是一了。因为你初始的时候呢。他就算一个位置,就是这个好,整个结束了以后,我们是不是再计算一下。这个运行的时间好,仍然是用system.current。Time。呃,Millions,把现在的结束的毫秒数再拿下,这个呢,我们就叫end。一个大一个的。好的,那现在我们就把这个时间说出来,看看他一共耗时多少,共。耗时。那么我把这个时间打出来,同学们看一下就OK,怎么打呢?就用end。End减去star就可以了,就是最后这个时间的毫秒数减去。减去这个。嗯,减去这一个,呃,开始时间的毫秒数,后面把这个单位带上毫秒对吧,毫秒。
05:07
OK,毫秒。嗯,那现在这个做完了过后,是不是我们应该把这个棋盘也输出来给大家看一下。就最后这个结果到底是怎么走的吗?输出,输出棋盘。棋盘的最后。情况。但他有可能是走通了,那就是。呃,一到64个点的位置给你标清楚了,如果他没有走通呢,这个棋盘应该是全零。怎么输出呢?非常简单,我就不写单独的方法,直接直接在输出先把肉拿到。我就用一个for循环增强,把这个棋盘进行一个for循环增强,For循环。这个地方取出来就是绕,再进行一个循环就搞定。对,Int,然后呢,Column Lu。对吧。然后呢,这边有个Rose,我有很多的行行把每一行的数据取出来,就是一列了嘛,现在又把值就可以取出来,怎么取呢。
06:09
好的,走,那这个时候我们这就先不要换行了,咱们直接把这个字打出来。这个是取出一行行里面每个干脆这样的啊,这个就叫。啊,这个可以叫step,是不是更好一点是吧,这代表第几步嘛,其实就是你最后每一个这个一,这个棋盘里面记录的就是走的第几步,所以是叫step应该更好理解一点来放这。然后呢,为了好看呢,我们进行一个制表符,输出一个制表符。好的,那每输出一行,我们换一行。就是你输完一行过后呢,换行。好,同学们,看看这个代码有没有问题啊,我再检查一下。现在我们是八行八列。八行八列。那这边呢,一一位置也是正确的,工号是多少。
07:04
好呃,现在我们可以来运行一把了,各位同学在我没有运行之前呢,我要给大家说清楚啊,同学们有发现在我们这个地方,在目前这个情况,我们用的这个策略呢,不是最优的。大家知道为什么吗?因为我在这个地方往这个点加是567,我我走的这个策略是这样走的,567。01234对不对,我是这样走的,但是你你这样走有一个问题,就是你你这样走有可能五五的下面呢,走完这个五过后,它下面的步骤还还有很多。大家知道我在说什么吗?就说你在走第五步的时候走,走完这个第五步,第五步这个新的位置下面可能有也有很多的选择,其实我们应该采用一个什么策略呢?就是如果我们让这个马儿先走的是下一步。
08:06
可选的步骤比较少的,这种步骤呢,应该更合理。我,我说清楚什么意思了吗?就是如果我们让这个马儿走的下一步是他的下一步的下一步,选择最少的那种情况才是最优的。因为你你你选择越多,那你就意味着回溯的情况就会越多。你的选择越少,说明这条线它回溯的可能性就会越小,从而呢速度会快,所以说我我要说明的是,我们这个方法运行可能会耗费一点时间。如果不出什么问题,应该是在呃是在一分钟之内才能完成好这样子啊,我们不管怎么样,我们先把这个,先把这个玩一下吧,先看这个结果到底对不对,如果代码不对,我们还要调嘞,来运行一下先。好,代码开始运行了。
09:05
好,同学们可以看到现在呢。我我这样子啊。因为这块没有任何提示信息,说感觉好像没运行,我在这打一个打一句话吧,说看看什么呢,就说我们叫做骑士周游。周游算法,开始计算。算法开始开始运行。那么我们来看看大概需要多少时间哈,各位朋友待会呢,可以看到这个结果来运行值。开始了,同学们看他现在正在找呢。因为我们这个是八乘以八的,所以说他现在你也没有,你也没有做优化,没有用贪心算法来进行优化,所以说你看这个时间。大概会花在一分钟之内才才能出结果,大家耐心等待一下。好,这样子,我把视频先暂停一下啊,因为这个不知道什么时候能完成。
10:02
好的,同学们,大家看到这个结果了没有?呃,如果你还在看视频,你可以跟上,因为刚才我停了一下。我停了下,因为我不知道花多少时间好,最后这个结果出来了,同学们结果呢,应该是没有没有问题的,就是他确实能够通过我们这个算法呢,把最后这个结果拿到,而且大家可以看到时间是。这么多毫秒,也就是说他一共花了39秒才得到这个结果。那刚才老师已经给大家讲过,你是39秒的原因,就是因为我们并没有去考虑这个策略。而我们这个策略应该怎么样考虑呢?就是如果待会我们用贪心算法来进行优化,就是说我们能够让这个马儿先走。他的下一步的下一步那个次数最少的那个点,比如说打个比方,我我比如说五,假设这个五走完了后五的下一步只有一个选择。而六的六的这个走六,六下面有三个选择。
11:01
七下面有四个选择走零过后,零下面有五个选择走一,一下面还有五个位置可以走,那么二有一个位置可以走,三呢有两个位置可以走,四呢有两个位置可走,那么其实我们应该先走五,走完五个呢再走二是这种顺序,它的这个性能就会得到一定优化。这就叫弹性算法,待会我们再优化好,那这样子同学们虽然我们这个算法出来了,但是我们不知道。这个结果对不对啊,我们没有玩玩过,没没办法验证我们算法对不对,是不是,所以说呢,现在我们来验一把,那现在同学们看我们在这个游戏里面再来一把。好,同学们,看到现在我们这个马的初始位置其实已经有了,而这个棋盘呢,是六乘以六的,我把这个稍微改一下,我们就来玩一把好不好?验证一下我们的算法到底对不对,我先把它改成六乘以六。那现在他给的这个码的位置是行是第几行呢?行是第。
12:06
二第二行列是第四列。二和四,我把这个改一改,二和四。现在这个棋盘变小了,所以说它花费的时间应该更少一点,那运行值。我们运行一下开始运好,你看这个时间就会很快,因为你现在棋盘。由八乘以八变成六乘以六了,我们来按照他给的这一个步骤,看看是否能能够把这个游戏给搞定来,同学们跟上我的思路来玩一把。呃,把这个往这边挪一下好吧。我们看一下我们这个算法到底是不是能够搞定这个事情,第一步,第二步先走这。第二步走完了,给我走三走这儿。山走完了过后走走这儿。
13:01
呃,走五走这儿。六走这儿,再往这边走,好的,六走完了走七,七在这儿。就这一步,没问题吧,同学们。好的,那七走完了第八步再去,在这儿。好的,第九一步走这儿。第十步在哪去了?在这?第十步,十步走完了过后,11步在哪呢?11步别看错了,在这儿。11 11完了走。12 12在这边。12 12走完走13。走这13走完走14。好,14走完走15。好的15走完走16 16走完走17 17走完走18 18走完走19,好的19走完,那它只只有一个位置了,对吧,19走完走20。走完20过后呢,走21 21在哪里呢?21在哪去了在这。
14:06
21 21走完走22 22步在哪里呢?好,我这眼睛有点花啊,22上哪去了?22上哪去,诶22呢,在在这在这个角落,二十二二十二走完走23 23走完走24 24这。24走完走,那只有这一步了。好。这这第几部了,我忘了。24步了,24走,走25了,哈,走25了,诶我刚才走到哪一步了,这是23,这是24了,看24在哪。20在哪去了,24。24在哦,就是25了吗。刚才24走走过了没有?呃,别,别弄错了,我刚怎么找不到了呢?14、21、12。诶,怎么找不到了呢。
15:03
我看看啊。怎么走,走着走,自己自己不知道走哪去了,十一十一步在哪呢?C在这儿。嗯,20,这个23走到这24了,应该走25步了,按理说。走25步,25在这儿啊。25在这儿,那应该怎么走呢?哦,现在已已经是25了,对吧,已经是第25步走第25步,下一个26步,26步应该走这。是这样子的吧。好,走这26,走27。27 27走28好,28走29好,29走30 30在这儿,30走完走31。
16:00
三十一三十一三十一三十一在。这里柜子。31在这儿别走错了,31走完走32,好,32走完走33。33走完了,只有这一步了。那只能走这儿。好朋友们,最后这一步搞定。最后回到这边来了。他最后马踏棋盘,最后你再重复回到这个位置,看到没有,其实36步已经走完了,再回到这成功。结束。36步全部走完,也就最后我还回来了,那整个这个算法是没有任何问题的,代码是OK的,好吧,代码是OK的,呃,就是按照这个一步一步走就完事了。好,同学们,那关于这个算法我们验证是没有问题的,没有问题,但是呢,同学们也看到我们这个算法存在的一个问题,就是并没有对我们这个马儿走法进行。
17:00
优化,所以说当我们这个地方是八。这地方是把这方也是把这个棋盘较大的情况的时候,我们这个码码在进行这个马踏棋盘算法的时候,花了39秒,这个不可不可以接受,待会呢,我们用贪心算法来进行一个简单的优化好不好,同学们那关于马踏棋盘的这个核心算法。也就是我们其实周游这个算法的核心就讲完了,大家理解一下其实并不难哈,想想。
我来说两句