《C语言实现8数码问题》由会员分享，可在线阅读，更多相关《C语言实现8数码问题（6页珍藏版）》请在金锄头文库上搜索。
1、(1) 1、实验目的熟悉人工智能系统中的问题求解过程；熟悉状态空间中的盲目搜索策略；掌握盲目搜索算法，重点是宽度优先搜索和深度优先搜索算法。2、实验要求8数码问题用VC语言编程，采用宽度优先搜索和深度优先搜索方法，求解3、实验内容(1)采用宽度优先算法，运行程序，要求输入初始状态假设给定如下初始状态S0283164705和目标状态Sg216408753验证程序的输出结果，写出心得体会。找一个没有被(2)对代码进行修改(选作)，实现深度优先搜索求解该问题提示：每次选扩展节点时，从数组的最后一个生成的节点开始找，扩展的节点。这样也需要对节点添加一个是否被扩展过的标志。4源代码及实验结果截图#inc
2、lude#include#include/八数码状态对应的节点结构体structNodeints33;/保存八数码状态，0代表空格intf,g;/启发函数中的f和g值structNode*next;structNode*previous;/保存其父节点;intopen_N=0;/记录Open列表中节点数目/八数码初始状态intinital_s33=2,8,3,1,6,4,7,0,5;/八数码目标状态intfinal_s33=2,1,6,4,0,8,7,5,3;/添加节点函数入口，方法：通过插入排序向指定表添加/voidAdd_Node(structNode*head,structNode*p)
3、structNode*q;if(head-next)/考虑链表为空q=head-next;if(p-fnext-f)/考虑插入的节点值比链表的第一个节点值小p-next=head-next;head-next=p;elsewhile(q-next)/考虑插入节点x，形如a=xff|q-f=p-f)&(q-next-fp-f|q-next-f=p-f)p-next=q-next;q-next=p;break;q=q-next;if(q-next=NULL)/考虑插入的节点值比链表最后一个元素的值更大q-next=p;elsehead-next=p;/删除节点函数入口/voiddel_Node(s
4、tructNode*head,structNode*p)structNode*q;q=head;while(q-next)if(q-next=p)q-next=p-next;p-next=NULL;if(q-next=NULL)return;/free(p);q=q-next;/判断两个数组是否相等函数入口/intequal(ints133,ints233)inti,j,flag=0;for(i=0;i3;i+)for(j=0;jnext;intflag=0;while(q)if(equal(q-s,s)flag=1;Old_Node-next=q;return1;elseq=q-next;i
5、f(!flag)return0;/计算p(n)的函数入口/其中p(n)为放错位的数码与其正确的位置之间距离之和/具体方法：放错位的数码与其正确的位置对应下标差的绝对值之和/intwrong_sum(ints33)inti,j,fi,fj,sum=0;for(i=0;i3;i+)for(j=0;j3;j+)for(fi=0;fi3;fi+)for(fj=0;fj3;fj+)if(final_sfifj=sij)sum+=fabs(i-fi)+fabs(j-fj);break;returnsum;/获取后继结点函数入口/检查空格每种移动的合法性，如果合法则移动空格得到后继结点扩展BESTNODE产
6、生其后继结点/intget_successor(structNode*BESTNODE,intdirection,structNode*Successor)/SUCCESSORinti,j,i_0,j_0,temp;for(i=0;i3;i+)for(j=0;jsij=BESTNODE-sij;/获取空格所在位置for(i=0;i3;i+)for(j=0;jsij=0)i_0=i;j_0=j;break;switch(direction)case0:if(i_0-1)-1)temp=Successor-si_0j_0;Successor-si_0j_0=Successor-si_0-1j_0;
7、Successor-si_0-1j_0=temp;return1;elsereturn0;case1:if(j_0-1)-1)temp=Successor-si_0j_0;Successor-si_0j_0=Successor-si_0j_0-1;Successor-si_0j_0-1=temp;return1;elsereturn0;case2:if(j_0+1)si_0j_0;Successor-si_0j_0=Successor-si_0j_0+1;Successor-si_0j_0+1=temp;return1;elsereturn0;case3:if(i_0+1)si_0j_0;Su
8、ccessor-si_0j_0=Successor-si_0+1j_0;Successor-si_0+1j_0=temp;return1;elsereturn0;/从OPen表获取最佳节点函数入口/-structNode*get_BESTNODE(structNode*Open)returnOpen-next;/输出最佳路径函数入口/voidprint_Path(structNode*head)structNode*q,*q1,*p;inti,j,count=1;p=(structNode*)malloc(sizeof(structNode);/通过头插法变更节点输出次序p-previous=
9、NULL;q=head;while(q)q1=q-previous;q-previous=p-previous;p-previous=q;q=q1;q=p-previous;while(q)if(q=p-previous)printf(八数码的初始状态：n);n);elseif(q-previous=NULL)printf(八数码的目标状态：elseprintf(八数码的中间态%dn,count+);for(i=0;i3;i+)for(j=0;jsij);if(j=2)printf(n);printf(f=%d,g=%dnn,q-f,q-g);q=q-previous;/A*子算法入口:处理后
10、继结点/voidsub_A_algorithm(structNode*Open,structNode*BESTNODE,structNode*Closed,structNode*Successor)structNode*Old_Node=(structNode*)malloc(sizeof(structNode);Successor-previous=BESTNODE;/建立从successor返回BESTNODE指针Successor-g=BESTNODE-g+1;/计算后继结点的g值/检查后继结点是否已存在于Open和Closed表中，如果存在：该节点记为old_Node，比较后继结点的g
11、值和表中old_Node节点g值，前者小代表新的路径比老路径更好，将Old_Node的父节点改为BESTNODE并修改其f，g值，后者小则什么也不做。/即不存在Open也不存在Closed表则将其加入OPen表，并计算其f值if(exit_Node(Open,Successor-s,Old_Node)if(Successor-gg)Old_Node-next-previous=BESTNODE;/将Old_Node的父节点改为BESTNODEOld_Node-next-g=Successor-g;/修改g值Old_Node-next-f=Old_Node-g+wrong_sum(Old_Nod
12、e-s);修改f值/排序del_Node(Open,Old_Node);Add_Node(Open,Old_Node);elseif(exit_Node(Closed,Successor-s,Old_Node)if(Successor-gg)Old_Node-next-previous=BESTNODE;Old_Node-next-g=Successor-g;Old_Node-next-f=Old_Node-g+wrong_sum(Old_Node-s);/排序del_Node(Closed,Old_Node);Add_Node(Closed,Old_Node);elseSuccessor-f
13、=Successor-g+wrong_sum(Successor-s);Add_Node(Open,Successor);open_N+;/A*算法入口/八数码问题的启发函数为：f(n)=d(n)+p(n)/其中A*算法中的g(n)根据具体情况设计为d(n),意为n节点的深度，而h(n)设计为p(n),/意为放错的数码与正确的位置距离之和/voidA_algorithm(structNode*Open,structNode*Closed)/A*算法inti,j;structNode*BESTNODE,*inital,*Successor;inital=(structNode*)malloc(sizeof(structNode);/初始化起始节点for(i=0;i3;i+)for(j=0;jsij=inital_sij;inital-f=wrong_sum(inital_s);inital-g=0;inital-previous=NULL;inital-next=NULL;Add_Node(Open,ini
