运用启发式策略的两种基本情况:
(1) 一个问题由于存在问题陈述和数据获取的模糊性,可能会使它没有一个确定的解。
(2)虽然一个问题可能有确定解,但是其状态空间特别大,搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。
启发式信息
用来简化搜索过程有关具体问题领域的特性的信息叫做启发信息。
估价函数
估价函数(evaluation function):估算节点“希望”度的量度。
估价函数值f（n):从初始节点经过节点到达目标节点路径的最小代价估计值,其一般形式是
f(n) = g(n)+ h(n)
g(n):从初始节点S到节点n的实际代价;
h(n):从节点n到目标节点S的最优路径的估计代价,称为启发函数。
h(n）比重大:降低搜索工作量,但可能导致找不到最优解;
h(n)比重小:一般导致工作量加大,极限情况下变为盲目搜索,但可能可以找到最优解。
A*搜索算法
使用了估价函数f的最佳优先搜索。
估价函数n)= g(n) +h(n)
如何寻找并设计启发函数(n),然后以fn)的大小来排列OPEN表中待扩展状态的次序,每次选择n)值最小
者进行扩展。
g(n):状态n的实际代价,例如搜索的深度;
h(n):对状态n与目标“接近程度”的某种启发式估计。
