Video在线视频

那么我们来看一下这个启发式函数到底要怎么来
定义才比较好呢

也就是说什么样的启发式函数是比较好的启发式
函数呢

那我们有一种原则 就是启发式函数要定义成可采
纳的

什么叫可采纳的启发式函数呢

也就是说如果你定义的启发式函数对于任意一个
结点n，都满足这么一个不等式

也就是h（n）小于等于h*（n）

那么这个h*（n）是什么意思呢

就是从这个结点n到达目标的真正代价

也就是说这个真正代价肯定是存在的

只不过你当前还不知道

那么如果你定义的启发式函数会比真正的代价要
小

也就是说不大于真正的代价

那么就称你定义的启发式函数是可采纳的

也就是说你不能过估计这个代价

这个就是可采纳的启发式函数的意思

那么我们关于A*算法有一个定理

也就是如果你定义的启发式函数是可采纳的

也就是说满足这个条件，不会过估计真正的代价

那么A*树搜索算法就具有最优性

看清楚它是说采用树搜索

就是说我们的结点只有当它拿出来拓展的时候才
会判断它是不是目标结点

这个树搜索算法是采用这样的算法的

采用可采纳的启发式函数的A*树搜索算法保证最
优性

也就是说它找到的解一定是代价最小的解，一定
是一个最优的解给你

那我们来看一下这个A*树搜索算法在我们的启发
式函数可采纳的时候

为什么能保证最优性

那么下面我们来证明A*树搜索算法的最优性

那么我们假设有一个次优的目标结点G2已经产生

并且他已经在fringe表里排队

就像前面那个罗马尼亚问题示例一样

那么假设n结点也在fringe表里面

并且它是从初始结点到达目标结点的最优路径上
的一个未拓展结点，也就是一个待拓展结点

它也在fringe表里面

那么我们就要证明最优路径上的一个待拓展结点

在fringe表里排队一定会排在次优目标结点前面

使得我们的次优结点永远都没有出头之日

永远都不可能排在队首，使得次优结点会被发现

也就是说永远都是我们最优路径上的结点会排在
它的前面

也就是说使得最优解被发现

那么来看一下为什么最优路径上的待拓展结点一
定会排在次优目标结点G2的前面呢

我们来看一下也就是说我们知道目标结点G2

它是一个目标结点的话，它的评估函数值就只等
于第一部分

因为第二部分h表示的是从这个结点到目标的一个
估计代价

那因为这个结点本身就是目标结点所以这个h值是
等于零的，包括G也是一样的

所以我们的G2和G结点的评估函数值都只等于第
一部分

因为第二部分h值是等于零的

因为它俩本身就是目标

所以我们就是到f（G2）等于g（G2）次优结点

那么这个是什么意思，这个就是从初始结点到达
次优结点的，次优路径的代价

然后f（G）表示的是从初始结点到达G最优解的代
价

所以它是这么一个意思

那么竟然我们假设G2是一个次优结点

那么从初始结点到达它的代价肯定会比从初始结
点到达最优结点的代价大

所以g（G2）大于g(G)

这个是根据假设得出的

那么有因为我们的这两个目标结点的评估函数值
就是等于第一部分

那么既然g（G2）大于g(G)

那次优结点的评估函数值肯定是大于最优结点的
评估函数值的，就是这个代价要更大

那么又因为我们刚才说了我们是要证明运用可采
纳的启发式函数的A*树搜索算法

那么也就是说假设我们采用的启发式函数是可采
纳的

也就是说可采纳的是有这么一个条件

h（n）要小于等于h*（n）

h*（n）前面也说过就是n到达目标的实际代价

那么这个不等式左右两边加个g（n）还是成立的

所以就是有第六个式子成立

那么第六个式子我们看到这个左边g（n）+h（n）
就是我们的A*搜索算法定义的f（n）

就是n结点的评估函数值

那么我们看一下这边是什么

我们知道这个n是从初始结点到最优结点的最短路
径上的一个结点

那么g（n）就是从初始结点到达这个结点的实际
代价，也就是最小的代价

然后再加上h*（n）就是n到达目标的实际代价

这个g（n）+h*（n）就是从初始结点到达这条最
短（最优）路径的代价

那它就是我们的最优结点的代价

那么最优结点的代价也就是它的评估函数值

因为它算的就是最优（最短）路径的实际代价

那么就是我们的最优结点的评估函数值

所以这个不等式的右边就等于f（G）

那么有这个不等式成立的话

我们结合看第四和第七两个不等式

f（G2）大于f（G），f（G）大于f（n），那么当
然f（G2）大于f（n）

那就意味着任何一个次优结点的评估函数值

都要比通往最优（目标）结点路径上的任何结点
的评估函数值大

所以任何通往最优（目标）结点路径上的待拓展
结点

都会排在次优结点G2的前面

所以使得G2永远没有机会排在队首

所以他就不会找一个次优的解给你

一定会找一个最优的解给你

一定是一点点去拓展最优路径上的结点，直到发
现最优解

所以我们的A*树搜索

采用这种可采纳的启发式函数的A*树搜索

绝对不会选择次优结点G2进行拓展

所以它就能够保证最优性

当然这里保证最优性有两个先决条件就是

他要采用这种可采纳的启发式函数

也就是说这个启发式函数不能过估计代价

实际的最优（最短）代价，实际的最小代价

这个是A*树搜索算法的最优性

那么来看一下A*树搜索算法的性质

首先来看一下有没有完备性

那么这个完备性是有的，也就是是说有解它就能
够找到解

因为他估计是一条完整的路径代价

那么如果你这个结点在不断地死循环

那么这个节点的g（n）是会不断增加的

那么它就会排到后面去就不会再走这条路了

除非你的单步代价是等于零的，这个在实际问题
中是没有的，所以它是有完备性的

也就是说这个是它的第一个性能指标

那么这个时间复杂度它也是要看你定义的h（n）
是什么样子的

定义的好的话它的时间是可以大大地降低

那么同样的空间也是和时间复杂度一样的

那么它在找到解之前所有的结点都要存储在内存
里面

那么最优性的话刚刚我们说了

如果它是采用可采纳的启发式函数

那么它是可以保证最优性的

所以这个是A*树搜索算法的一些性质