注：1)这里，搜索的对象(常称状态)往往是边 搜索边生成，因此在考虑这种搜索的复杂性时， 必须将搜索对象的生成和评估的代价计算在内。
8
第三章 搜索技术
第二节 启发式搜索
一、启发式搜索
注：2)根据启发性信息(特定领域的知识信息)， 在生成搜索树时可考虑种种可能的选择：
a)下一步展开哪个节点？ b)是部分展开还是全部展开？ c)使用哪个规则(算子)？ d)怎样决定舍弃还是保留新生成的节点？ e)怎样决定舍弃还是保留一棵子树？ f)怎样决定停止或继续搜索？ g)如何定义启发函数(估值函数)？ h)如何决定搜索方向？
22
第三章 搜索技术
第二节 启发式搜索 五、H*算法 注：5)若估计值函数h(n)满足单调条件：
h(ni)-h(nj) k*(ni,nj)（其中k*(ni,nj)是从ni到nj的 最小代价，nj是ni的后续节点）， 则H*算法是循着从初始状态通向该节点的最优路 径到达该节点的。
6)在H*算法中，每次只生成一个后续节点。
5
第三章 搜索技术
第一节 引言 二、研究和选用搜索算法的原则 10、有对手搜索还是无对手搜索？
若有两个控制源均能改变同一状态空间，并且 任何一方向目标前进时，另一方均试图将它从目 标拉开，则称为有对手搜索，通常称为博弈搜索。 注：博弈搜索算法可以看成是一种特殊的问题空 间搜索。
6
第三章 搜索技术
八、A*算法 注： 3)A*算它的效率，则 当启发式函数h的值单调上升时，它的效率只会 上升，不会下降，且有较合理的渐近性质
5)若不是考虑被展开的节点个数，而是考虑 各节点被展开的次数，则A*算法在最坏情况下表 示出很高的复杂性
第二节 启发式搜索 六、完全展开的有序搜索算法 6)若在SS或SB中原有一个状态与当前某个新状态 共一个状态，则删去原有状态 7)若SS的第一项是一个新状态，则转11) 8)若某种状态极限已达到，则搜索失败，算法运 行结束，无解
