Video在线视频

那么来看一下怎么定义这种可采纳的启发式函数

那么我们来看一个例子，这个例子就是我们的八
数码问题

这个是属于一个滑块游戏

也就是说这里面有八个数字块和一个空格

通过不断移动数字块到空格里

使得这八个板块排成这个样子

那么这个是一个游戏问题

那么我们可以怎么样来定义结点n到达目标结点代
价的一个估计呢

那么我们可以这样估计，第一种启发式函数可以
这样定义

定义成错放的数字板块的个数

比如说像这个初始状态

如果用h1（n）来估计它到达目标状态的代价的话

我们就看一下它哪些数字块错放了

像7错放了，2也错放了，4也错放了

那么这个5、6、8、3、1也错放了

那么这八个都错放了所以它的估计是等于8

那么我们还可以定义另外一种启发式函数

另外一种启发式函数就是我们的h2（n）

那么它定义的是状态n到目标状态的曼哈顿距离

这个什么意思呢，就是

比如说7，也就是说我们可以把板看成一个坐
标，7到目标位置的曼哈顿距离是多少

2到它的目标位置的曼哈顿距离是多少

那么这八个数字块到它们的目标位置的曼哈顿距
离之和

就是我们的状态n到目标状态的曼哈顿距离之和

那么这两种启发式函数的定义是不是可采纳的

它有没有过估计从这个状态到目标状态需要移动
的板块次数呢

我们可以看得出来那肯定是没有过估计的

因为第一种启发式函数的定义其实上意味着

你可以把板子直接和我目标位置的板子互换

也就是说7可以直接和3互换

然后2也可以直接和4换一下

4又可以直接放到空格这里

也就是说相当于把游戏规则放松了

就是每一个数字块可以移动到任何一个位置去

那么这当然是一种最简单（快速）的方法

那么它比你通过不断移到空格里面来换位置要快
的多

所以它绝对不会过估计代价

那么第二个启发式函数会不会过估计代价呢

它定义的是所有数字块到目标位置的曼哈顿距离
和

比如说7到这个位置的曼哈顿距离是横坐标差的绝
对值加上纵坐标差的决对值

也就是说让7右移、下移、下移，到达这个位置

就是说横坐标差为1，纵坐标差为2，所以1+2，3

就是说让它可以和任何相邻的板块互换位置

所以它只要三步就能到达目标位置

那么2也是只要一步就能到达目标位置

它可以和相邻的板块互换

那么其实这种估计也是把游戏规则进行了一个放
松

也就是说它把游戏规则放松成任何一个数字块都
可以和它相邻的数字块互换位置

那么7就可以快速的移到目标位置去

那么任何一个数字块都可以通过和相邻板块互换
快速的移到目标位置去

那么这种也不会多估计我们实际的游戏步骤

也就是说实际的游戏步骤是不可以这样做的

它只能通过移到推到空格里面，比较繁琐

那么这种步骤要比放宽的游戏步骤要多

所以这两个启发式函数都是可采纳的启发式函数

它不会过估计实际的代价

那么所以呢我们来看一下对于这么一个状态

对于第一个启发试函数它的启发式函数值是等于8

也就是我们看一下它错放的数字块的个数

就是这八个数字块都是和目标位置不一样的

所以它就是等于8

第二种启发式函数每一个数字块和目标位置的曼
哈顿距离的和

那么我们来看一下7到目标位置的曼哈顿距离

就是横坐标差的绝对值加上纵坐标差的绝对值

就是1+2是等于3的，所以7是3

2呢是1，它横坐标的距离是1，纵坐标为0

然后4要到中间去，横坐标纵坐标差的绝对值加起
来是2

然后再看5，5到它要去的位置横坐标的差是2，它
也是2

然后6到左下的横坐标差是2纵坐标差是1，所以它
是3

然后再看8，横坐标差是2纵坐标差是0，所以是2

然后再看3，横坐标纵坐标差都是1，所以加起来
是2

