宽度优先算法求解八数码问题

1、实验目的(1)熟悉人工智能系统中的问题求解过程；(2)熟悉状态空间中的盲目搜索策略；(3)掌握盲目搜索算法，重点是宽度优先搜索和深度优先搜索算法。

2、实验要求用VC语言编程，采用宽度优先搜索和深度优先搜索方法，求解8数码问题3、实验内容（1）采用宽度优先算法，运行程序，要求输入初始状态假设给定如下初始状态S02 8 31 6 47 0 5和目标状态Sg2 1 64 0 87 5 3验证程序的输出结果，写出心得体会。

（2）对代码进行修改（选作），实现深度优先搜索求解该问题提示：每次选扩展节点时，从数组的最后一个生成的节点开始找，找一个没有被扩展的节点。

这样也需要对节点添加一个是否被扩展过的标志。

4 源代码及实验结果截图#include<stdio.h>#include<stdlib.h>#include<math.h>//八数码状态对应的节点结构体struct Node{int s[3][3];//保存八数码状态，0代表空格int f,g;//启发函数中的f和g值struct Node * next;struct Node *previous;//保存其父节点};int open_N=0; //记录Open列表中节点数目//八数码初始状态int inital_s[3][3]={2,8,3,1,6,4,7,0,5};//八数码目标状态int final_s[3][3]={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 < head->next->f){//考虑插入的节点值比链表的第一个节点值小p->next = head->next;head->next = p;}else {while(q->next)//考虑插入节点x，形如a<= x <=b{if((q->f < p->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;while(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 s1[3][3], int s2[3][3])int i,j,flag=0;for(i=0; i< 3 ; i++)for(j=0; j< 3 ;j++)if(s1[i][j] != s2[i][j]){flag = 1; break;}if(!flag)return 1;else return 0;}//------------------------------------------------------------------------//判断后继节点是否存在于Open或Closed表中函数入口//------------------------------------------------------------------------int exit_Node(struct Node * head,int s[3][3], struct Node *Old_Node) {struct Node *q=head->next;int flag = 0;while(q)if(equal(q->s,s)) {flag=1;Old_Node->next = q;return 1;}else q = q->next;if(!flag) return 0;}//------------------------------------------------------------------------//计算p(n)的函数入口//其中p(n)为放错位的数码与其正确的位置之间距离之和//具体方法：放错位的数码与其正确的位置对应下标差的绝对值之和//------------------------------------------------------------------------int wrong_sum(int s[3][3]){int i,j,fi,fj,sum=0;for(i=0 ; i<3; i++)for(j=0; j<3; j++){for(fi=0; fi<3; fi++)for(fj=0; fj<3; fj++)if((final_s[fi][fj] == s[i][j])){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,j_0,temp;for(i=0; i<3; i++)for(j=0; j<3; j++)Successor->s[i][j] = BESTNODE->s[i][j];//获取空格所在位置for(i=0; i<3; i++)for(j=0; j<3; j++)if(BESTNODE->s[i][j] == 0){i_0 = i; j_0 = j;break;} switch(direction){case 0: if((i_0-1)>-1 ){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0-1][j_0];Successor->s[i_0-1][j_0] = temp;return 1;}else return 0;case 1: if((j_0-1)>-1){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0][j_0-1];Successor->s[i_0][j_0-1] = temp;return 1;}else return 0;case 2: if( (j_0+1)<3){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0][j_0+1];Successor->s[i_0][j_0+1] = temp;return 1;}else return 0;case 3: if((i_0+1)<3 ){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0+1][j_0];Successor->s[i_0+1][j_0] = temp;return 1;}else return 0;}}//------------------------------------------------------------------------//从OPen表获取最佳节点函数入口//------------------------------------------------------------------------struct Node * get_BESTNODE(struct Node *Open){return Open->next;}//------------------------------------------------------------------------//输出最佳路径函数入口//------------------------------------------------------------------------void print_Path(struct Node * head){struct Node *q, *q1,*p;int i,j,count=1;p = (struct Node *)malloc(sizeof(struct Node));//通过头插法变更节点输出次序p->previous = 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");else if(q->previous == NULL)printf("八数码的目标状态：\n");else printf("八数码的中间态%d\n",count++);for(i=0; i<3; i++)for(j=0; j<3; j++){printf("%4d",q->s[i][j]);if(j == 2)printf("\n");}printf("f=%d, g=%d\n\n",q->f,q->g);q = q->previous;}}//------------------------------------------------------------------------//A*子算法入口:处理后继结点//------------------------------------------------------------------------void sub_A_algorithm(struct Node * Open, struct Node * BESTNODE, struct Node * Closed,struct Node *Successor){struct Node * Old_Node = (struct Node *)malloc(sizeof(struct Node));Successor->previous = BESTNODE;//建立从successor返回BESTNODE的指针Successor->g = BESTNODE->g + 1;//计算后继结点的g值//检查后继结点是否已存在于Open和Closed表中，如果存在：该节点记为old_Node，比较后继结点的g值和表中old_Node节点//g值，前者小代表新的路径比老路径更好，将Old_Node的父节点改为BESTNODE，并修改其f，g值，后者小则什么也不做。

