搜索方法
启发式搜索
启发式搜索
前面讨论的搜索策略中没有考虑问题本身的特性信息，而只是按事先规定的路线进行搜索。
如果在搜索过程中使用在搜索过程中获得的问题自身的一些特性信息来指导搜索显然会有利于搜索。我们将利用问题自身特性信息来引导搜索过程的搜索方法称为启发式搜索。
启发性信息的作用
启发性信息对搜索的指导作用可归纳为3个方面。
选择下一个要被扩展的结点。
在结点扩展时，选择有用的结点。
修剪掉某些不可能导致搜索成功的结点。
估价函数
启发信息在搜索过程中的主要作用是对结点的重要性进行评估，通过这个评估来实现OPEN表中结点的排序
这个评估一般是通过估价函数实现的。
估价函数
估价函数f(n)的一般形式为：
f(n)=g(n)+h(n)
其中：
结点n是搜索图中当前被扩展的结点。
f(n)是从初始状态经由结点n到达目标结点的所有路径中最小路径代价的估计值。
g(n)是从初始结点到结点n的实际代价。
h(n)是从结点n到达目标结点的最优路径的估计代价。
估价函数示例
例：八数码问题。设初始状态和目标状态如下图，且估价函数为：f(n)=d(n)+w(n)
其中：d(n)表示结点的结点深度；w(n)表示结点n不在位的数码个数。请计算初始状态的估价函数值。
2 3
1 8 4
7 6 5
2 3
8 4
7 6 5
S0
Sg
估价函数示例
解：此例估价函数中有
g(n)=d(n)-路径的深度代表实际代价；
h(n)=w(n)-不在位数码说明结点与目标的差距。
f(S0)=d(S0)+w(S0)=0+4=4
A算法
在一般图搜索算法中，如果每一步都利用估价函数f(n)=g(n)+h(n)对OPEN表中的结点进行排序，则称该搜索算法为A算法。
由于估价函数带有问题自身的启发性信息，所以A算法也是启发式搜索算法。
A算法-全局择优搜索
产生一个仅有初始结点S0的OPEN表，建立一个仅有初始结点S0的图G,置S0的估价函数f(S0)=g(S0)+h(S0)；
产生一个空的CLOSED表；
如果OPEN表为空，则失败退出；
在OPEN表的首部取一个结点n，将其放入CLOSED表，在OPEN表删除结点n；
A算法-全局择优搜索
考察结点n是否为目标结点，若是，则得到问题的解，成功退出；
若结点不可扩展，则转第3步；
扩展结点n，计算子结点的f(ni), 并为每一个子结点指定父结点,将子结点放入OPEN表中；
按估价函数为OPEN表中的结点排序，转第3步。
A算法-全局择优搜索
例：八数码问题。设初始状态和目标状态如下图，且估价函数为： f(n)=d(n)+w(n)
其中：d(n)表示结点的结点深度；w(n)表示结点n不在位的数码个数。请使用全局择优搜索求解问题。
2 3
1 8 4
7 6 5
2 3
8 4
7 6 5
S0
Sg
A算法-全局择优搜索
解：搜索图为
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
1 2 3
8 4
7 6 5
S0
Sg
S1
S2
S3
S4
S5
S6
S7
S8
4
4
4
6
4
6
7
7
1 2 3
7 8 4
6 5
6
3
A算法-局部择优搜索
产生一个仅有初始结点S0的OPEN表，建立一个仅有初始结点S0的图G,置S0的估价函数f(S0)=g(S0)+h(S0)；
产生一个空的CLOSED表；
如果OPEN表为空，则失败退出；
在OPEN表的首部取一个结点n，将其放入CLOSED表，在OPEN表删除结点n；
A算法-局部择优搜索
考察结点n是否为目标结点，若是，则得到问题的解，成功退出；
若结点不可扩展，则转第3步；
扩展结点n，计算子结点的f(ni), 并为每一个子结点指定父结点, 按估价函数将子结点排序，并放入OPEN表的首部，转第3步。
关于A算法
全局择优搜索：当f(n)=g(n)，算法退化为代价树广度优先搜索；f(n)=d(n)，算法退化为广度优先搜索。
局部择优搜索：当f(n)=g(n)，算法退化为代价树深度优先搜索；f(n)=d(n)，算法退化为深度优先搜索。
A*算法
设f*(n)是从初始状态经由结点n到达目标结点的所有路径中最小路径代价值，f(n)是它的估计值。则f*(n)应由两部分组成：
g＊(n)是从初始结点到结点n的最小代价。
h＊(n)是从结点n到达目标结点的最优路径的代价值，有多个目标结点时取其代价最小者。
所以 f*(n)= g＊(n)+ h＊(n)
A*算法
对A算法-全局择优搜索中的增加如下限制：
g(n)是对g*(n)的估计，并且g(n)>0
h(n)是h*(n)的下界，即对任意结点都有
h(n)<h*(n)
则称此算法为Ａ*算法
A*算法的可纳性
可纳性：如果搜索算法能在有限步内找到一条从初始结点到目标结点的最佳路径，则称该搜索算法是可纳的。
可以证明A*算法是可纳的。
A*算法的最优性
结论：设有两个A*算法A1*和A2*，它们有
A1*: f1(n)=g1(n)+h1(n)
A2*: f2(n)=g2(n)+h2(n)
如果对所有非目标结点均有
h2(n)>h1(n)
则被A2*扩展的结点一定被A1*扩展。
A*算法的最优性
如果启发函数满足以下两个条件：
h(目标结点)=0
对任意结点n和它的子结点m，都有
0≤h(n)-h(m) ≤C(n,m)
C(n,m)是结点到其子结点的边代价，则称h(n)满足单调限制。
A*算法的最优性
结论：如果h满足单调条件，则当A*算法扩展结点n时，该结点就已经找到通往它的最佳路径，即g(n)=g*(n)
A*算法-示例
例：八数码问题。设初始状态和目标状态如下图，且估价函数为： f(n)=d(n)+w(n)
其中：d(n)表示结点的结点深度；w(n)表示结点n不在位的数码个数。请使用A*算法求解问题。
2 3
1 8 4
7 6 5
2 3
8 4
7 6 5
S0
Sg
A*算法-示例
解：在前一个例中取
h(n)=w(n)
w(n)表示结点n不在位的数码个数
显然有 w(n)≤h*(n)
即例中的A算法也是A*算法。
A*算法-示例
还可以选择h(n)=P(n)，其中是每一个数码与其目标位置的距离之和，则有：
P(n)≤h*(n)
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
8 4
7 6 5
S0
Sg
S1
S2
S3
S4
S5
S8
3
3
6
5
3
1 2 3
7 8 4
6 5
3
5
