2.1.11 八数码魔方实例分析在线视频

下面我们回到这一章的最开始那个问题

八数码魔方如何能够通过搜索的办法

快速找到我们的答案

比如这是起始状态

2831647空格3

怎么样到达我们的目标状态

12345678顺序排列

怎么样通过一系列的操作

能够把这样的问题给求解出来

我们考虑这样一个问题的时候

我们就要考虑一下采用什么样的代价函数来估计

我们可以定义

对于每一个节点

它的数据库中错放的棋子个数是多少

因为如果错方的棋子个数是零的话

对照目标状态来看

它就是已经找到了这个问题的答案

所以对于初始状态28316475

我们发现他错放了几个数

显然二错放了

八错放了

3457没有错放

一六错放了

所以错放了四个数

也就是说对于当前这种状态

它的代价函数

取值就是四

那么操作怎么办呢

就是当前这种状态

要想进行变化它的状态

改变它的状态

我就要将空格可以向上移

可以向左移

也可以向右移变成下一波

那么通过分析发现

对于当前状态

我们按照向上向左向右

还有向下类似的这样操作

一步步的改变当前的状态

就一定可以朝着使得代价

也就是说错放了棋子个数减小的方向操作

最终使得错放的棋子个数为零

也就是找到了我们的答案

把这个问题给求解出来

那么对于当前这种状态

2831647空格五

它的子节点有几种可能状态

显然我们把空格操作可以向左走到了左边这种

向跟六对调一下

向右跟五对调一下

分别得到了下面这三种状态

那么对于这三种状态

它们对应的代价值是多少呢

显然左边的是错放的棋子是有哪些

28167都错放了

所以是5

中间错放棋子数就是128

错放的棋子数是三

右边错放的棋子数是28165

所以错放的棋子数是五个

那么显然我们下一步搜索的时候

我们就优先考虑这个代价最小的

就中间那个状态进行搜索

其他的以此类推

这样的话

我们通过七步就可以得到的结果

我们看一下如何采用刚才这种方法

叫最佳优先搜索数

能找到我们的解

对于当前状态来说

初始状态

空格可以向左向上向右

分别得到了这三种不同的状态

那么它们所对应的代价值分别多少

535

显然考虑中间这种

代价是3

我优先考虑它

那么下一步的时候我们要考虑一下

不能再走回头路了

因为我们有CLOSED表

所以这个空格本来是可以向上向下向左向右

有四种可能的子节点

但是这个空格是不能再往下的

不然的话就回到初始状态

因为我们要CLOSED表

所以这个时候我们就有三种不同的子节点

空格可以向左向上向右

这样的话

它们对应的代价分别多少

三四四

这时候我们优先考虑代价为三这种情况

同样的由于CLOSED表存在

空格是不能向右的

它可以向上向下

从而就形成了两种子节点

也就是这两种

那么左边这个代价是多少三

右边代价是四

我们还要进一步搜索中间

因为它的代价也是四

对于中间这种状态

我们的空格是不能向下的

但是它可以向左向右

所以他要两个子节点

向左的话

就形成中间这个代价是二

向右的话形成右边这个代价是四

我们发现了在这一层

我们找一个代价最小的显然是二

所以继续往下搜索

由于空格是不能向右搜索了

所以空格只能向下搜索

也就是变成了下面这个状态

这时候我们发现它对应的代价就是一

那么在这个位置

它空格是不能向上搜索的

因为有CLOSED表存在

但它可以向下或者向右

从而形成了最下面这两种状态

它对应的代价分别是零和四

显然这时候我们已经找到了

这就是我们的目标状态

按照蓝色箭头回溯一下

其实我们就已经找到了这个问题的答案

这就是利用最佳优先搜索

来求解八数码魔方的这样一个过程

下面我们看一下如何采用A※算法

来解决这样一个八数码魔方问题

那么这时候我们要考虑两个问题

第一他是第几次操作

第二他要考虑当前的节点状态和目标节点状态

每一个数字

它的错放的相对位置的之和

我们看一下初始状态

叫第零次操作

我们错放的棋子数有四个1268

对一来说

错放的棋子数

错放的位置就是一

二也是一

六也是一八是二

所以加起来是1+1+1+2等于5

所以对于初始状态来说

它的代价就是0+5等于5

那么由于初始状态

它这个空格可以向左向上向右移动

从而可以得到了下面三个子状态

向左的时候