1、实验目的(1)熟悉人工智能系统中的问题求解过程；(2)熟悉状态空间中的盲目搜索策略；(3)掌握盲目搜索算法，重点是宽度优先搜索和深度优先搜索算法。

2、实验要求用VC语言编程，采用宽度优先搜索和深度优先搜索方法，求解8数码问题3、实验内容（1）采用宽度优先算法，运行程序，要求输入初始状态假设给定如下初始状态S02 8 31 6 47 0 5和目标状态Sg2 1 64 0 87 5 3验证程序的输出结果，写出心得体会。

（2）对代码进行修改（选作），实现深度优先搜索求解该问题提示：每次选扩展节点时，从数组的最后一个生成的节点开始找，找一个没有被扩展的节点。

这样也需要对节点添加一个是否被扩展过的标志。

4 源代码及实验结果截图#include<stdio.h>#include<stdlib.h>#include<math.h>//八数码状态对应的节点结构体struct Node{int s[3][3];//保存八数码状态，0代表空格int f,g;//启发函数中的f和g值struct Node * next;struct Node *previous;//保存其父节点};int open_N=0; //记录Open列表中节点数目//八数码初始状态int inital_s[3][3]={2,8,3,1,6,4,7,0,5};//八数码目标状态int final_s[3][3]={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 < head->next->f){//考虑插入的节点值比链表的第一个节点值小p->next = head->next;head->next = p;}else {while(q->next)//考虑插入节点x，形如a<= x <=b{if((q->f < p->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;while(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 s1[3][3], int s2[3][3]){int i,j,flag=0;for(i=0; i< 3 ; i++)for(j=0; j< 3 ;j++)if(s1[i][j] != s2[i][j]){flag = 1; break;}if(!flag)return 1;else return 0;}//------------------------------------------------------------------------ //判断后继节点是否存在于Open或Closed表中函数入口//------------------------------------------------------------------------ int exit_Node(struct Node * head,int s[3][3], struct Node *Old_Node){struct Node *q=head->next;int flag = 0;while(q)if(equal(q->s,s)) {flag=1;Old_Node->next = q;return 1;}else q = q->next;if(!flag) return 0;}//------------------------------------------------------------------------ //计算p(n)的函数入口//其中p(n)为放错位的数码与其正确的位置之间距离之和//具体方法：放错位的数码与其正确的位置对应下标差的绝对值之和//------------------------------------------------------------------------ int wrong_sum(int s[3][3]){int i,j,fi,fj,sum=0;for(i=0 ; i<3; i++)for(j=0; j<3; j++){for(fi=0; fi<3; fi++)for(fj=0; fj<3; fj++)if((final_s[fi][fj] == s[i][j])){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,j_0,temp;for(i=0; i<3; i++)for(j=0; j<3; j++)Successor->s[i][j] = BESTNODE->s[i][j];//获取空格所在位置for(i=0; i<3; i++)for(j=0; j<3; j++)if(BESTNODE->s[i][j] == 0){i_0 = i; j_0 = j;break;}switch(direction){case 0: if((i_0-1)>-1 ){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0-1][j_0];Successor->s[i_0-1][j_0] = temp;return 1;}else return 0;case 1: if((j_0-1)>-1){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0][j_0-1];Successor->s[i_0][j_0-1] = temp;return 1;}else return 0;case 2: if( (j_0+1)<3){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0][j_0+1];Successor->s[i_0][j_0+1] = temp;return 1;}else return 0;case 3: if((i_0+1)<3 ){temp = Successor->s[i_0][j_0];Successor->s[i_0][j_0] = Successor->s[i_0+1][j_0];Successor->s[i_0+1][j_0] = temp;return 1;}else return 0;}}//------------------------------------------------------------------------ //从OPen表获取最佳节点函数入口//------------------------------------------------------------------------ struct Node * get_BESTNODE(struct Node *Open){return Open->next;}//------------------------------------------------------------------------ //输出最佳路径函数入口//------------------------------------------------------------------------ void print_Path(struct Node * head){struct Node *q, *q1,*p;int i,j,count=1;p = (struct Node *)malloc(sizeof(struct Node));//通过头插法变更节点输出次序p->previous = 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");else if(q->previous == NULL)printf("八数码的目标状态：\n");else printf("八数码的中间态%d\n",count++);for(i=0; i<3; i++)for(j=0; j<3; j++){printf("%4d",q->s[i][j]);if(j == 2)printf("\n");}printf("f=%d, g=%d\n\n",q->f,q->g);q = q->previous;}}//------------------------------------------------------------------------//A*子算法入口:处理后继结点//------------------------------------------------------------------------void sub_A_algorithm(struct Node * Open, struct Node * BESTNODE, struct Node * Closed,struct Node *Successor) {struct Node * Old_Node = (struct Node *)malloc(sizeof(struct Node));Successor->previous = BESTNODE;//建立从successor返回BESTNODE的指针Successor->g = BESTNODE->g + 1;//计算后继结点的g值//检查后继结点是否已存在于Open和Closed表中，如果存在：该节点记为old_Node，比较后继结点的g值和表中old_Node 节点//g值，前者小代表新的路径比老路径更好，将Old_Node的父节点改为BESTNODE，并修改其f，g值，后者小则什么也不做。

