文档介绍：
搜索技术的应用－智能搜索引擎
启发式搜索涉及的基本概念
基本的启发式搜索方法
代价树的广度优先搜索
动态规划法（改进的代价树广度优先搜索)
代价树有界深度优先搜索
启发式搜索搜索技术的应用－智能搜索引擎
启发式搜索概念
启发式搜索与无信息搜索
无信息（盲目）搜索：按预定的控制策略进行搜索，在搜索过程中 获得的中间信息并不改变控制策略。 81
启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导 搜索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。
启发性信息
评估函数
启发式搜索搜索技术的应用－智能搜索引擎
评估函数的表示
含义：用于估价节点重要性的函数称为估价函数
表示： f(x)=g(x)+h(x)
g(x)是从初始结点S0到x实际代价
h(x)是从x到目标结点Sg的最佳路径的估计代价, 启发性信息的函数描述。
例 重排九宫问题 f(x)=d(x)+h(x)
启发式搜索搜索技术的应用－智能搜索引擎
代价的计算
边代价：从父节点到子节点的代价
表示：c(x1,x2)表示从父节点x1到子节点x2的代价
例：c(s0,A)=2 c(A,C)=4
代价：从一个节点经过一条支路到另一个节点所支付的代价。
表示：g(x)表示从初始节点s0到节点x的代价
例: g(A)=g(s0)+c(s0,A)=0+2=2 g(C)=g(A)+c(A,C)=2+4=6
代价树：边上标有代价的搜索树
s0
A
C
B
3
2
4
s0
A
B
C
2
3
4
启发式搜索搜索技术的应用－智能搜索引擎
代价驱动的搜索策略
代价树的广度优先搜索
动态规划法（改进的代价树广度优先搜索)
代价树的深度优先搜索
启发式搜索搜索技术的应用－智能搜索引擎
代价树的广度优先搜索
基本思想
搜索过程
实例
存在问题
解决方法(动态规划法）
启发式搜索搜索技术的应用－智能搜索引擎
基本思想
open表的节点顺序按的节点代价排列（从小到大）
启发式搜索搜索技术的应用－智能搜索引擎
搜索过程
,令g(s0)=0
，则问题无解，退出
（记为n节点）取出放入CLOSED表
。若是，则求得了问题的解，退出。
（2）步。
，将其子节点放入OPEN表中，并为每一个子节点都配置指向父节点的指针；计算各个子节点的代价，并按各个节点的代价对表的全部节点进行排序（按从小到大的顺序），然后转（2）步。
启发式搜索搜索技术的应用－智能搜索引擎
例 如图是八城市间的交通图，两城市间的交通费用（代价）如图中数字所示。
S
A
D
E
B
F
T
C
3
4
4
5
2
5
4
4
3
启发式搜索搜索技术的应用－智能搜索引擎
代价树的广度优先搜索（例）
1
2
3
4
5
6
7
10
11
12
13
8
9
19
20
21
15
17
18
14
S(0)
D1(4)
A1(3)
B1( 7 )
D2(8)
A2(9)
E1(6)
F1(10)
T1(13)
C1(11)
B2(11)
B3(13)
E3(10)
E2(12)
16
D3(14)
F3(16)
B4(15)
F2(14)
C3(17)
A3(15)
C2(15)
3
4
4
4
5
5
5
2
4
5
4
2
2
4
5
4
4
4
4
3
启发式搜索搜索技术的应用－智能搜索引擎