1的横坐标差是1纵坐标差是2，所以加起来是3

所以总共加起来就是18

第二个启发式函数值加起来就是18

那么大家想一下这两个启发式函数值哪个更好

那么当然是越接近真实代价的启发式函数越好

那么既然你们都是小于等于真实的代价

那么它更大当然是它更接近真实的代价

所以说h2的定义要比h1更好

那么这个是可采纳启发式函数的一个示例

那么来看一下这个启发式函数有一种占优势的概
念

也就是哪一种启发式函数更好

也就是说你在定义启发式函数的时候应该怎么样
来选择

那么来看一下对于所有的结点n都有h2（n）大于
等于h1（n）

当然这里比较启发式函数的前提条件就是

这些启发式函数都要是可采纳的

也就是说都没有过估计实际的代价

在这种前提条件下我们来比较哪种启发式函数更
好

那么假设对于两个可采纳的启发式函数h1、h2

如果对所有的结点n都满足h2（n）大于等于
h1（n）

那么我们就觉得h2比h1占优势

也就是说认为h2比h1更好，占优势就是这个意思

就是h2比h1更大，更接近于真实的代价值

那比如说像我们刚才的板块游戏，八数码问题

这个问题假设我随便给一个初始状态

那么这个初始状态到达目标状态最少要推动板块
12次才能到达目标状态

也就是说最优解的深度是12

就是最少都要推12下才能推到目标状态去

那么如果用迭代深入搜索它需要产生这么多个结
点才能够搜索到解

也就是说搜索到最优解

如果我用h1这个刚才定义的启发式函数

就是用错放的数字块个数来作为启发式函数

用这样的一个启发式函数的A*树搜索算法

只要拓展227个结点就能把最优解找出来

那么如果采用h2这个启发式函数

我们的A*搜索算法只要拓展73个结点就能把最优
解找出来

所以启发式函数定义的好与坏非常重要

所以这个是一个比较，大家也看得出来

这个启发式搜索策略要比盲目搜索策略好的多

也就是说只要你的启发式函数定义的比较好，比
较靠谱

那么它都能够巨大的提高搜索效率

那么再看这个例子，这个例子问题就更复杂

也就是说这个问题就是我们的八数码问题

如果我给一个非常难的初始状态

它到达目标状态最少需要24步

对于这个么一个更难的问题

我们的迭代深入搜索要产生太多太多的结点

可能你都等不了这么长时间

那么如果用我们的A*树搜索算法

用第一种启发式函数

也就是说用错放的板块个数来估计代价的话

那么它要产生39135个节点就可以找到目标

然后如果是采用第二种曼哈顿距离启发式函数

我们的A*树搜索算法只要找到1641个结点就可以
把这个解找出来

所以非常快速，盲目搜索策略是没法比拟的

所以盲目搜索策略和我们的启发式搜索策略是没
有办法比的

那么这个是这么一个例子

那么我们怎么样来找启发式函数呢

也就是说怎么来定义一个可采纳的启发式函数呢

那么我们就可以通过对原来问题进行松弛化

那么松弛化的意思就是比如你原来的问题产生后
续是有约束的

或者说对于特定的状态它只能采取一些有约束的
动作来产生一些后续状态

如果你对原来这个问题动作的约束进行放宽

那么我们就称放宽了的这个新的问题为这个问题
的松弛化版本

那么这种松弛化问题的最优解代价

就可以用来定义原来这个问题的可采纳的启发式
函数

就像刚才这个8数码问题一样

我把这个游戏规则变松一点，就是说我可以把数
字版块移动到任何一个位置

那么这么一个新的松弛化的游戏的代价就可以用
来定义第一种启发式函数

如果我把问题松弛化成它可以和任何相邻的板块
互换位置

那么这个问题的代价就可以用来定义第二种启发
式函数

所以这个是我们定义可采纳的启发式函数的一种
方法

就是将问题进行松弛化