“八”数码问题的宽度优先搜索与深度优先搜索我在观看视频和查看大学课本及网上搜索等资料才对“八”数码问题有了更进一步的了解和认识。

一、“八”数码问题的宽度优先搜索步骤如下：1、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步；2、由初始节点向第1层扩展，得到3个节点：2、3、4；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若2、3、4节点均不是目标节点则转到第3步；3、从第1层的第1个节点向第2层扩展，得到节点5；从第1层的第2个节点向第2层扩展，得到3个节点：6、7、8；从第1层的第3个节点向第2层扩展得到节点9；得到一个节点即判断该节点是否为目标节点，若是则搜索过程结束；若6、7、8、9节点均不是目标节点则转到第4步；4、按照上述方法对下一层的节点进行扩展，搜索目标节点；直至搜索到目标节点为止。

二、“八”数码问题的深度优先搜索步骤如下：1、设置深度界限，假设为5；2、判断初始节点是否为目标节点，若初始节点是目标节点则搜索过程结束；若不是则转到第2步；3、由初始节点向第1层扩展，得到节点2，判断节点2是否为目标节点；若是则搜索过程结束；若不是，则将节点2向第2层扩展，得到节点3；4、判断节点3是否为目标节点，若是则搜索过程结束；若不是则将节点3向第3层扩展，得到节点4；5、判断节点4是否为目标节点，若是则搜索过程结束；若不是则将节点4向第4层扩展，得到节点5；6、判断节点5是否为目标节点，若是则搜索过程结束；若不是则结束此轮搜索，返回到第2层，将节点3向第3层扩展得到节点6；7、判断节点6是否为目标节点，若是则搜索过程结束；若不是则将节点6向第4层扩展，得到节点7；8、判断节点7是否为目标节点，若是则结束搜索过程；若不是则将节点6向第4层扩展得到节点8；9、依次类推，知道得到目标节点为止。

