4．搜索算法的研究工作

　　算法是N.J.Nilsson70年代初的研究成果，是从函数的观点来讨论搜索问题，并在理论上取得若干结果。但算法不能完全克服"指数爆炸"的困难。
　　70年代末J.Pear1从概率观点研究了启发式估计的精度同A*算法平均复杂性的关系。Pear1假设如下的概率搜索空间：一个一致的m-枝树G，在深度d处有一个唯一的目标节点Gd，其位置事先并不知道。
　　设估计量h(n)是在[0，h*(n)]区间中的随机应量，由分布函数来描述；E（Z）表示用A*算法求到目标时所展开的节点平均个数，并称之为A*的平均复杂性。若h(n)满足

　　80年代初，张钹、张铃提出把启发式搜索看成某种随机取样的过程，从而将统计推断引入启发式搜索。把各种统计推断方法，如序贯概率比检验法（SPRT），均值固定宽度信度区间渐近序贯法（ASM）等，同启发式搜索算法相结合，得到一种称为SA（统计启发式）的搜索算法。该算法在一定假设条件下，能以概率为一找到目标，且其平均复杂性为O（dlnd）或，而且证明其所需的条件比使搜索为多项复杂性的条件为弱。
　　总之搜索策略是人工智能研究的核心问题之一，已有许多成熟的结果，并在解决人工智能的有关问题中得到广泛应用。但目前仍有若干深入的问题有待发展，特别是结合实际问题，探索有效实用的策略仍是一个研究和开发的工作，还应当给予足够的重视。