人工智能大作业

《人工智能大作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《人工智能》实验大作业实验题目：启发式搜索专业信息与计算科学年级091001姓名贾凡学号091001103指导老师时华日期2012年12月11日一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A算法求解九宫问题，理解求解流程和搜索顺序。二、实验方法：1.先熟悉启发式搜索算法；2.用C、C++或JAVA语言编程实现实验内容。三、实验背景知识：1.估价函数在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。这些控制信息反映在估价函数中。估价函数的任务就是估计待搜索节点的重要程度，给这些

2、节点排定次序。估价函数可以是任意一种函数，如有的定义它是节点x处于最佳路径的概率上，或是x节点和目标节点之间的距离等等。在此，我们把估价函数f(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值，它的一般形式是：f(n)=g(n)+h(n)其中g(n)是从初始节点到节点n的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n到目标节点的最佳路径的代价估计，h(n)主要体现了搜索的启发信息。2.启发式搜索过程的特性（1）可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。所有A*算法都是可采

3、纳的。（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考察的状态要少。但必须注意的是

4、更多信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处。3.常用的启发式搜索算法（1）局部择优搜索算法（瞎子爬山法）瞎子爬山法是最简单的启发式算法之一。该算法在搜索过程中扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩展；该子节点的兄弟节点和父节点都不再被保留。当搜索到达一种状态，该状态比它的所有子状态都要好，则搜索停止。因此，该算法的估价函数可表示为f(n)=h(n)。在一个限定的环境下，瞎子爬山法可能会极大的提高搜索的效率，但是对整个搜索空间而言，可能得不到全局最优解。（2）最好优先搜索法（有序搜索法）该算法的估价函数采用f

5、(n)=g(n)+h(n)，在搜索过程中算法使用OPEN表和CLOSE表来记录节点信息：OPEN表中保留所有已生成而未考察的节点；CLOSE表中保留所有已访问过的节点。算法在每一次搜索过程中都会对OPEN表中的节点按照每个节点的f值进行排序，选择f值最小节点进行扩展。算法的描述如下：①把起始节点S放到OPEN表中，计算f(S),并把其值与节点S联系起来。②若OPEN是个空表，则算法失败退出，无解。③从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。④把节点i从OP

6、EN表中移出，并把它放入到CLOSED的扩展节点表中。⑤若节点i是个目标节点，则成功退出，求得一个解。⑥扩展i，生成其全部后继节点。对i的每个后继节点j：（a）计算f(j)。（b）如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f将其添加到OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。（c）如果j已则OPEN表中或CLOSED表中，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f的值。若新的f值较小，则（i）以此值取代旧值。（ii）从j指向i，而不是指向它的父辈节点。（iii）若节点j在CLO

7、SED表中，则把它移回OPEN表。⑦转向②。四、实验内容：问题描述：用启发式搜索方法求解下列九宫问题2831647512384765五、实验原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数表示的，如：最佳优先搜索的最广为人知的形式称为A*搜索(发音为“A星搜索”).它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n

8、)结合起来对节点进行评价：f(n)=g(n)+h(n)因为以g(n)给出了从起始节点到节点n的