631306050105何昭霞 状态空间搜索 启发式搜索

《631306050105何昭霞 状态空间搜索 启发式搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、重庆交通大学计算机与信息学院验证性实验报告班级：软件开发专业2013级1班学号：631306050105姓名：何昭霞实验项目名称：状态空间搜索实验项目性质：验证性实验实验所属课程：人工智能实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国实验完成时间：2016年6月10日评阅意见：实验成绩：签名：年月日一、实验目的1.理解和掌握状态空间搜索的策略。2.熟悉人工智能系统中的问题求解过程；3.熟悉状态空间的盲目搜索和启发式搜索算法的应用；4.熟悉对八数码问题的建模、求解及编程语言的应用。二、实验内容及要求（一）

2、实验内容在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相邻的一个数字平移到空格中。（二）实验要求用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）。三、实验设备及软件PC机一台、VisualStudio2012编程软件四、设计方案㈠题目状态空间搜索8数码问题㈡设计的主要思路考虑广度优先算法：(1)状态空间盲目搜索——宽度优先搜索其基

3、本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。(2)宽度优先算法如下首先把初始结点S0放入OPEN表中，然后若OPEN表为空，则搜索失败，问题无解，接着取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n，若目标结点Sg=N，则搜索成功，问题有解。若N无子结点，则重复取OPEN表中最前面的结点N放在CLOSE表

4、中。扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，然后重复取OPEN表中最前面的结点N放在CLOSE表中。根据算法的中心思想进行程序设计，其流程图如下图所示。㈢主要功能使用C语言相关知识，将3*3的九宫格调整为某种有序的形式。五、主要代码#include#includestructnode{intx,y;intcntdif;intstep;intf[9];intxy[3][3];}queue[10000];intmap[3][3];intdir[4]

5、[2]={{-1,0},{1,0},{0,1},{0,-1}};intopen[10000];intzz[9];intf1,f2;structnodesour,dest;queue[tail].f[i*3+j]=queue[tail].xy[i][j]=ff[i*3+j];queue[tail].step=HH.step+1;queue[tail].x=sx;queue[tail].y=sy;queue[tail].cntdif=count(queue[tail].f,zz);open[tail]=visit(que

6、ue[tail].f);print(queue[tail].xy);if(match(queue[tail])){printf("step(s):%d！",queue[tail].step);return;}}}qsort(queue+head,tail-head+1,sizeof(queue[0]),comp);//排序，每次选择cntdif数目最小的扩展}}intmain(){inti,j,a[9],b[9];printf("Pleaseinputthenitialstatus,input0tothevaca

7、ntposition:");for(i=0;i<3;i++)for(j=0;j<3;j++){scanf("%d",&map[i][j]);sour.xy[i][j]=map[i][j];sour.f[i*3+j]=map[i][j];a[i*3+j]=map[i][j];if(map[i][j]==0){sour.x=i;sour.y=j;sour.step=0;sour.cntdif=0;}}printf("Pleaseinputthefinalstatus:");for(i=0;i<3;i++)for(

8、j=0;j<3;j++){scanf("%d",&map[i][j]);dest.xy[i][j]=map[i][j];dest.f[i*3+j]=map[i][j];b[i*3+j]=map[i][j];zz[i*3+j]=map[i][j];}printf("");if((judge(a)+judge(b))&1){printf("Th