C语言实现8数码问题

1、实验目的熟悉人工智能系统中的问题求解过程；熟悉状态空间中的盲目搜索策略；（3）掌握盲目搜索算法，重点是宽度优先搜索和深度优先搜索算法。实验要求用VC语言编程，采用宽度优先搜索和深度优先搜索方法，求解8数码问题实验内容（1）采用宽度优先算法，运行程序，要求输入初始状态假设给定如下初始状态so2 8 31 6 47 0 5和目标状态Sg2 1 64 0 87 5 3验证程序的输出结果，写出心得体会。（2）对代码进行修改（选作），实现深度优先搜索求解该问题提示：每次选扩展节点时，从数组的最后一个生成的节点开始找，找一个没有被 扩展的节点。这样也需要对节点添加一个是否被扩展过的标志。4源代码及实验结果

2、截图#include#include#include八数码状态对应的节点结构体struct Node)else if( exit_Node(Closed, Successor-s, 01d_Node)if(Successor-g g)01d_Node-next-previous = BESTNODE;01d_Node-nex t-g = Successor-g：01d_Node-next-f - 01d_Node-g + s);del_Node(Closed, 01d_Node);Add_Node(Closed, 01d_Node)：)else Successor-f = Successor-

3、 + 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), 意为放错的数码与正确的位置距离之和/void A_algorith(struct Node Open, struct Node Closed) A*算法 (int i, j;struct Node BESTNODE, *inital, Successor;initai = (struct Node )malloc

4、(sizeof(struct Node);初始化起始节点for(i=0; i3; i+)for(j=0; jsij = inital_sij;inital-f = wrong_su(inital_s);inital-g = 0;inital-previous = NULL;inital-next = NULL;Add_Nos, final_s) 判断 BESTNODE 是否为目标节点printf(*success!n*);print.Path(BESTNODE);return;针对八数码问题，后继结点Successor的扩展方法：空格（二维数组中的0）上下左右移动,判断每种移动的有效性，有效那

5、么转向A*子算法处理后继节点，否那么进行下一种移动 elseSuccessor = (struct Node * )malloc(sizeof(struct Node); Successor-next = NULL：if(get_successor(BESTNODE, 0, Successor)sub_A_algorithm( Open, BESTNODE, Closed, Successor);Successor = (struct Node )malloc(sizeof(struct Node); Successor-next = NULL;if(get_successor(BESTNOD

6、E, 1, Successor)sub_A_algorithm( Open, BESTNODE, Closed, Successor);Successor = (struct Node )malloc(sizeof(struct Node); Successor-next = NULL：i f(get_successor(BESTNODE, 2, Successor)sub_A_algori thm( Open, BESTNODE, Closed, Successor);Successor = (struct Node * )malloc(sizeof(struct Node); Succes

7、sor-next = NULL：if(get_successor(BESTNODE, 3, Successor)sub_A_algorithm( Open, BESTNODE, Closed, Successor);)/mainO函数入口定义Open和Closed列表.Open列表：保存待检查节点。Closed列表：保存不需要再检查的节点/void main()(struct Node Open = (struct Node )malloc(sizeof(struct Node);struct Node Closed = (struct Node )nalloc(sizeof(struct N

8、ode);0pen-next - NULL ; Open-previous - NULL;Closed-next =NULL; Closed-previous = NULL;A_algorithm(Open, Closed); C:UtefpointDtktopR!-吗的初始状态, 283164705=12, g=0（数码的中间态1283164750-13, gl1甑3的中间态2283160754=14, g=2国好$的中间态3280163754-15. g-3散码的中间态4208163754-14, t=4 * *CAU5erspointDlctopFfl.八数码的中间态6人数科的中间态72

9、 6710 5f-17, g-7 CAUseripointDktopffl.段码的中间态122067181=18, 8=12间态883间态98数码的中间态102 6 87105 4 318.10仪码的中间态112 6 07 1 85 4 3八数科的中间态13ttlL1 60 84 38-13八敷码的中间f=18, g=14八数四的中间态151 64 85 3 g15八数码的中间态162 07 tf=18.5 3 铲16int s33;保存八数码状态，。代表空格int f, 8；启发函数中的f和8值struct Node * next;struct Node *prev

10、ious;/保存其父节点 )；int open_N=0; 记录Open列表中节点数目八数码初始状态int inital_s33=2,8,3,1,6,4,7,0,5)；八数码目标状态int final_s33=2,1,6,4,0,8,7,5,3)；/添加节点函数入口，方法：通过插入排序向指定表添加/void Add_Node( struct Node head, struct Node *p) (struct Node *q：if(head-next)/考虑链表为空 q = head-next;if(p-f f)(考虑插入的节点值比链表的第一个节点值小 p-next = head-next;he

11、ad-next - p;else while(q-next)考虑插入节点x,形如a= x f f |q-f = p-f) & (q-next-f p-f | q-next-f - p-f) p-next - q-next;q-next = p;break;q = q-next;if(q-next = NULL) 考虑插入的节点值比链表最后一个元素的值更大 q-next = p;)else head-next = p;)/删除节点函数入口/void del_Node(struct Node * head, struct Node *p )(struct Node *q;q = head;whil

12、e(q-next)(if(q-next = p) q-next - p-next;p-next = NULL;if(q-next = NULL) return;/ free(p);)q = q-next;/判断两个数组是否相等函数入口/int equal(int si33, int s233) (int i, j,flag=O;for(i=0; i 3 ; i+)for(j=0; j 3 J+)if(slij != s2ij)flag = 1; break;if(!flag)return 1：else return 0; )/判断后继节点是否存在于Open或Closed表中函数入口/int e

13、xit_Node (struct Node * head, int s3 3, struct Node *01d_Nonext;int flag = 0;while(q)if (equal(q-s, s)(flag=l;01d_Node-next - q;return 1;else q = q-next;if(!flag) return 0;)/计算p(n)的函数入口其中p(n)为放错位的数码与其正确的位置之间距离之和具体方法：放错位的数码与其正确的位置对应下标差的绝对值之和int wrong_sum(int s33)(int i, j, fi, fj, sum=0;for(i=0 ： i3;

14、 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;)return sum;)/获取后继结点函数入口 检查空格每种移动的合法性，如果合法那么移动空格得到后继结点/int get_successor(struct Node * BESTNODE, int direction, struct Node Successor)扩展 BESTNODE,产生其后继结点 SUCCESSOR(int i, j, i_0,

15、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 = jjbreak：switch(direction)(case 0: if(i_0-l)-l )temp = Successor-si_0j_0;Successor-si_0j_0 = Successor-si_0-lj_0：Successor-si_0_lj_0 = temp：return 1;else return 0;if(j_O-l)-l)temp = Success

16、or-si_0j_0;Successor-si_0j_0 = Successor-si_0;Successor-si_0j_0l = temp： return 1;else return 0;if( (j_0+l)si_0j_0;Successor-si_0j_0 = Successor-si_0j_O+l；Successor-si_0j_0+l = temp：return 1;)else return 0;if(i_0+l)si_0j_0;Successor-si_0j_0 = Successor-si_0+lj_0;Successor-si_0+lj_0 = teop;return 1;)

17、else return 0;)/从OPen表获取最正确节点函数入口struct Node get_BESTNODE(struct Node *0pen)return Open-next;输出最正确路径函数入口/void print_Path(struct Node head)(struct Node *q, *ql,*p；int i,j,count=l：p = (struct Node )malloc(sizeof(struct Node);通过头插法变更节点输出次序p-previous = NULL;q - head;while(q)(ql = q-previous;q-previous =

18、 p-previous;p-previous = q;q = qi;)q = p-previous:while(q)if(q = p-previous)printf (八数码的初始状态：n);else if (q-previous = NULL)printf (八数码的目标状态：n);else printf(八数码的中间态%dn”, count+)：for(i=0; i3; i+)for(j=0: jf, q-g)：q = q-previous：)/A*子算法入口：处理后继结点void sub_A_algorithm(struct Node Open, struct Node BESINODE, struct Node Closed, struct Node Successor)