人工智能实验报告-图搜索策略

《人工智能实验报告-图搜索策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、人工智能第一次实验报告图搜索策略班级：姓名：学号：一、实验目的1.加深对各种图搜索策略概念的理解；2.进一步了解启发式搜索、a・[3剪枝等概念；3.比较并分析图搜索策略的实质，通过实验理解启发式搜索的意义。二、实验要求以九宫问题/八数码问题为例，以某种搜索策略编程演示其搜索过程，最好能采用全局择优搜索，其中的启发式函数自己设计；三、实验算法1•有解和无解如何判定？答：计算两种状态的逆序值，若两者奇偶性相同则可达，不然两个状态不可达。下面是判断的调用函数：intpanduan(structpointx,structpointy)〃判断是否有解{i

2、nti,j,no二0,a[9],b[9],tempi,temp2,numl二0,num2=0;for(i=0;i〈3;i++)for(j=0;j<3;j++){a[no]=x.path[i][j];b[no]=y.path[i][j];no++;}for(i=0;i<9;i++){templ=0;temp2=0;for(j=i+l;j<9;j++){if(a[j]

3、turn0;}2•启发式函数如何设定？答：比较当前状态和目标状态不同位的个数，数值越小的越接近，因此优先扩展,当为0是表示打到目标：intdecide(structpoint*x)//h函数&判断函数{inti,j;intno二0;//no是数字不同的个数for(i=0;i〈3;i++)for(j=0;j<3;j++)//循环比较if(x->path[i][j]!=end.path[i][j])no++;returnno;}3.open表和close表如何实现？答：以结构体存储open表和close表，structpoint{intstep;/

4、/stcp用于存储相异的元素intpath[3][3];structpoint*next;}start,end;structpoint*open[362880];structpoint^closed[362880];4.关键的函数有哪些？①.该函数实现空格的上移：structpointup(structpoint*b,intx,inty){pointnevone=*b;chara;if(x>=0&&x<=2&&y>=0&&y<=2){a二newone.path[x][y];newone.path[x][y]=newone.path[x~l][

5、y];newone.path[x~l][y]=a;}returnnewone;}②.该函数用于将open表中数据排序：voidpaixuO{inti,a二optail;structpoint*x;for(i二optail;Kophead;i++)if(open[optail]->stepstep)a=i;for(i=optail;i

6、i++)//找空格for(j=0;j<3;j++){if(closed[cl]->path[i][j]==0){x=i;y=j;point*up=(point*)malloc(sizeof(structpoint));//向上*up=*closed[cl];if(x>0){up->path[x][y]=up->path[x-l][y];up一〉path[xT][y]=0;}if(testhash(up)){up->step=decide(up);up->next=closed[cl];open[optail]=up;paixu();optai1

7、--；}elsefree(up);point*down二(point*)malloc(sizeof(structpoint));//向下*down=*closed[cl];if(x<2)down->path[x][y]=down-〉path[x+l][y];down->path[x+l][y]=0;}if(testhash(down)){down->step二decide(down);down->next=closed[cl];open[optai1]二down;paixu();optai1一一；}elsefree(down);point*le

8、ft=(point*)malloc(sizeof(structpoint));//向左*left=*closed[cl];if(y>0){left~>