2007级_高级人工智能_试卷答案

《高级人工智能》试卷答案（2007级）一、简答题：1.初始状态S0=(0,1,2,1,3,0)，首先定义两个操作：分别把箱子A，箱子B推到目标状态。首先机器人向左推3格得到状态S1＝(0,1,2,1,0,0),机器人推箱子向上走两格得到状态S2＝(0,3,2,1,0,2)第二步，机器人返回去推箱子B，得状态S3＝(0,3,2,1,3,1),机器人推箱子B向左走一格得状态S4＝(0,3,1,1,2,1)，机器人再向下走一格，再向左走格得状态S5=(0,3,1,3,3,0)最后机器人推着箱子B向上走两眇到达目标状态S6＝(0,3,1,3,3,0)2.FOIL算法1）生成训练子集合T（包括正例和负例），如果T包含正例，则继续，否则结束;2）用目标谓词初始化1个新子句头P(V1,V2…..,Vk);3）生成一个新的训练集合T1，T1-T;4）如果T1中包含负例，则在背景知识中找到一个约束L，添加在子句P的右边，否则车到7）5）生成新的空的训练集合T2，如果T1中的每个元素ti和基于约束L的每一个绑定（扩展）bi都满足L，则将bi加入到ti中，将ti加入到T2中。6）T1-T2,转到4）；7）结束。3.从结点S0开始搜索，S0不是目标结点G，则扩展S0，由f(n)=V(n)/10+D(n)得如下两式：f(S1)=3/10+1f(S2)=7/10+1由于S1、S2不是目标结点G，则从S1、S2中选取代价最小的进行扩展，对S1进行扩展得如下两式：f(S3)=5/10+2f(S4)=10/10+2由于S3、S4不是目标结点G，则从S3、S4、S2中选取代价最小的进行扩展，对S2进行扩展得如下两式：f(G)=14/10+2f(S5)=13/10+2找到所求结点G，搜索停止。4.9个方格的一字棋博弈问题算法具体实现（C++实现）#includestdio.h#includestring.h#includeiostream.hconstintmaxwin=32767;constintminwin=-32767;constintMAX=3;intpai;structnode{intvalue;intfather;charpf[MAX][MAX];intfloor;intson;};classchess{private:intdep;intp,q,ppp;nodequeue[10000];intsign[10000];public:voidinit();voidprint(chartemp[3][3]);intequal(chara[MAX][MAX],charb[MAX][MAX]);intGetAllMoves(nodef,intp,int&bit);intche(charf[MAX][MAX],intx,charch);intcheck(charf[MAX][MAX]);intfun(charf[MAX][MAX]);intmaxnum(inta,intb);intminnum(inta,intb);intmax(intdepth,nodef,intvf_min);intmin(intdepth,nodef,intvf_max);intwork(charsump[3][3],int&x,int&y);};voidchess::print(chartemp[3][3]){inti,j;printf(stateis:\n);printf(+-+-+-+\n);for(i=0;iMAX;i++){for(j=0;jMAX;j++){if(temp[i][j]=='c')printf(|);elseprintf(|%c,temp[i][j]);}printf(|\n+-+-+-+\n);}//printf(Itsvalueis%d,itsflooris%d\n,f.value,f.floor);return;}//打印结点的状态intchess::che(charf[MAX][MAX],intx,charch){if(x==0)if(f[0][0]==ch&&f[0][1]==ch&&f[0][2]==ch)return1;if(x==1)if(f[1][0]==ch&&f[1][1]==ch&&f[1][2]==ch)return1;if(x==2)if(f[2][0]==ch&&f[2][1]==ch&&f[2][2]==ch)return1;if(x==3)if(f[0][0]==ch&&f[1][0]==ch&&f[2][0]==ch)return1;if(x==4)if(f[0][1]==ch&&f[1][1]==ch&&f[2][1]==ch)return1;if(x==5)if(f[0][2]==ch&&f[1][2]==ch&&f[2][2]==ch)return1;if(x==6)if(f[0][0]==ch&&f[1][1]==ch&&f[2][2]==ch)return1;if(x==7)if(f[0][2]==ch&&f[1][1]==ch&&f[2][0]==ch)return1;return0;}//判断f[i][j]为最上方的连续三个格子是否都为chintchess::check(charf[MAX][MAX]){intk;for(k=0;k8;k++)if(che(f,k,'x')==1)returnmaxwin;elseif(che(f,k,'o')==1)returnminwin;return0;}intchess::fun(charf[MAX][MAX])//计算评估值{inti,j,k,maxf,minf;for(k=0;k8;k++)if(che(f,k,'x')==1)returnmaxwin;elseif(che(f,k,'o')==1)returnminwin;//返回P必胜或必败时的值intresult=0;for(i=0;i3;i++){if(f[i][0]!='c'&&f[i][1]!='c'&&f[i][2]!='c'&&(f[i][0]=='x'||f[i][1]=='x'||f[i][2]=='x'))return100;if(f[0][i]!='c'&&f[1][i]!='c'&&f[2][i]!='c'&&(f[0][i]=='x'||f[1][i]=='x'||f[2][i]=='x'))return100;}if(f[0][0]!='c'&&f[1][1]!='c'&&f[2][2]!='c'&&(f[0][0]=='x'||f[1][1]=='x'||f[2][2]=='x'))return100;if(f[0][2]!='c'&&f[1][1]!='c'&&f[2][0]!='c'&&(f[0][2]=='x'||f[1][1]=='x'||f[2][0]=='x'))return100;for(i=0;i3;i++){if(f[i][0]!='c'&&f[i][1]!='c'&&f[i][2]!='c'&&(f[i][0]=='o'||f[i][1]=='o'||f[i][2]=='o'))return-100;if(f[0][i]!='c'&&f[1][i]!='c'&&f[2][i]!='c'&&(f[0][i]=='o'||f[1][i]=='o'||f[2][i]=='o'))return-100;}if(f[0][0]!='c'&&f[1][1]!='c'&&f[2][2]!='c'&&(f[0][0]=='o'||f[1][1]=='o'||f[2][2]=='o'))return-100;if(f[0][2]!='c'&&f[1][1]!='c'&&f[2][0]!='c'&&(f[0][2]=='o'||f[1][1]=='o'||f[2][0]=='o'))return-100;//防将军chartemp[MAX][MAX];for(i=0;iMAX;i++)for(j=0;jMAX;j++)temp[i][j]=f[i][j];for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(temp[i][j]!='x'&&temp[i][j]!='o')temp[i][j]='x';maxf=0;for(k=0;k8;k++)if(che(temp,k,'x')==1)maxf++;//无法必胜或必败时，空格全是x时，max有多少种胜法for(i=0;iMAX;i++)for(j=0;jMAX;j++)temp[i][j]=f[i][j];for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(temp[i][j]!='x'&&temp[i][j]!='o')temp[i][j]='o';minf=0;for(k=0;k8;k++)if(che(temp,k,'o')==1)minf++;//无法必胜或必败时，空格全是o时，min有多少种胜法returnmaxf-minf;}voidchess::init(){memset(queue,0,sizeof(queue));memset(sign,0,sizeof(sign));p=0;q=1;inti;for(i=0;i10000;i++)queue[i].son=-1;queue[p].father=-1;//初始点没有父亲queue[p].floor=0;//初始点的层数为0queue[p].value=0;//初始点的值为0（因为刚开始时，局面对谁都是公平的）return;}//初始化，队列置空后，放成c表示空格intchess::equal(chara[MAX][MAX],charb[MAX][MAX]){inti,j,t;t=0;for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(a[i][j]!=b[i][j])t=1;if(t==0)return1;//是否相同t=0;for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(a[i][j]!=b[i][MAX-j-1])t=1;if(t==0)return1;//是否关于y轴方向轴对称t=0;for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(a[i][j]!=b[MAX-i-1][j])t=1;if(t==0)return1;//是否关于x轴方向轴对称t=0;for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(a[i][j]!=b[MAX-j-1][MAX-i-1])t=1;if(t==0)return1;//是否关于y=x方向轴对称t=0;for(i=0;iMAX;i++)for(j=0;jMAX;j++)if(a[i][j]!=b[j][i])t=1;if(t==0)return1;//是否关于y=-x方向轴对称return0;//都不是，才相等；}//判断两个max*max的棋局是否为相同的，是则返回1，否则返回0intchess::maxnum(inta,intb){if(ab)returna;elsereturnb;}intchess::minnum(inta,intb){if(ab)returna;elsereturnb;}intchess::GetAllMoves(nodef,intp,int&bit){ints=0,i,j;for(i=0;iMAX;i++)for(j=0;jMAX;j++){//如果枚举的位置上有棋子了，那么不理它，继续下一个枚举if(f.pf[i][j]=='x'||f.pf[i][j]=='o')continue;nodetemp;temp=f;temp.father=p;temp.floor=f.floor+1;temp.value=fun(temp.pf);//如果层数为奇数的话，那么就是max下棋，标