这是第一次操作

所以前面是一

这时候有五个棋子错放的

12678

那么一错放的位置是几呢一

二也是一

六也是一

七也是一八是二

所以加起来是四个一加二六

所以最左边这种状态

它对应代价就是1+6等于7

那么这中间这种也是第一次操作

错放的棋子数呢是128

一错放的位置是一

二也是一八是二

所以加起来就是1+1+2等于4

这是他错放的棋子的位置之和

所以代价就是1+4等于5

最右边这种也是第一次操作

错放的棋子有五个

12568

一错放的一

二错放的也是1

五一

六也是一

而八错放的是二

所以四个一加二代价是六

显然在第一步操作的时候

我们选择代价最小的那个

就中间那个五

那么考虑到CLOSED表存在

那么对于空格在中间的这种状态

我们是不能往下走了

就回去了

所以空格可以向左向上向右

得到了第二步操作的结果

第二步操作的时候

我们发现空格如果向左的话

错放里面三个棋子128

一错放是二

二错放的是一

八错放的也是二

所以加起来就是1+2+2等于5

所以最左边这个它的代价就是2+5等于7

中间这个也是第二次操作

一错放的是一

二错放的的也是一

八错放的也是一

所以加起来就是错放的数是三

2+3等于5

这是中间这个

右边这个也是第二次操作

一错放的一

二错放的一

四错放的一

八错放的是二

所以加起来是五

所以它的代价是2+5等于7

显然第二次操作也应该选择中间这个

因为它代价最小五

下一步由于空格可以向左也可以向右

但它不能向下

不然就回去

所以它有两个子节点

形成了第三步操作

我们看左边一错放的是一

八错放的也是一

所以它代价是二

加起来就是3+2等于5

右边呢

错放的一

二错放的一

三也错放的一

八呢错放的也是一

所以加起来就是四

总代价就是3+4等于7

显然下一步我们要考虑的是代价最小的五

就中间这个

再往下走

空格是不能向右的

只能向下

所以下一个子结点有且只有一个选择

也就是空格向下走

这样得到了这样一个结果

中间这张图我发现他第四步

它代价多少呢

代价错放的的数

就一个数错放了八

代价是多少

错放的位置是一

它的代价是4+1等于5

那么对于这种状态

空格是不能上去了

但它可以向下也可以向右

就走到了最后一步

如果向右的话

其实它这时候代价就是零了

因为就是目标节点

这是第五步

所以它代价是5+0等于5

而如果空格向下的话

它是第五步操作

错放的棋子数就是八错放的二

所以就是七

显然左边这个呢就是我们的目标节点

按照蓝色的箭头指示回溯一下

我们就能够找到这个问题答案

显然它是一个最优解

这就是用A*算法来求解八数码魔方问题的一个过程

下面我们可以练习一下这样一个问题

已知初始状态12345678

怎么样到达这个目标状态

显然我们每个人都可以很容易地判断出来

把六向右移七向下移八向左移

这就是答案

我们现在看一下怎么样

A*算法把这个问题给求出来

首先初始状态

他跟目标状态的差异有多少呢

错放的就是

六错放的一

七错放的一

八也错放的的一

所以错放的代价是三

总代价就是0+3就是3

那么下一步空格可以向左向上向右

这样形成了下面三个子节点

如果是向上

那么这时候错放了几个

六错放了一

七错放的一

八错放的二

所以加起来是四

这时候它代价就是第一次操作1+4等于5

中间这个就是空格向左的结果

我们发现错放的棋子数是几

七错放的一八错放的一

所以错放的棋子位置是二

1+2等于3

右边这个五错放的是一

六错放的一

七错放的一

八也错放的一

所以代价是四

加上第一次操作

所以总代价是五

显然我们要选择中间这个路径

再下一步

我们的空格是不能向右移的

所以他这时候只能往上移

往上移的话就得到了中间两张图

这是第二次操作

那么显然这时候只有八错放了

错放的是一

所以总代价是2+1等于3

那么下一步这个空格是可以往右移

可以往上移

对吧

但是不能往下移

往右移往上移

我们发现其实这空格往右移就是答案

他这时候跟目标是一致的

这时候它对应的代价就是第三次操作

而且代价是零

加起来就是三

这就是我们要的答案

按照蓝色箭头回溯一下

其实就找到了这个问题的解

而且我们发现它跟我们之前分析出来的结果是一致的

也找到了一个最优解