三、上述两种搜索策略的比较在宽度优先搜索过程中，扩展到第26个节点时找到了目标节点；而在深度优先搜索过程中，扩展到第18个节点时得到了目标节点。

Y.八数码问题具体思路：宽度优先算法实现过程（1）把起始节点放到OPEN表中；（2）如果OPEN是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；（4）扩展节点n。

如果没有后继节点，则转向（2）（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2）。

深度优先实现过程（1）把起始节点S放入未扩展节点OPEN表中。

如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出；（3）把第一个节点从OPEN表移到CLOSED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。

如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。

方法一：用C语言实现#include <stdio.h>#include <string.h>#include<stdlib.h>typedef long UINT64;typedef struct{char x; //位置x和位置y上的数字换位char y; //其中x是0所在的位置} EP_MOVE;#define SIZE 3 //8数码问题，理论上本程序也可解决15数码问题，#define NUM SIZE * SIZE //但move_gen需要做很多修改，输入初始和结束状态的部分和check_input也要修改#define MAX_NODE 1000000#define MAX_DEP 100#define XCHG(a, b) { a=a + b; b=a - b; a=a - b; }#define TRANS(a, b)/*{ long iii; (b)=0; for(iii=0; iii < NUM; iii++) (b)=((b) << 4) + a[iii]; }*/ //将数组a转换为一个64位的整数b#define RTRANS(a, b) \{ \long iii; \UINT64 ttt=(a); \for(iii=NUM - 1; iii >= 0; iii--) \{ \b[iii]=ttt & 0xf; \ttt>>=4; \} \} //将一个64位整数a转换为数组b//typedef struct EP_NODE_Tag{ UINT64 v; //保存状态，每个数字占4个二进制位，可解决16数码问题struct EP_NODE_Tag *prev; //父节点struct EP_NODE_Tag *small, *big;} EP_NODE;EP_NODE m_ar[MAX_NODE];EP_NODE *m_root;long m_depth; //搜索深度EP_NODE m_out[MAX_DEP]; //输出路径//long move_gen(EP_NODE *node, EP_MOVE *move){long pz; //0的位置UINT64 t=0xf;for(pz=NUM - 1; pz >= 0; pz--). {if((node->v & t) == 0){ break; //找到0的位置}t<<=4;}switch(pz){case 0:move[0].x=0;move[0].y=1;move[1].x=0;move[1].y=3;return 2;case 1:move[0].x=1;move[0].y=0;move[1].x=1;move[1].y=2;move[2].x=1;move[2].y=4;return 3;case 2:move[0].x=2;. move[0].y=1;move[1].x=2;move[1].y=5;return 2;case 3:move[0].x=3;move[0].y=0;move[1].x=3;move[1].y=6;move[2].x=3;move[2].y=4;return 3;case 4:move[0].x=4;move[0].y=1;move[1].x=4;move[1].y=3;move[2].x=4;move[2].y=5;move[3].x=4;move[3].y=7;return 4;. case 5:move[0].x=5;move[0].y=2;move[1].x=5;move[1].y=4;move[2].x=5;move[2].y=8;return 3;case 6:move[0].x=6;move[0].y=3;move[1].x=6;move[1].y=7;return 2;case 7:move[0].x=7;move[0].y=6;move[1].x=7;move[1].y=4;move[2].x=7;move[2].y=8;return 3;.case 8:move[0].x=8;move[0].y=5;move[1].x=8;move[1].y=7;return 2;}return 0;}long mov(EP_NODE *n1, EP_MOVE *mv, EP_NODE *n2) //走一步，返回走一步后的结果{char ss[NUM];RTRANS(n1->v, ss);XCHG(ss[mv->x], ss[mv->y]);TRANS(ss, n2->v);return 0;}long add_node(EP_NODE *node, long r){EP_NODE *p=m_root;EP_NODE *q;. while(p){ q=p;if(p->v == node->v) return 0;else if(node->v > p->v) p=p->big;else if(node->v < p->v) p=p->small;}m_ar[r].v=node->v;m_ar[r].prev=node->prev;m_ar[r].small=NULL;m_ar[r].big=NULL;if(node->v > q->v){ q->big= &m_ar[r];}else if(node->v < q->v){ q->small= &m_ar[r];}return 1;}/*得到节点所在深度*/long get_node_depth(EP_NODE *node) { long d=0;while(node->prev).{ d++;node=node->prev;}return d;}/*返回值：成功－返回搜索节点数，节点数不够－(-1)，无解－(-2)*/ long bfs_search(char *begin, char *end){ long h=0, r=1, c, i, j;EP_NODE l_end, node, *pnode;EP_MOVE mv[4]; //每个局面最多4种走法TRANS(begin, m_ar[0].v);TRANS(end, l_end.v);m_ar[0].prev=NULL;m_root=m_ar;m_root->small=NULL;m_root->big=NULL;while((h < r) && (r < MAX_NODE - 4)){ c=move_gen(&m_ar[h], mv);for(i=0; i < c; i++){ mov(&m_ar[h], &mv[i], &node);node.prev= &m_ar[h];if(node.v == l_end.v){ pnode= &node;j=0;while(pnode->prev){ m_out[j]=*pnode;j++;pnode=pnode->prev;}m_depth=j;return r;}if(add_node(&node, r)) r++; //只能对历史节点中没有的新节点搜索，否则会出现环}h++;printf("\rSearch...%9d/%d @ %d", h, r, get_node_depth(&m_ar[h]));}if(h == r){ return -2; }else{return -1; }}long check_input(char *s, char a, long r){ long i;for(i=0; i < r; i++){ if(s[i] == a - 0x30) return 0; }return 1;}long check_possible(char *begin, char *end){ char fs;long f1=0, f2=0;long i, j;for(i=0; i < NUM; i++){ fs=0;for(j=0; j < i; j++){if((begin[i] != 0) && (begin[j] != 0) && (begin[j] < begin[i])) fs++; }f1+=fs;fs=0;for(j=0; j < i; j++){ if((end[i] != 0) && (end[j] != 0) && (end[j] < end[i])) fs++;}f2+=fs;}if((f1 & 1) == (f2 & 1)) return 1;. elsereturn 0;}void output(void){ long i, j, k;char ss[NUM];for(i=m_depth - 1; i >= 0; i--){ RTRANS(m_out[i].v, ss);for(j=0; j < SIZE; j++){ for(k=0; k < SIZE; k++){ printf("%2d", ss[SIZE * j + k]);}printf("\n");}printf("\n");}}int main(void){ char s1[NUM];char s2[NUM];long r;char a;printf("请输入开始状态:");r=0;while(r < NUM){ a=getchar();if(a >= 0x30 && a < 0x39 && check_input(s1, a, r)) { s1[r++]=a - 0x30;printf("%c", a);}}printf("\n请输入结束状态:");r=0;while(r < NUM){ a=getchar();if(a >= 0x30 && a < 0x39 && check_input(s2, a, r)) { s2[r++]=a - 0x30;printf("%c", a);}}printf("\n");if(check_possible(s1, s2)){ r=bfs_search(s1, s2);printf("\n");if(r >= 0){ printf("查找深度=%d,所有的方式=%ld\n", m_depth, r);output();}else if(r == -1){ printf("没有找到路径.\n");}else if(r == -2){printf("这种状态变换没有路径到达.\n");}else{printf("不确定的错误.\n");}}else{ printf("不允许这样移动!\n");}return 0;}方法二：用MATLAB实现program 8no_bfs; {八数码的宽度优先搜索算法} ConstDir : array[1..4,1..2]of integer {四种移动方向，对应产生式规则} = ((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no = array[1..3,1..3]of integer;TList = recordFather : integer; {父指针}dep : byte; {深度}X0,Y0 : byte; {0的位置}State : T8no; {棋盘状态}end;VarSource,Target : T8no;List : array[0..10000] of TList; {综合数据库}Closed,open,Best : integer { Best表示最优移动次数} Answer : integer; {记录解}Found : Boolean; {解标志}procedure GetInfo; {读入初始和目标节点}var i,j : integer;beginfor i:=1 to 3 dofor j:=1 to 3 do read(Source[i,j]);for i:=1 to 3 dofor j:=1 to 3 do read(Target[i,j]);end;procedure Initialize; {初始化}var x,y : integer;beginFound:=false;Closed:=0;open:=1;with List[1] do beginState:=Source;dep:=0;Father:=0;For x:=1 to 3 doFor y:=1 to 3 doif State[x,y]=0 then Begin x0:=x;y0:=y; End;end;end;Function Same(A,B : T8no):Boolean; {判断A,B状态是否相等} Var i,j : integer;BeginSame:=false;For i:=1 to 3 do for j:=1 to 3 do if A[i,j]<>B[i,j] then exit; Same:=true;End;Function not_Appear(new : tList):boolean;{判断new是否在List中出现}var i : integer;beginnot_Appear:=false;for i:=1 to open do if Same(new.State,List[i].State) then exit;not_Appear:=true;end;procedure Move(n : tList;d : integer;var ok : boolean;var new : tList);{将第d条规则作用于n得到new,OK是new是否可行的标志}var x,y : integer;beginX := n.x0 + Dir[d,1];Y := n.y0 + Dir[d,2];{判断new的可行性}if not ((X > 0) and ( X < 4 ) and ( Y > 0 ) and ( Y < 4 )) then begin ok:=false;exit end;OK:=true;new.State:=n.State; {new=Expand(n,d)}new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;procedure Add(new : tList); {插入节点new}beginif not_Appear(new) then Begin {如果new没有在List出现} Inc(open); {new加入open表}List[open] := new;end;end;procedure Expand(Index : integer; var n : tList); {扩展n的子节点}var i : integer;new : tList;OK : boolean;Beginif Same(n.State , Target) then begin {如果找到解}Found := true;Best :=n.Dep;Answer:=Index;Exit;end;For i := 1 to 4 do begin {依次使用４条规则} Move(n,i,OK,new);if not ok then continue;new.Father := Index;new.Dep :=n.dep + 1;Add(new);end;end;procedure GetOutInfo; {输出} procedure Outlook(Index : integer); {递归输出每一个解} var i,j : integer;beginif Index=0 then exit;Outlook(List[Index].Father);with List[Index] dofor i:=1 to 3 do beginfor j:=1 to 3 do write(State[i,j],' ');writeln;end;writeln;end;beginWriteln('Total = ',Best);Outlook(Answer);end;procedure Main; {搜索主过程} beginRepeatInc(Closed);Expand(Closed,List[Closed]); {扩展Closed} Until (Closed>=open) or Found;if Found then GetOutInfo {存在解}else Writeln('no answer'); {无解}end;BeginAssign(Input,'input.txt');ReSet(Input);Assign(Output,'Output.txt');ReWrite(Output);GetInfo;Initialize;Main;Close(Input);Close(Output);End.五、实验结果六、实验总结通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。

