安徽大学人工智能实验一.doc

人工智能实验报告实验名称 八数码问题实验时间 2014.11.6院系 计算机科学与技术学院班级 软件工程2班学号 E01214281姓名 周公谨1. 实验目的: 、 熟悉人工智能系统中的问题求解过程；熟悉状态空间的盲目搜索和启发式搜索算法的应用；熟悉对八数码问题的建模、求解及编程语言的应用。2.实验原理广度优先算法：(1) 状态空间盲目搜索宽度优先搜索其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。(2) 宽度优先算法如下步1 把初始结点S0放入OPEN表中步2 若OPEN表为空，则搜索失败，问题无解 步3 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 步4 若目标结点Sg=N，则搜索成功，问题有解 步5 若N无子结点，则转步2 步6 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转步2 3.实验内容在33的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态，输出全局择优搜索全过程。4.实验代码与结果#include#includestruct 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;int judge(int a) /用逆序数判断是否可达 int i,j,k=0; for(i=1;i9;i+) if(ai) for(j=0;jai) k+; return k;int count(int a,int b)/计算不一样的个数 int i,j; for(i=j=0;i9;i+) if(ai!=bi)j+; return j;int match(struct node m) /判断是否和末状态匹配 int i,j; for(i=0;icntdif=b-cntdif)return a-step-b-step; return a-cntdif-b-cntdif;int visit(int x)/返回hash函数值 int i,cnt=1,sum=0; for(i=0;i9;i+) sum+=xi*cnt+; return sum;void print(int f3) int i,j; for(i=0;i3;i+) for(j=0;j3;j+) printf(%d ,fij); printf(n); printf(n);void bfs()/全局择优算法 int p,val,i,j,ff9,flin=0; int head=0; int tail=0; memset(queue,0,sizeof(queue); queuehead=sour; tdif=count(queuehead.f,zz); openhead=visit(queuehead.f); print(queuehead.xy);/打印头结点 while(head=tail) struct node HH=queuehead+; int sx,sy; for(p=0;p4;p+) flin=0; for(i=0;i=0&sx=0&sy3) ffsx*3+sy=0; ffHH.x*3+HH.y=HH.xysxsy; for(j=0;j10000;j+)/判断是否是已经有过的状态,看open表中是否已有 if(openj=visit(ff) flin=1; break; if(flin)continue; tail+; for(i=0;i3;i+) for(j=0;j3;j+) queuetail.fi*3+j=queuetail.xyij=ffi*3+j; queuetail.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(Please input the initial 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,&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;5.实验总结人工智能搜索可分为盲目搜索和启发式搜索。盲目搜索算法有宽度优先算法、深度优先算法（有界深度优先算法），启发式搜索算法有A算法、A*算法。本实验采用的是宽度优先（广度优先）算法，这种算法是按预定的控制策略进行，在搜素的过程中所获得的信息不