《教学人工智能实验大作业》由会员分享，可在线阅读，更多相关《教学人工智能实验大作业（11页珍藏版）》请在金锄头文库上搜索。
1、? 人工智能 ?实验大作业实验题目： 启发式搜索 专业 信息与计算科学 年级 091001 姓名 贾凡 学号 091001103 指导老师 时华 日 期 2021年12月11日 一、实验目的：熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用算法求解九宫问题，理解求解流程和搜索顺序。二、实验方法：1.先熟悉启发式搜索算法； 2.用C、C+或JV语言编程实现实验内容。三、实验背景知识：在对问题的状态空间进行搜索时，为提高搜索效率需要和被解问题的解有关的大量控制性知识作为搜索的辅助性策略。这些控制信息反映在估价函数中。估价函数的任务就是估计待搜索节点的重要程度，给这些节点排定次序。估价函数可以
2、是任意一种函数，如有的定义它是节点x处于最正确路径的概率上，或是x节点和目标节点之间的距离等等。在此，我们把估价函数(n)定义为从初始节点经过n节点到达目标节点的最小代价路径的代价估计值，它的一般形式是： (n) = g(n) + h(n)其中g(n)是从初始节点到节点n的实际代价，g(n)可以根据生成的搜索树实际计算出来；h(n)是从n到目标节点的最正确路径的代价估计，h(n)主要表达了搜索的启发信息。2. 启发式搜索过程的特性1可采纳性当一个搜索算法在最短路径存在的时候能保证能找到它，我们就称该算法是可采纳的。所有*算法都是可采纳的。2单调性一个启发函数h是单调的，如果a） 对所有的状态n
3、i和 nj，其中nj是ni的子孙，h(ni )- h(nj )cost(ni,nj ),其中cost(ni,nj )是从ni到nj 实际代价。b） 目标状态的启发函数值为0，即h(Gol)=0.具有单调性的启发式搜索算法在对状态进行扩展时能保证所有被扩展的状态的值是单调递增不减。3信息性比拟两个启发策略h1和h2，如果对搜索空间中的任何一个状态n都有h1(n) h2(n)，就说h2比h1具有更多的信息性。一般而言，假设搜索策略h2比h1有更多的信息性，那么h2比h1考察的状态要少。但必须注意的是更多信息性需要更多的计算时间，从而有可能抵消减少搜索空间所带来的益处。1局部择优搜索算法瞎子爬山法瞎
4、子爬山法是最简单的启发式算法之一。该算法在搜索过程中扩展当前节点并估价它的子节点。最优的子节点别选择并进一步扩展；该子节点的兄弟节点和父节点都不再被保存。当搜索到达一种状态，该状态比它的所有子状态都要好，那么搜索停止。因此，该算法的估价函数可表示为(n) = h(n)。在一个限定的环境下，瞎子爬山法可能会极大的提高搜索的效率，但是对整个搜索空间而言，可能得不到全局最优解。2最好优先搜索法有序搜索法该算法的估价函数采用(n) = g(n) + h(n)，在搜索过程中算法使用OPEN表和CLOSE表来记录节点信息：OPEN表中保存所有已生成而未考察的节点；CLOSE表中保存所有已访问过的节点。算法
5、在每一次搜索过程中都会对OPEN表中的节点按照每个节点的值进行排序，选择值最小节点进行扩展。算法的描述如下： 把起始节点S放到OPEN表中，计算(S),并把其值与节点S联系起来。 假设OPEN是个空表，那么算法失败退出，无解。 从OPEN表中选择一个值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，那么选择此目标节点，否那么就选择其中任一个节点作为节点i 。 把节点i从OPEN表中移出，并把它放入到CLOSED的扩展节点表中。 假设节点i是个目标节点，那么成功退出，求得一个解。 扩展i，生成其全部后继节点。对i的每个后继节点j：（a） 计算(j)。（b） 如果j既不在OPEN表中，
6、也不在CLOSED表中，那么用估价函数将其添加到OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。（c） 如果j已那么OPEN表中或CLOSED表中，那么比拟刚刚对j计算过的值和前面计算过的该节点在表中的的值。假设新的值较小，那么（i） 以此值取代旧值。（ii） 从j指向i，而不是指向它的父辈节点。（iii） 假设节点j在CLOSED表中，那么把它移回OPEN表。 转向。四、实验内容：问题描述：用启发式搜索方法求解以下九宫问题283164 7512384 765五、 实验原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位
7、置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数表示的，如：最正确优先搜索的最广为人知的形式称为*搜索(发音为“星搜索).它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：(n)=g(n)+h(n)因为以g(n)给出了从起始节点到节点n的路径耗散，而h(n)是从节点n到目标节点的最低耗散路径的估计耗散值，因此(n)=经过节点n的最低耗散解的估计耗散.这样，如果我们想要找到最低耗散解，首先尝试找到g(n)+h(n)值最小
8、的节点是合理的。可以发现这个策略不只是合理的:倘假设启发函数h(n)满足一定的条件，*搜索既是完备的也是最优的。如果把*搜索用于Tree-Serch,它的最优性是能够直接分折的。在这种情况下，如果h(n)是一个可采纳启发式-也就是说，倘假设h(n)从不会过高估计到达目标的耗散-*算法是最优的。可采纳启发式天生是最优的，因为他们认为求解问题的耗散是低于实际耗散的。因为g(n)是到达节点n确实切耗散，我们得到一个直接的结论：(n)永远不会高估经过节点n的解的实际耗散。启发算法有： 蚁群算法，遗传算法、模拟退火算法等，蚁群算法是一种来自大自然的随机搜索寻优方法，是生物界的群体启发式行为，现己陆续应用
9、到组合优化、人工智能、通讯等多个领域。蚁群算法的正反应性和协同性使其可用于分布式系统，隐含的并行性更使之具有极强的开展潜力。从数值仿真结果来看，它比目前风行一时的遗传算法、模拟退火算法等有更好的适应性。六、 代码#include #includestruct nodeint 33;/用二维数组存放8数码 int hx;/函数hx的值，表示与目标状态的差距struct node *prent;/指向父结点的指针struct node *next;/指向链表中下一个结点的指针;int hx(int s33)int i,j;int hx=0;int sg33=1,2,3,8,0,4,7,6,5;or
10、(i=0;i3;i+)or(j=0;jnext=NULL;/初始化or(i=0;i3;i+)or(j=0;jij=0)lg=1;brek;i(lg=1)brek; or(m=0;m赋给xor(n=0;nmn; i(i-1=0)t=xij;xij=xi-1j;xi-1j=t; lg=0;or(m=0;m3;m+)/将x赋给 or(n=0;nprent-mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(node); or(m=0;m3;m+)/将x赋给 or(n=0;nmn=xmn; q-prent=ex; q-hx=hx(q-); q-next=NULL; p-ne
11、xt=q; p=p-next; or(m=0;m重新赋给x，即复原xor(n=0;nmn;i(i+1=2)t=xij;xij=xi+1j;xi+1j=t; lg=0;or(m=0;m3;m+) or(n=0;nprent-mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(node); or(m=0;m3;m+)/将x赋给 or(n=0;nmn=xmn; q-prent=ex; q-hx=hx(q-); q-next=NULL; p-next=q; p=p-next; or(m=0;m重新赋给x，即复原xor(n=0;nmn;i(j-1=0) t=xij;xij=xij-1;xij-1=t;lg=0;or(m=0;m3;m+) or(n=0;nprent-mn) lg+; i(lg!=9) q=(node *)mlloc(sizeo(node);