⼋数码问题摘要：近⽇来，⼈⼯智能成为科技领域搜索热词，⽆论是从⼈机⼤战的新闻来看，还是从新提出的深度学习理论来分析，我们可以可以清晰的预见，⼈⼯智能即将腾飞。

⼈⼯智能，顾名思义，就是模拟⼈类思考模式的超级算法系统，学习能⼒和推理能⼒是其核⼼内容。

举个简单的例⼦，“机器学习（MachineLearning）”就是⼈⼯智能领域⾥很有前途的课题，其主要内容是利⽤⼤数据训练程序，让它们找到⼀些可遵循的规律，并且让程序本⾝⼤胆的预测结果。

在这个过程中搜索策略变的尤为关键。

本⽂主要论述计算机科学与技术专业⼤三下专业课《⼈⼯智能》第⼆个实验算法。

关键字：⼈⼯智能，搜索问题，启发式搜索Eight digital problemAbstract: in recent days, the artificial intelligence search words become areas of science and technology, whether from the point of man-machine war news, or the depth of the new proposed learning theory to the analysis, we can clearly foresee, artificial intelligence is about to take off.Artificial intelligence, as the name implies, is to simulate human thinking mode of super algorithm system, learning ability and reasoning ability is the core content. A simple example, the "machine learning (MachineLearning)" is the field of artificial intelligence is a promising subject, its main content is to use big data training program, let them find some follow rules, and make bold prediction to the program itself. In the process of the search strategy is particularly critical. This paper mainly discusses the computer science and technology under the junior in professional course "artificial intelligence".Keywords: artificial intelligence, search problems, heuristic search1，问题重述3×3九宫棋盘，放置数码为1 -8的8个棋牌，剩下⼀个空格，只能通过棋牌向空格的移动来改变棋盘的布局。

