****大学人工智能基础课程实验报告（2011-2012学年第一学期）启发式搜索王浩算法班级： *********** 学号： ********** 姓名： ****** 指导教师： ******成绩：2012年 1 月 10 日实验一 启发式搜索算法1. 实验内容：使用启发式搜索算法求解8数码问题。

⑴ 编制程序实现求解8数码问题A *算法，采用估价函数()()()()w n f n d n p n ⎧⎪=+⎨⎪⎩， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。

⑵ 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是()p n 的上界的()h n 的定义，并测试使用该估价函数是否使算法失去可采纳性。

2. 实验目的熟练掌握启发式搜索A *算法及其可采纳性。

3. 实验原理使用启发式信息知道搜索过程，可以在较大的程度上提高搜索算法的时间效率和空间效率；启发式搜索的效率在于启发式函数的优劣，在启发式函数构造不好的情况下，甚至在存在解的情形下也可能导致解丢失的现象或者找不到最优解，所以构造一个优秀的启发式函数是前提条件。

4.实验内容 1.问题描述在一个3*3的九宫格 里有1至8 八个数以及一个空格随机摆放在格子中，如下图：初始状态 目标状态现需将图一转化为图二的目标状态，调整的规则为：每次只能将空格与其相邻的一个数字进行交换。

实质是要求给出一个合法的移动步骤，实现从初始状态到目标状态的转变。

2.算法分析 (1)解存在性的讨论对于任意的一个初始状态，是否有解可通过线性代数的有关理论证明。

按数组存储后，算出初始状态的逆序数和目标状态的逆序数，若两者的奇偶性一致，则表明有解。

（2）估价函数的确定通过对八数码的特性的研究，找出一个相对好的函数，f(n)=d(n)+h(n)其中h(n)=2*compare(n)+3*S(n);d(n)为已搜索的深度；（compare（n）为当前节点与目标结点相同位置不相同的个数，S(n)为当前节点的无序度。

）（3）节点的处理取得一个结点后，判断是否有解，然后对其进行扩展，用估价函数从中取得一个最优节点，依次循环将路径得到，直到取的最后的目标状态。

(4)算法设计a.输入初始结点，判断解的存在性，并与目标节点对比。

b.若不是目标节点则进行扩展，生成其全部后继节点。

c.对于每个后继节点均求其f(n),并比较。

d.将最小f(n)存入正确路径，并与目标节点进行对比。

