您现在的位置是：自然百科

搜索

2023-03-13 15:58自然百科人已围观

[拼音]：sousuo

[外文]：search

寻找问题的解的过程或技术，是人工智能中问题求解的基本方法。

搜索空间与搜索图

在问题求解中搜索空间包括状态空间和一切非状态空间。搜索过程中在计算机内部实际形成的部分搜索空间称为搜索图。搜索的目的就是用尽量小的搜索图找到问题的解。

在问题求解系统中，问题表示有两种基本方法：状态空间表示法和问题归约表示法。在状态空间表示法中，状态空间的节点表示状态，即问题求解过程的不同阶段，两节点之间的有向弧线则代表状态转移。在问题归约表示法中，原始问题被分解为若干子问题，这些子问题又进一步被分解为更低层次的若干子问题，节点之间的有向弧线则代表问题的归约，这样就形成了问题归约空间。问题归约空间和状态空间是不同类型的搜索空间。

搜索空间一般用图表示。在实际问题中有时搜索空间是无限的(如定理的机器证明情形)。在棋类游戏中虽然搜索空间有限，但有些棋类其不同棋局总数高达10¹²⁰。因此把同整个搜索空间对应的图（称为隐含图）全部显式表示出来既无可能也无必要。通常只将与部分搜索空间对应的隐含图的子图，即搜索图显式表示出来。

限制搜索量

搜索必须在合理的时间和计算机存储容量条件下完成。对复杂的现实问题，穷举搜索难以实现。例如要列出某种棋类游戏的全部可能着法，那么搜索空间内节点数将随步数n成指数规律增长,这种现象称为指数爆炸。限制搜索量的基本途径是改进问题表示方法，采用启发式搜索，引入问题求解的其他技术，例如行动计划等。

无信息搜索

如果在搜索过程中不使用与问题领域有关的启发信息，这种搜索就称为无信息搜索，或盲式搜索。例如对搜索树可按节点扩展顺序予以分类。所谓扩展某一节点，指的是将该节点所有后继节点全部求出。宽度优先搜索是按照节点与起始节点相隔辈分的高低来扩展节点的,也就是说在所有长度为n的算子序列分析完毕以前不考虑长度为 n+1的算子序列。如果问题的解存在，用宽度优先搜索策略可望得到最短的算子序列，即最短的解题通路。深度优先搜索的特征是首先扩展最新生成的或最深的节点，直到已无可扩展的节点或搜索深度已达到规定限度。这时返回到最邻近的分支，继续搜索。无信息搜索虽然方法简单，但效率很低，难以用于直接解决复杂的实际问题。

启发式搜索

一种依靠直观和经验知识的搜索方法。如运用得当，能大幅度地减少搜索工作量。但是启发式搜索并不保证获得问题的最优解，甚至还不一定保证得到问题的一个解。实践表明，如果问题有解，好的启发式搜索方法在大多数场合下能给出令人满意的结果。运用启发式搜索的基本方法如下：

（1）决定下一步要扩展的节点（并不机械地遵循宽度优先或深度优先方法），有序搜索或称最佳优先搜索就遵循这一途径。每次选择最有希望的节点优先扩展。为了对“有希望”的程度进行度量，需要建立评价函数。“有希望”的涵义和相应评价函数的具体构造完全取决于问题的性质和要求。这里需要权衡的两个因素是解的简明性（搜索图的解题通路所花费的节点和有向弧线数目最小）和搜索工作量的大小。对于有序状态空间搜索，已按照使解题通路花费最小的目的建立了A^*算法和相应的评价函数。这类A^*算法还以分枝限界法的名称在运筹学中得到广泛的应用。

（2）在对节点进行扩展时决定哪一个或哪一些后继节点首先生成，而不是盲目地同时生成所有后继节点，许多博弈程序遵循这一途径，如对策树搜索。

（3）决定有些节点不再展开，应从搜索树中剪除。剪除的原因可能是因为展开这些节点对找到解题通路的作用不大，也可能是出于其他策略的考虑。

对策树搜索

采用最小最大方法的基本技术。下图为一对策树，树中每一节点代表一个棋局的局面。树的非终端标上棋手代码，表示此时由该方走下一步棋。所谓最小最大方法是两人共同遵循的策略，即一方希望自己得分最大，因此称max方,而另一方则希望自己得分最小,因此称min方。对策树的终端节点（终结局面）用静态评价函数评分。当棋手从某一局面出发决定下一步棋时,要对该局面用返回法评分。对策树是一种与或树(见问题求解),凡一方能控制的局面其后继节点是或节点，一方不能控制的局面其后继节点则是与节点。图中的对策树是站在max一方画出的。在图a中，不管评价函数F(5)的值是多少,max一方在局面①能确保的下限值（或称α 值）为F(2)=15,所以节点⑤已没有必要扩展而予以剪除，称为α 截枝；同理图b不管评价函数 F(7)的值是多少,max一方在局面①得分的上限值（或称β值）为F(4)=20,节点⑦也不再扩展而予以剪除,称为β 截枝，α截枝和β 截枝统称为α-β剪枝技术,它改进了原来实施穷举搜索的最小最大法，从而提高了搜索效率。人们一度曾将α-β剪枝技术看成是启发式方法,后来证明它有严格的理论算法。

参考书目

N.J.尼尔逊著，石纯一等译：《人工智能原理》，科学出版社，北京，1983。(N.J.Nilsson, Principles of Artificial Intelligence, Tioga Publ. Co., New York, 1980.)
Judea Pearl,Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley Publ.Co.,Inc., Reading, Mass.,1984.

参考文章