实验报告课程名称人工智能_____________实验项目八数码难题______________实验仪器电脑、visual C++_________系别____________ 专业__ _____班级/学号学生姓名_ _________实验日期____成绩_______________________指导教师_________一、实验目的理解并熟悉掌握深度优先搜索和广度优先搜索地方法。

二、实验内容九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数【算法分析】解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。

当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化。

这个问题也可以推广到流行的拼图游戏。

【具体步骤】一、确定问题规模（考虑搜索的时间代价）二、确定产生式规则（如果规则太多，则时间代价会很大）三、套用经典宽度搜索框架写程序三、代码和结果#include <stdlib.h>#include <stdio.h>typedef struct Node {int num[9]; //棋盘状态int deepth; //派生的深度g(n)int diffnum; //不在位的数目h(n)int value; //耗散值f(n)=g(n)+h(n)struct Node * pre;struct Node * next;struct Node * parent;}numNode; /* ---------- end of struct numNode ---------- */int origin[9]; //棋盘初始状态int target[9]; //棋盘目标状态int numNode_num,total_step;numNode *open,*close; //Open表和Close表numNode *create_numNode(){return (numNode *)malloc(sizeof(numNode));}numNode *open_getfirst(numNode *head); //返回第一项，并从Open表中删除void open_insert(numNode *head,numNode *item); //向Open表中按序插入新节点void close_append(numNode *head,numNode *item); //向Close表中插入新节点int expand(numNode *item); //扩展节点int print_result(numNode *item); //打印结果numNode *copy_numNode(numNode *orgin);char isNewNode(numNode *open,numNode *close,int num[9]);//是否在Open表或Close表中void print_num(int num[9]); //打印棋盘状态int diff(int num[9]); //求不在位棋子的个数void init(); //初始化，获得棋盘初始状态和目标状态void swap(int *a,int *b);int operate(int num[],int op);void free_list(numNode *head);/** === FUNCTION ======================================================================* Name: 主函數* Description: 程序入口*=============================================================================== ======*/intmain ( int argc, char *argv[] ){//初始化Open表和Close表open=create_numNode();close=create_numNode();open->pre=open->next=close->pre=close->next=NULL;init(); //由用户输入初始和目标状态//初始化初始节点numNode *p1;p1=create_numNode();p1->parent=NULL;p1->deepth=0;int i=0;for ( i=0; i<9; i++){p1->num[i]=origin[i];}open_insert(open,p1);numNode_num=1;p1=open_getfirst(open);while (p1!=NULL){close_append(close,p1);if(expand(p1))return EXIT_SUCCESS;p1=open_getfirst(open);}printf("No solution!\n");return EXIT_SUCCESS;} /* ---------- end of function main ---------- */voidinit ( ){while(1){printf("Please input opriginal status:\nFor example:123456780 stands for\n""1 2 3\n""4 5 6\n""7 8 0\n");char temp[10];scanf("%s",&temp);int i=0;for ( i=0;i<9 && temp[i]-'0'>=0 && temp[i]-'0'<=8; i++) {origin[i]=temp[i]-'0';}printf("Please input target status:\n");scanf("%s",&temp);int j=0;for ( j=0; j<9 && temp[j]-'0'>=0 && temp[j]-'0'<=8; j++){target[j]=temp[j]-'0';}system("cls");if ( i==9&&j==9){break;}}} /* ----- end of function init ----- */voidopen_insert (numNode *head,numNode *item){numNode *p,*q;p=head->next;q=head;while ( p!=NULL && item->value > p->value ){q=p;p=p->next;}q->next=item;item->pre=q;item->next=p;if(p!=NULL){p->pre=item;}} /* ----- end of function open_insert ----- */numNode *open_getfirst (numNode *head){numNode *p;if ( head->next == NULL ){return NULL;}p=head->next;head->next=p->next;if ( p->next != NULL ){p->next->pre=head;}p->pre=NULL;p->next=NULL;return p;} /* ----- end of function open_getfirst ----- */voidclose_append (numNode *head,numNode *item) {item->next=head->next;item->pre=head;head->next=item;if ( item->next!=NULL ){item->next->pre=item;}} /* ----- end of function close_append ----- */intexpand (numNode *p1){numNode * p2;int op=1;for ( op=1; op<=4; op++){p2=copy_numNode(p1);operate(p2->num,op);if(isNewNode(open,close,p2->num)=='N'){p2->parent=p1;p2->deepth=p1->deepth+1;p2->diffnum=diff(p2->num);p2->value=p2->deepth+p2->diffnum;if(p2->diffnum==0){total_step=print_result(p2);printf("Total step: %d\n",total_step);free_list(open);free_list(close);return 1;}else{numNode_num++;open_insert(open,p2);}}elsefree(p2);}return 0;} /* ----- end of function expand ----- */intoperate(int m[], int op){int blank;blank=0;while (m[blank]!=0 && blank<9 )++blank;if (blank==9)return 1;switch (op) {case 1: /* up */if (blank>2)swap(m+blank,m+blank-3);break;case 2: /* down */if (blank<6)swap(m+blank,m+blank+3);break;case 3: /* left */if (blank!=0 && blank!=3 && blank!=6)swap(m+blank,m+blank-1);break;case 4: /* right */if (blank!=2 && blank!=5 && blank!=8)swap(m+blank,m+blank+1);break;default : return 1;}return 0;}voidswap(int *a, int *b){int c;c=*a;*a=*b;*b=c;}numNode *copy_numNode (numNode *origin){numNode *p;p=create_numNode();p->deepth=origin->deepth;p->diffnum=origin->diffnum;p->value=origin->value;int i;for ( i=0; i<9; i++){(p->num)[i]=(origin->num)[i];}return p;} /* ----- end of function copy_numNode ----- */intdiff (int num[9]){int i,diffnum=0;for(i=0;i<9;i++)if(num[i]!=target[i])diffnum++;return diffnum;} /* ----- end of function diff ----- */charisNewNode (numNode *open,numNode *close,int num[9]) {numNode *p;int i=0;p=open->next;while ( p!=NULL ){for ( i=0; i<9; i++){if(p->num[i]!=num[i])break;}if(i==9)return 'O'; //Openp=p->next;}p=close->next;while ( p!=NULL ){for ( i=0; i<9; i++){if(p->num[i]!=num[i])break;}if(i==9)return 'C'; //Closep=p->next;}return 'N';} /* ----- end of function isNewNode ----- */voidfree_list (numNode *head){numNode *p,*q;p=head->next;while ( p!=NULL ){q=p->next;free(p);p=q;}free(head);} /* ----- end of function free_list ----- */voidprint_num (int num[9]){int i;for ( i=0; i<9; i++){printf("%d\t",num[i]);if((i%3)==2)printf("\n");}} /* ----- end of function print_num ----- */intprint_result ( numNode *item){numNode *p;int step;p=item;if(p!=NULL){step=print_result(p->parent);printf("\nStep %d:\n",step+1);print_num(p->num);return step+1;}else{return -1;}}四．实验心得这次试验让我更加深入了解了什么是人工智能，让我了解了人工智能的作用以及含义和人工智能的使用范围以及对于我们未来生活得作用的广大。