《何昭霞状态空间搜索启发式搜索》由会员分享，可在线阅读，更多相关《何昭霞状态空间搜索启发式搜索（19页珍藏版）》请在金锄头文库上搜索。
1、重庆交通大学计算机与信息学院验证性实验报告班 级： 软件开发 专业 2013 级 1 班 学 号： 631306050105 姓 名： 何昭霞 实验项目名称： 状态空间搜索 实验项目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼） 指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 10 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 1. 理解和掌握状态空间搜索的策略。 2.熟悉人工智能系统中的问题求解过程； 3.熟悉状态空间的盲目搜索和启发式搜索算法的应用； 4.熟悉对八数码问题的建模、求解及编程语言的应用。二、实验内容及要求
2、（一）实验内容在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。 （二）实验要求 用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件 PC机一台、Visual Studio 2012编程软件四、设计方案 题目 状态空间搜索 8数码问题 设计的主要思路考虑广度优先算法：(1) 状态空间盲目搜索宽度优先搜索其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察
3、它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。(2) 宽度优先算法如下首先把初始结点S0放入OPEN表中，然后若OPEN表为空，则搜索失败，问题无解，接着取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n，若目标结点Sg=N，则搜索成功，问题有解。若N无子结点，则重复取OPEN表中最前面的结点N放在CLOSE表中。扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，然后重复取OPEN表中最前面的结点N放在CLOSE表中。
4、根据算法的中心思想进行程序设计，其流程图如下图所示。 主要功能使用C语言相关知识，将3*3的九宫格调整为某种有序的形式。五、主要代码#include #include struct node int x,y; int cntdif;int step; int f9; int xy33; queue10000; int map33; int dir42=-1,0,1,0,0,1,0,-1; int open10000; int zz9; int f1,f2; struct node sour,dest; queuetail.fi*3+j=queuetail.xyij=ffi*3+j; queue
5、tail.step=HH.step+1; queuetail.x=sx; queuetail.y=sy; tdif=count(queuetail.f,zz); opentail=visit(queuetail.f); print(queuetail.xy); if(match(queuetail) printf(step(s):%d！n,queuetail.step); return; qsort(queue+head,tail-head+1,sizeof(queue0),comp);/排序，每次选择cntdif数目最小的扩展 int main() int i,j,a9,b9; printf
6、(Please input the nitial status,input 0 to the vacant position :n); for(i=0;i3;i+) for(j=0;j3;j+) scanf(%d,&mapij); sour.xyij=mapij; sour.fi*3+j=mapij; ai*3+j=mapij; if(mapij=0) sour.x=i; sour.y=j; sour.step=0; tdif=0; printf(Please input the final status:n); for(i=0;i3;i+) for(j=0;j3;j+) scanf(%d,&
7、mapij); dest.xyij=mapij; dest.fi*3+j=mapij; bi*3+j=mapij; zzi*3+j=mapij; printf(n); if(judge(a)+judge(b)&1) printf(The final status cannot be reached .); return 0; printf(The searching process is:n); bfs(); return 0; 六、测试结果及说明 七、实验体会 人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法），启发式搜索算法有A算法、A*算
8、法。我在本实验中，采用的是宽度优先（广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不用来改进控制策略。由于搜索总是按预定的路线进行，没有考虑问题本身的特性，这种缺乏问题求解的针对性，需要进行全方位的搜索，而没有选择最优的搜索路径。通过这次实验更加熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法及计算机语言对常用数据结构如链表、队列等的描述应用。因此，我对人工智能搜索有了更深的认识。 重庆交通大学计算机与信息学院验证性实验报告班 级： 软件开发 专业 2013 级 1 班 学 号： 631306050105 姓 名： 何昭霞 实验项目名称： 启发式搜索 实验项
9、目性质： 验证性实验 实验所属课程： 人工智能 实验室(中心)：软件中心实验室（语音楼8楼） 指 导 教 师 ： 朱振国 实验完成时间： 2016 年 6 月 10 日评阅意见：实验成绩： 签名： 年 月 日一、实验目的 理解和掌握A*算法。二、实验内容及要求（一）实验内容在8数码问题中，利用策略函数判断搜索，并使用A*算法减少搜索目标。 （二）实验要求 用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件 PC机一台、Visual Studio 2012编程软件四、设计方案 题目 启发式搜索A*算法 设计的主要思
10、路根据任务要求，该实验我采用A*搜索算法。对于八数码问题的解决,首先要考虑是否有答案。每一个状态可认为是一个19的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵.由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。如果初始状态可以到达目标状态,常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。在这里就要用到启发式搜索启发中的估
11、价是用估价函数表示的,如:f(n)=g(n)+h(n)其中f(n)是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。在此八数码问题中,显然g(n)就是从初始状态变换到当前状态所移动的步数,估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数,即错位数。 1.状态的表示 在A*算法中，需要用到open表和closed表，特别是在open表中，待扩展节点间有很严格的扩展顺序。因此在表示当前状态的变量中，与数据结构中的链表相似，必须要有能指向下一个扩展节点的指针，以完成对open表中元素的索引。这里表示问题的结构体包括
12、表示当前节点状态的DATA和指向open表中下一个待扩展节点的指针NEXT。其中DATA中包括的内容采用一个的二维数组s33表示当前状态的具体信息。而为了保证在搜索到目标状态后能够顺利复现寻优路径，当前状态的DATA中还应该包括一个指向其父节点的指针father，这样，才能在达到目标状态后，通过指针father逐层回溯到初始状态，即复现寻优路径。2.启发函数的设计 根据A*算法的定义，启发函数应满足：h(n)=h*(n)其中h*(n)表示从当前节点n到目标节点s_g的最优路径的实际代价。3. 规则库设计 0在某一位置时，能选择向左、向右、向上、向下移动中的哪几种策略进行移动，主要是由当前0所处位置（更具体地说是当前位置的行列号）和其祖父节点（为提高搜索效率，新扩展的节点应当至少不为其祖父节点）所决定的。当然，按照A*算法的思想，每扩展出一个新节点，都要判断其是否为有效子节点，不为有效子节点的不能加入到open表中。 主要功能使用C+语言的相关知识，利
