人工智能大作业[资料教育]

人工智能基础大作业-八数码难题 学院:数学与计算机科学学院 班级:计科14-1 姓名:王佳乐 学号:1060314014032 2016.12.20 一、 实验名称八数码难题的启发式搜索二、 实验目的八数码问题：在33的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。要求：1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。三、 实验设备及软件环境1. 实验编程工具：VC+ 6.02. 实验环境：Windows7 64位四、 实验方法：启发式搜索1.算法描述1. 将S放入open表，计算估价函数f(s)2. 判断open表是否为空，若为空则搜索失败，否则，将open表中的第一个元素加入close表并对其进行扩展（每次扩展后加入open表中的元素按照代价的大小从小到大排序，找到代价最小的节点进行扩展）注：代价的计算公式f(n)=d(n)+w(n).其中f(n)为总代价，d(n)为节点的度，w(n)用来计算节点中错放棋子的个数。判断i是否为目标节点，是则成功，否则拓展i，计算后续节点f(j)，利用f(j)对open表重新排序2.算法流程图：3.程序源代码：# include# include# include# includetypedef struct node int i,cost,degree,exp,father;int a33;struct node *bef,*late;struct node *son;treenode;int flag=0,count=1,num=0,i=0;void set(treenode *s);void cpynode(treenode *s1,treenode *s2);void add1(treenode *s,treenode *open);void adjust1(treenode *close);void jscost(treenode *s);void tiaozheng(treenode *open);void sortopen(treenode *open);int test(treenode *s1,treenode *s2);void position(treenode *s,treenode *open,treenode *close,treenode *s1);void printstr(treenode *open);int search(treenode *s1,treenode *s2);void input(treenode *s);int cmpnode(treenode *s1,treenode *s2);void print(treenode *s);void add(treenode *s,treenode *close);void xuhao(treenode *s);void extend(treenode *r1,treenode *s,treenode *s1,treenode *open,treenode *close);void main() treenode *s0,*s1,*s;treenode *open,*close,*opend,*closed;open=(treenode*)malloc(sizeof(treenode);close=(treenode*)malloc(sizeof(treenode); open-late=NULL;close-late=NULL;opend=open;closed=close;s0=(treenode*)malloc(sizeof(treenode);set (s0);s1=(treenode*)malloc(sizeof(treenode);set(s1);printf(请输入八数码的初始状态：（以空格为分隔）n);input (s0);printf(请输入八数码的目标状态 ：（以空格为分隔）n);input(s1);xuhao(s0);add (s0,opend);while(open-late!=NULL & flag=0)s=(treenode*)malloc(sizeof(treenode); cpynode(s,open-late);open=open-late;add(s,close);if(test(s,s1)=0)flag=1;elseposition(s,open,close,s1);sortopen(open);if(open-late!=NULL) printf(搜索过程如下：n ); adjust1(close);printstr(close);printf(n%d 步,%d 个节点n,num,count);else printf(查找错误 ! n); void set(treenode *s) s-i=i;s-father=0;s-degree=0;s-bef=NULL;s-son=NULL;s-late=NULL; ;void input(treenode *s) int j,k;for(j=0;j3;j+)for(k=0;kajk); ;int cmpnode(treenode *s1,treenode *s2)int j,k;for(j=0;j3;j+)for(k=0;kajk!=s2-ajk)return 0; ;return 1; int test(treenode *s1,treenode *s2) int j,k,n=0;for(j=0;j3;j+)for(k=0;kajk!=s2-ajk)n+; ;s1-exp=n;return n; ;void xuhao(treenode *s) i+;s-i=i; void cpynode(treenode *s1,treenode *s2) int j,k;for(j=0;j3;j+)for(k=0;kajk=s2-ajk;s1-bef=s2-bef;s1-cost=s2-cost;s1-exp=s2-exp;s1-degree=s2-degree;s1-i=s2-i;s1-father=s2-father; ;void print(treenode *s) int j,k;for(j=0;j3;j+) for(k=0;kajk); if(j=1) printf( n=%2d d=%2d f=%2d,s-i,s-degree,s-father);printf(n); printf(n); void position(treenode *s,treenode *open,treenode *close,treenode *s1) int m,n,t,k;treenode *r1;for(m=0;m3;m+) for(n=0;namn;if(k=0)break; ;if(k=0) break; if(m+1am+1n; r1-am+1n = r1-amn; r1-amn=t;extend(r1,s,s1,open,close); ;if(m-1=0&flag=0)r1=(treenode*)malloc(sizeof(treenode); cpynode(r1,s);t=r1-am-1n; r1-am-1n=r1-amn; r1-amn=t;extend(r1,s,s1,open,close);if(n-1=0 & flag=0) r1=(treenode*)malloc(sizeof(treenode); cpynode(r1,s);t=r1-amn-1; r1-amn-1=r1-amn; r1-amn=t;extend(r1,s,s1,open,close); ;if(n+1amn+1; r1-amn+1=r1-amn; r1-amn=t;extend(r1,s,s1,open,close); void printstr(treenode *s) treenode *t;t=s-late;while(t!=NULL) num+;print(t);t=t-son; ; void extend(treenode *r1,treenode *s,treenode *s1,treenode *open,treenode *close) r1-father=s-i;r1-degree=s-degree+1;if(test(r1,s1)!=0) jscost(r1);if(search(r1,close)=1 & search(r1,open)=1) xuhao(r1);add1(r1,open);r1-bef=s;count+; else free(r1); else xuhao(r1);jscost(r1);count+;add(r1,close);r1-bef=s;flag=1; int search(treenode *s1,treenode *close) treenode *r,*t;r=s1;t=close-late;while(t!=NULL) if(r-exp=t-exp) if(cmpnode(r,t)=1)return 0; ;t=t-late; ; return 1; void add(treenode *s,treenode *close) treenode *r,*t;t=s;r=close;while(r-late!=NULL)r=r-late;r-late=t;t-late=NULL; void add1(treenode *s,treenode *open)treenode *t;t=open;s-late=t-late;t-late=s; void adjust1(treenode *close) treenode *s,*t;s=close;s-late-bef=NULL;while(s-late!=NULL)s=s-late;s-son=NULL;while(s-bef!=NULL)t=s-bef;t-son=s;s=s-bef; ; void jscost(treenode *s) s-cost=(s-exp)+s-degree; void sortopen(treenode *open) treenode *t,*s,*r;int k;r=(treenode*)malloc(sizeof(treenode);t=open-late;while(t!=NULL & t-late!=NULL) s=t-late;k=t-cost;while(s!=NULL) if(k s-cost) k=s-cost;cpynode(r,t);cpynode(t,s);cpynode(s,r); s=s-late; t=t-late; ; 五、 实验结果:1.程序截图2.搜索过程请输入八数码的初始状态：（以空格为分隔）283104765请输入八数码的目标状态：（以空格为分隔）123804765搜索过程如下： 283104n=1d=0f=0765203184n=3d=1f=1765023184n=8d=2f=3765123084n=10d=3f=8765123804n=12d=4f=107655步,12个节点Pressanykeytocontinue 六、 实验分析：在进行搜索的过程中，同时记录了扩展新节点的个数。启发式搜索仅扩展12个新节点。可见,在本实验中启发式搜索更优，效率更高。而在求解最短路径的问题上盲目搜索能更高效一点。在实际的应用中应根据具体情况灵活选择不同的策略，提高程序执行效率启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。七、 结论此次实验用启发式搜索方法求解问题的使用，让我们明白了具体问题具体分析，更明白了算法的重要，好的算法能够极大的提高程序的运行效率。同时，通过此次实践，也对课本知识有了更深刻的认识和体会，真正将课本知识融于实践中是对我们的最大考验。这次试验让我更加深入了解了什么是人工智能，让我了解了人工智能的作用以及含义和人工智能的使用范围以及对于我们未来生活得作用的广大。用机器语言解决实际问题的，提高了动手能力。13作业c类