《 人工智能 》 实验大作业 实验题目： 启发式搜索 专业 信息与计算科学 年级 091001 姓名 贾凡 学号 091001103 指导老师 时华 日 期 2012 年 12 月 11 日 一、实验目的： 熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用 A 算法求解九宫问题，理解求解流程和搜索顺序。 二、实验方法： 1.先熟悉启发式搜索算法； 2.用 C、C++或 JAVA 语言编程实现实验内容。 三、实验背景知识： 1 .估价函数 在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。这些控制信息反映在估价函数中。 估价函数的任务就是估计待搜索节点的重要程度，给这些节点排定次序。估价函数可以是任意一种函数，如有的定义它是节点 x 处于最佳路径的概率上，或是 x 节点和目标节点之间的距离等等。在此，我们把估价函数 f(n)定义为从初始节点经过 n 节点到达目标节点的最小代价路径的代价估计值，它的一般形式是： f(n) = g(n) + h(n) 其中 g(n)是从初始节点到节点 n 的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n 到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。 2 . 启发式搜索过程的特性 （1）可采纳性 当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。所有 A*算法都是可采纳的。 （2）单调性 一个启发函数 h 是单调的，如果 a） 对所有的状态 ni 和 nj，其中 nj 是 ni 的子孙，h(ni )- h(nj )≤cost(ni,nj ),其中cost(ni,nj )是从ni 到nj 实际代价。 b） 目标状态的启发函数值为 0，即 h(Goal)=0. 具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的f值是单调递增（不减）。 （3）信息性 比较两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n) ≤h2(n)，就说h2比h1具有更多的信息性。 一般而言，若搜索策略h2比h1有更多的信息性，则h2比h1考察的状态要少。但必须注意的是更多信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处。 3.常用的启发式搜索算法 （1）局部择优搜索算法（瞎子爬山法） 瞎子爬山法是最简单的启发式算法之一。该算法在搜索过程中扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩展；该子节点的兄弟节点和父节点都不再被保留。当搜索到达一种状态，该状态...