e.若不是目标节点则循环执行b，若是目标节点则输出5实验结果输入输出：源代码如下：#include<stdio.h>int final[9]={1,2,3,8,0,4,7,6,5};//目标状态节点int a[1000][9],c[9],e[9],f[9];//路径节点和扩展节点int deep=1,fn;//深度和估计值int b[9];char moveaction;//移动方向int fnjisuan(int b[9])//估价函数{int compare=0,s=0,fn1,d[9];d[0]=b[0];d[1]=b[1];d[2]=b[2];d[3]=b[5];d[4]=b[8];d[5]=b[7];d[6]=b[6];d[7]=b[3];d[ 8]=b[4];for(int i=0;i<9;i++){if(b[i]!=final[i]&&i!=4)compare++;}for(i=0;i<7;i++)if((d[i+1]-d[i])!=1)s++;fn1=2*compare+3*s+deep;//估价函数计算结果return fn1;}void show(int c[9])//输出节点{for(int i=0;i<9;i++)a[deep][i]=c[i];for(i=0;i<9;i++){if((i)%3==0)printf("\n");printf("%d\t",c[i]);}deep++;printf("\n");}int jingguo(int e[9])//测试当前节点是否已经经过避免回溯{for(int i=0;i<deep;i++){int k=0;for(int j=0;j<9;j++)if(e[j]==a[i][j])k++;if(k==9)return 0;}return 1;}int move_up(int c[9],int Zerosign)//上移操作{for(int i=0;i<9;i++)c[i]=b[i];c[Zerosign]=c[Zerosign-3];c[Zerosign-3]=0;int fn1=fnjisuan(c);return fn1;}int move_down(int c[9],int Zerosign)//下移操作{for(int i=0;i<9;i++)c[i]=b[i];c[Zerosign]=c[Zerosign+3];c[Zerosign+3]=0;int fn1=fnjisuan(c);return fn1;}int move_left(int c[9],int Zerosign)//左移操作{for(int i=0;i<9;i++)c[i]=b[i];c[Zerosign]=c[Zerosign-1];c[Zerosign-1]=0;int fn1=fnjisuan(c);return fn1;}int move_right(int c[9],int Zerosign)//右移操作{for(int i=0;i<9;i++)c[i]=b[i];c[Zerosign]=c[Zerosign+1];c[Zerosign+1]=0;int fn1=fnjisuan(c);return fn1;}int zuixiao(int fn1,int fn2,int fn3,int fn4)//求最小值{int f1,f2,f3;f1=(fn1<=fn2)?fn1:fn2;f2=(fn3<=fn4)?fn3:fn4;f3=(f1<=f2)?f1:f2;return f3;}int cixiao(int fn1,int fn2,int fn3,int fn4)//求次小值{int f1,f2,f3,f4;f1=(fn1<=fn2)?fn1:fn2;f3=(fn1>fn2)?fn1:fn2;f2=(fn3<=fn4)?fn3:fn4;f4=(fn1>fn2)?fn1:fn2;if(f1<=f2){if(f3<=f2)return f3;else return f2;}else if(f4<=f1)return f4;else return f1;}void budeng(int f1,int f2,int fn1,int fn2,int fn3,int fn4,int Zerosign)//处理估价函数最小值唯一的时候{if(f1==fn1){if(moveaction!='d'&&jingguo(c)){move_up(c,Zerosign);moveaction='u';}else{if(f2==fn2){move_right(c,Zerosign);moveaction='r';}if(f2==fn3){move_left(c,Zerosign);moveaction='l';}if(f2==fn4){move_down(c,Zerosign);moveaction='d';}}}if(f1==fn2){if(moveaction!='l'&&jingguo(c)){move_right(c,Zerosign);moveaction='r';}else{if(f2==fn3){move_left(c,Zerosign);moveaction='l';}if(f2==fn4){move_down(c,Zerosign);moveaction='d';}if(f2==fn1){move_up(c,Zerosign);moveaction='u';}}}if(f1==fn3){if(moveaction!='r'&&jingguo(c)){move_left(c,Zerosign);moveaction='l';}else{if(f2==fn1){move_up(c,Zerosign);moveaction='u';}if(f2==fn2){move_right(c,Zerosign);moveaction='r';}if(f2==fn4){move_down(c,Zerosign);moveaction='d';}}}if(f1==fn4){if(moveaction!='u'&&jingguo(c)){move_down(c,Zerosign);moveaction='d';}else{if(f2==fn2){move_right(c,Zerosign);moveaction='r';}if(f2==fn3){move_left(c,Zerosign);moveaction='l';}if(f2==fn1){move_up(c,Zerosign);moveaction='u';}}}}int ceshi(int k[9])//测试估价函数{int fn1=100,fn2=100,fn3=100,fn4=100,f1,Zerosign;for(int i=0;i<9;i++)if(0==k[i]){Zerosign=i;break;}if(Zerosign!=0&&Zerosign!=1&&Zerosign!=2&&moveaction!='d')fn1=move_up(c,Zerosign);if(Zerosign!=2&&Zerosign!=5&&Zerosign!=8&&moveaction!='l')fn2=move_right(c,Zerosign);if(Zerosign!=0&&Zerosign!=3&&Zerosign!=6&&moveaction!='r')fn3=move_left(c,Zerosign);if(Zerosign!=6&&Zerosign!=7&&Zerosign!=8&&moveaction!='u')fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);return f1;}void move(int c[9])//确定移动方向{int fn1=100,fn2=100,fn3=100,fn4=100,f1,f2,Zerosign;for(int i=0;i<9;i++)if(0==c[i]){Zerosign=i;break;}if(Zerosign!=0&&Zerosign!=1&&Zerosign!=2&&moveaction!='d')fn1=move_up(c,Zerosign);if(Zerosign!=2&&Zerosign!=5&&Zerosign!=8&&moveaction!='l')fn2=move_right(c,Zerosign);if(Zerosign!=0&&Zerosign!=3&&Zerosign!=6&&moveaction!='r')fn3=move_left(c,Zerosign);if(Zerosign!=6&&Zerosign!=7&&Zerosign!=8&&moveaction!='u')fn4=move_down(c,Zerosign);f1=zuixiao(fn1,fn2,fn3,fn4);f2=cixiao(fn1,fn2,fn3,fn4);if(f1==f2){if(fn1==fn2&&fn1==f1){move_up(c,Zerosign);for(i=0;i<9;i++)e[i]=c[i];move_right(c,Zerosign);for(i=0;i<9;i++)f[i]=c[i];if((ceshi(e)<ceshi(f))&&jingguo(e)){move_up(c,Zerosign);moveaction='u';}else {move_right(c,Zerosign);moveaction='r';}}if(fn1==fn3&&fn1==f1){move_up(c,Zerosign);for(i=0;i<9;i++)e[i]=c[i];move_left(c,Zerosign);for(i=0;i<9;i++)f[i]=c[i];if((ceshi(e)<ceshi(f))&&jingguo(e)){move_up(c,Zerosign);moveaction='u';} else {move_left(c,Zerosign);moveaction='l';}}if(fn1==fn4&&fn1==f1){move_up(c,Zerosign);for(i=0;i<9;i++)e[i]=c[i];move_down(c,Zerosign);for(i=0;i<9;i++)f[i]=c[i];if((ceshi(e)<ceshi(f))&&jingguo(e)){move_up(c,Zerosign);moveaction='u';}else {move_down(c,Zerosign);moveaction='d';}}if(fn2==fn3&&fn2==f1){move_right(c,Zerosign);for(i=0;i<9;i++)e[i]=c[i];move_left(c,Zerosign);for(i=0;i<9;i++)f[i]=c[i];if((ceshi(e)<ceshi(f))&&jingguo(e)){move_right(c,Zerosign);moveaction='r';}else {move_left(c,Zerosign);moveaction='l';}}if(fn2==fn4&&fn2==f1){move_right(c,Zerosign);for(i=0;i<9;i++)e[i]=c[i];move_down(c,Zerosign);for(i=0;i<9;i++)f[i]=c[i];if((ceshi(e)<ceshi(f))&&jingguo(e)){move_right(c,Zerosign);moveaction='r';}else {move_down(c,Zerosign);moveaction='d';}}if(fn3==fn4&&fn3==f1){move_left(c,Zerosign);for(i=0;i<9;i++)e[i]=c[i];move_down(c,Zerosign);for(i=0;i<9;i++)f[i]=c[i];if((ceshi(e)<ceshi(f))&&jingguo(e)){move_left(c,Zerosign);moveaction='l';}else {move_down(c,Zerosign);moveaction='d';}}}else budeng(f1,f2,fn1,fn2,fn3,fn4,Zerosign);}int duibi(int c[9]) {//与目标节点比较for(int i=0;i<9;i++)if(c[i]!=final[i])break;if(i>=9)return 1;else return 0;}int cunzaixing(int c[9]) {//得出初始化节点是否存在路径到目标节点int nixu=0,nixu1=0,i,j;for( j=0;j<9;j++)for(int i=j+1;i<9;i++)if(final[j]>final[i]&&final[j]!=0&&final[i]!=0)nixu++;for(j=0;j<9;j++)for( i=j+1;i<9;i++)if(c[j]>c[i]&&c[j]!=0&&c[i]!=0)nixu1++;if((nixu%2)-(nixu1%2)==0)return 1;else return 0;}void main(){//主函数int sd=1;printf("请输入初始结点如（2 8 3 1 6 4 7 0 5）以空格隔开的九个0到9之间的不重复数: \n");for(int i=0;i<9;i++){scanf("%d",&b[i]);c[i]=b[i];}printf("您输入的初始矩阵为：\n");show(c);deep--;if(cunzaixing(c)==0)printf("此矩阵不存在路径至目标矩阵！\n");else{while(!duibi(c)&&deep<100){move(c);printf("第%d步移动后的矩阵为：\n",sd++);show(c);for(int i=0;i<9;i++) b[i]=c[i];}}}实验二王浩算法的实现1. 实验内容：实现命题逻辑框架内的王浩算法。