启发式搜索算法解决八数码问题(C语言)

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值，后者小则什么也不做。

一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如：图1 八数码问题示意图请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A 算法或A* 算法）编程求解八数码问题（初始状态任选）。

选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。

二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。

三、实验算法A*算法是一种常用的启发式搜索算法。

在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。

A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。

由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) = g(n) + h(n)其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。

在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。

用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。

这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。

（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。

启发式搜索浅谈，解决⼋数码问题博客迁移⾄相信很多⼈都接触过九宫格问题，也就是⼋数码问题。

问题描述如下：在3×3的棋盘，摆有⼋个棋⼦，每个棋⼦上标有1⾄8的某⼀数字，不同棋⼦上标的数字不相同。

棋盘上还有⼀个空格，与空格相邻的棋⼦可以移到空格中。

要求解决的问题是：给出⼀个初始状态和⼀个⽬标状态，找出⼀种从初始转变成⽬标状态的移动棋⼦步数最少的移动步骤。

其实在很早之前我就做过这道题了，当时我⽤的是双向⼴搜，后来⼜⼀知半解的模仿了⼀个启发式搜索（A*）。

昨天在图书馆看书的时候，翻阅了⼀下⼈⼯智能的书籍，⼜发现了这个经典的⼋数码问题。

于是便看了下去，渐渐的明⽩了启发式搜索的真正含义，才知道⾃⼰⼏年前模仿的那个代码是什么意思。

在这篇⽂章⾥，我把昨天的所学东西稍稍的记录⼀下，顺便分享给⼤家，如果有什么错误，欢迎各位指出。

平时，我们所使⽤的搜索算法⼤多数都是⼴搜（BFS）和深搜（DFS），其实他们都是盲⽬搜索，相对来说搜索的状态空间⽐较⼤，效率⽐较低。

⽽启发式搜索则相对的智能⼀些，它能对所有当前待扩展状态进⾏评估，选出⼀个最好的状态、最容易出解的状态进⾏搜索。

这样，我们就可以避免扩展⼤量的⽆效状态，从⽽提⾼搜索效率。

在对状态进⾏评估的时候，我们会使⽤到⼀个这样的等式f(n)=g(n)+h(n)。

那这个等式是什么含义呢？其中g(n)代表到达代价，即从初始状态扩展到状态n的代价值。

h(n)代表状态n的估计出解代价，即从状态n扩展到⽬标状态的代价估计值。

所以，f(n)代表估计整体代价，即⼀个搜索路径上经过状态n且成功出解的估计代价值。

于是，在启发式搜索算法中，我们只要对每⼀个状态，求出其f(n)，每次取f(n)最⼩的状态进⾏扩展即可。

那现在还有⼀个问题，就是如何确定g(n)和h(n)到底是什么函数？否则f(n)也⽆法求出。

其实g(n)相对来说⽐较好确定，因为在到达状态n之后，必定有⼀条从初始状态到n的搜索路径，于是我们可以从这条路径上找出到达代价g(n)，⼀般的我们就取路径长度即可。

八数码实验报告实验名称：八数码实验目的：通过使用搜索算法和启发式算法，解决八数码问题，深入理解搜索算法原理和应用。

实验环境：使用Python语言进行编程实现，操作系统为Windows。

实验过程：1. 定义八数码问题的状态和目标状态，分别以列表的形式表示。

* 初始状态：[2, 8, 3, 1, 6, 4, 7, 0, 5]* 目标状态：[1, 2, 3, 8, 0, 4, 7, 6, 5]2. 实现深度优先搜索算法，运行程序得到结果。

通过深度优先搜索算法，得到了八数码问题的解法。

但是，由于深度优先搜索算法过于盲目，搜索时间过长，而且容易陷入无解状态，因此需要改进算法。

3. 改进算法——广度优先搜索。

在深度优先搜索的基础上，改用广度优先搜索算法，实现代码如下：```def bfs(start, target):queue = [(start, [start])]seen = {tuple(start)}while queue:node, path = queue.pop(0)for move, i in direction.items():new_node = [j for j in node]if i not in range(0, 9):continuenew_node[0], new_node[i] = new_node[i], new_node[0] if tuple(new_node) in seen:continueif new_node == target:return path + [new_node]seen.add(tuple(new_node))queue.append((new_node, path + [new_node]))```4. 改进算法——A*算法。

在广度优先搜索的基础上，使用A*算法进行优化。

进行了以下改进：* 引入估价函数，加快搜索速度；* 遍历过程中对结点进行评估，保留最优的结点。

八个数字问题实验报告. 《八数码问题》实验报告首先，实验的目的:熟悉启发式搜索算法。

二、实验内容:启发式搜索算法用于解决8位数问题。

编制了程序，实现了解决8位数问题的算法。

采用评估功能，其中:是搜索树中节点的深度；在节点数据库中放错位置的件数；这是每个棋子与其在节点数据库中的目标位置之间距离的总和。

三、实验原理:1.问题描述:八位数问题也被称为九宫问题。

在3×3的棋盘上，有八个棋子，每一个棋子都标有一定的1到8的数字，不同棋子上标的数字是不同的。

棋盘上还有一个空格(用数字0表示)，与空格相邻的棋子可以移动到空格中。

要解决的问题是: 给定初始状态和目标状态，找出从初始状态到目标状态移动次数最少的移动步骤。

所谓问题的一种状态是棋盘上棋子的排列。

解决八位数问题实际上是找出一系列从初始状态到目标状态的中间过渡状态。

2.原则描述:启发式搜索(1)原理启发式搜索是评估每个搜索在状态空间中的位置以获得最佳位置，然后从这个位置搜索到目标。

这样，可以省略大量不必要的搜索路径，并且提高了效率。

在启发式搜索中，位置的评估非常重要。

不同的评估会产生不同的效果。

(2)评估函数计算节点的评估函数，可分为两部分:1.成本已经支付(从开始节点到当前节点)；2.要支付的价格(当前节点到目标节点)。

节点n的评估函数被定义为从初始节点通过n到目标节点的路径的最小成本的估计值，即=。

是从初始节点到达当前节点n的实际成本；是从节点n到目标节点的最佳路径的估计开销。

比例越大，它越倾向于先搜索宽度或同等成本。

相反，比例越大，启发式性能越强。

(3)算法描述:(1)将起始节点S放入OPEN表中，计算节点S的值；(2)如果OPEN为空表，则无法退出且没有解决方案；(3)从OPEN表中选择具有最小值的节点。

如果多个节点具有相同的值，当其中一个节点是目标节点时，选择目标节点；否则，任意一个节点被选为节点；(4)从OPEN表中移除节点，并将其放入CLOSED扩展节点表中；(5)如果它是目标节点，它成功退出并获得解决方案；⑥扩展节点以生成其所有后续节点。

八数码问题源程序及注释：#include<stdio.h>#include<conio.h>int n,m;typedef struct Node{char matrix[10];/*存储矩阵*/char operate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/char extend;/*是否可以扩展，Y代表可以，N代表不可以*/int father;/*指向产生自身的父结点*/}Node;char start[10]={"83426517 "};/*此处没有必要初始化*/char end[10]={"1238 4765"};/*此处没有必要初始化*/Node base[4000];int result[100];/*存放结果的base数组下标号，逆序存放*/int match()/*判断是否为目标*/{int i;for(i=0;i<9;i++){if(base[n-1].matrix[i]!=end[i]){return 0;}}return 1;}void show()/*显示矩阵的内容*/{int i=1;while(m>=0){int mm=result[m];//clrscr();printf("\n\n\n 状态方格\t\t步骤 %d",i);printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].mat rix[1],base[mm].matrix[2]);printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[6],base[mm].matrix[7] ,base[mm].matrix[8]);//sleep(1);m--;i++;}}void leave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/ {n--;while(base[n].father!=-1){result[m]=n;m++;n=base[n].father;}result[m]=0;result[m+1]='\0';show();//clrscr();printf("\n\n\n\n\n\n\n\n\n\t\t\t\t搜索结束\n\n\n\n\n\n\n\n\n\n"); getch();//exit(0);}int left(int x)/*把下标为X的数组中的矩阵的空格左移*/{int i,j;char ch;for(i=0;i<9;i++){if(base[x].matrix[i]==' ')break;}if(i==0||i==3||i==6||i==9){return 0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i-1];base[n].matrix[i-1]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='R';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return 1;}int right(int x)/*把下标为X的数组中的矩阵的空格右移*/ {int i,j;char ch;for(i=0;i<9;i++){if(base[x].matrix[i]==' ')break;}if(i==2||i==5||i==8||i==9){return 0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i+1];base[n].matrix[i+1]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='L';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return 1;}int up(int x)/*把下标为X的数组中的矩阵的空格上移*/ {int i,j;char ch;for(i=0;i<9;i++){if(base[x].matrix[i]==' ')break;}if(i==0||i==1||i==2||i==9){return 0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i-3];base[n].matrix[i-3]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='D';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return 1;}int down(int x)/*把下标为X的数组中的矩阵的空格下移*/ {int i,j;char ch;for(i=0;i<9;i++){if(base[x].matrix[i]==' ')break;}if(i==6||i==7||i==8||i==9){return 0;}for(j=0;j<9;j++){base[n].matrix[j]=base[x].matrix[j];}ch=base[n].matrix[i+3];base[n].matrix[i+3]=base[n].matrix[i];base[n].matrix[i]=ch;base[n].operate='U';base[n].extend='Y';base[n].father=x;base[x].extend='N';n++;if(match(i))leave();return 1;}main(){int i;char a[20],b[20];n=1;//textcolor(LIGHTGREEN);//clrscr();/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/ printf("Please input the start 9 chars:");scanf("%s",a);printf("Please input the end 9 chars:");scanf("%s",b);for(i=0;i<9;i++){if(a[i]=='0'){start[i]=' ';continue;}if(b[i]=='0'){end[i]=' ';continue;}start[i]=a[i];end[i]=b[i];}start[9]='\0';end[9]='\0';for(i=0;i<9;i++){base[0].matrix[i]=start[i];}base[0].operate='N';base[0].extend='Y';base[0].father=-1;/*以上是为第一个base数组元素赋值*/for(i=0;n<4000;i++){if(base[i].extend=='Y'){if(base[i].operate=='L'){right(i);up(i);down(i);}if(base[i].operate=='R'){left(i);up(i);down(i);}if(base[i].operate=='U'){left(i);right(i);down(i);}if(base[i].operate=='D'){left(i);right(i);up(i);}if(base[i].operate=='N'){left(i);right(i);up(i);down(i); }}}}。

#include<stdio.h>#include<stdlib.h>#define null 0static int target[3][3]={1,2,3,8,0,4,7,6,5};//记录最终状态static int K=0;struct node{ int data[3][3]; //定义八数码的初始状态int not_in_position_num; //定义不在正确位置八数码的个数int deapth; //定义了搜索的深度int eva_function; //评价函数的值，每次选取最小的进行扩展struct node *parent;//父节点struct node *next;//下一个节点int end;//表示是否已经扩展，为0未扩展};int not_in_position_num(int s[3][3]) //函数说明：计算s与目标状态的差距值{int i,j;int not_in_position_num=0;for(i=0;i<3;i++)for(j=0;j<3;j++)if(s[i][j]!=target[i][j]){not_in_position_num++;}return not_in_position_num;}int eight_numpara(node *top)//计算启发函数的值{if(top->parent==null )top->deapth=0;elsetop->deapth=top->parent->deapth+1;return top->eva_function=top->not_in_position_num+top->deapth;}node* Into(node *Parent, int x[3][3])//生成一个节点{node *p;p=(node *)malloc(sizeof(node));int i,j;for(i=0;i<3;i++)for(j=0;j<3;j++)p->data[i][j]=x[i][j];p->not_in_position_num=not_in_position_num(x);p->parent=Parent;p->eva_function=eight_numpara(p);p->end=0;return p;}int existed(node *head,int x[3][3])//判断节点是否存在过，先判断这个数是否存在过{int key=1;//未出现过int flag=0;int m,n;struct node *q=head->next;while(q!=null){flag=0;for(m=0;m<3;m++)for( n=0;n<3;n++){if(x[m][n]==q->data[m][n])flag++;}if(flag==9){key=0;//出现过return key;}elseq=q->next;}return key;}node *findleaf(node *head)//寻找估价函数最小的节点{struct node *p=head->next;while(p!=null){if(p->end==1)p=p->next;elsebreak;}struct node *q;q=p;int flag=p->eva_function;while(p!=null){if((p->eva_function<flag)&&(p->end!=1 )){flag=p->eva_function;q=p;}elsep=p->next;}q->end=1;//标志这个节点已经扩展过了return q;}void Print(node *head){int m,n;node *p=head->next;printf("依次输出链表节点\n");while(p!=null){printf("-----------------------------\n");for(m=0;m<3;m++){ for( n=0;n<3;n++){printf("%d\t",p->data[m][n]);}printf("\n");}printf("\n");printf("与目标节点相差：%d\n",p->not_in_position_num);printf("深度为：%d\n",p->deapth);printf("启发函数值：%d\n",p->eva_function);printf("-----------------------------\n");p=p->next;}printf("-----------------------------\n");}void print(node *head)//输出节点数据{int m,n;node *p=head->next;while(p->next!=null){p=p->next;}printf("输出最终结果\n");while(p!=null){printf("-----------------------------\n");for(m=0;m<3;m++){ for( n=0;n<3;n++){printf("%d\t",p->data[m][n]);}printf("\n");}printf("-----------------------------\n" );p=p->parent;}}node *extend(node *head){int i,j,m,n; //循环变量int key;//判断是否出现过，默认未出现过int t;int flag=0;int x[3][3];//临时存放二维数组node *open=head;//指向最后一个节点node *p;node *q;//存储刚生成的节点while(open->next!=null){open=open->next;}p=findleaf(head);//找到代价最小的节点for(i=0;i<3;i++)//找到二维数组中0的位置{for(j=0;j<3;j++)if(p->data[i][j]==0){flag=1;break;}if(flag==1)break;}//情况1for(m=0;m<3;m++)for(n=0;n<3;n++)x[m][n]=p->data[m][n];if(i-1>=0){t=x[i][j];x[i][j]=x[i-1][j];x[i-1][j]=t;key=existed(head,x);if(key==1)//判断是否出现过{q=Into(p,x);//生成一个节q->next=open->next;open->next=q;open=open->next;if(q->not_in_position_num==0){K=1;return head;}}}//情况2for(m=0;m<3;m++)//还原xfor(n=0;n<3;n++)x[m][n]=p->data[m][n];if(i+1<=2){t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t;key=existed(head,x);if(key==1){q=Into(p,x);q->next=open->next;open->next=q;open=open->next;if(q->not_in_position_num==0){K=1;return head;}}}//情况3for(m=0;m<3;m++)//还原xfor(n=0;n<3;n++)x[m][n]=p->data[m][n];if(j-1>=0){t=x[i][j];x[i][j]=x[i][j-1];x[i][j-1]=t;key=existed(head,x);if(key==1){q=Into(p,x);q->next=open->next;open->next=q;open=open->next;if(q->not_in_position_num==0){K=1;return head;}}}//情况4for(m=0;m<3;m++)//还原xfor(n=0;n<3;n++)x[m][n]=p->data[m][n];if(j+1<=2){t=x[i][j];x[i][j]=x[i][j+1];x[i][j+1]=t;key=existed(head,x);if(key==1){q=Into(p,x);q->next=open->next;open->next=q;open=open->next;if( q->not_in_position_num==0){K=1;return head;}}}return head;}void main(){int x[3][3];int i,j;printf("请输入初始状态的8数码（按每行从左往右依次输入,用0表示空格）：\n");for(i=0;i<3;i++)for(j=0;j<3;j++)scanf("%d",&x[i][j]);node *head=null;head=(node *)malloc(sizeof(node));head->next=null;head->parent=null;//生成头结点node *newlist=(node *)malloc(sizeof(node));//生成第一个节点node *p=head;newlist->next=head->next;head->next=newlist;newlist->deapth=0;for(i=0;i<3;i++)for(j=0;j<3;j++)newlist->data[i][j]=x[i][j];newlist->not_in_position_num=not_in_position_num(x);newlist->eva_function=newlist->not_in_position_num;newlist->parent=null;newlist->end=0;while(K!=1){extend(head);}Print(head);print(head); }。

八数码问题的启发式计算
八数码问题是一个十分经典的启发式搜索问题，其中启发式计算可以用来评估搜索状态的优先级。

启发式计算是通过一定的估计方法来估测当前状态距离目标状态的距离或成本，从而帮助搜索算法选择最有希望的路径。

在八数码问题中，可以使用曼哈顿距离作为启发式函数。

曼哈顿距离可以通过将当前状态和目标状态分别转化为二维坐标，并计算两个坐标之间的曼哈顿距离来表示状态之间的距离。

具体步骤如下：
1. 将当前状态和目标状态转换为二维坐标：将每个数字在三乘三的游戏板中的位置映射为坐标，例如将数字1映射为(0, 0)，数字2映射为(1, 0)，以此类推。

2. 对于当前状态的每个数字，计算它与目标状态对应数字的曼哈顿距离：通过求两个数字的坐标的横向距离和纵向距离之和来计算曼哈顿距离。

例如，对于数字4在当前状态的坐标是(1,
2)，在目标状态的坐标是(0, 2)，则它们之间的曼哈顿距离为1。

3. 将所有数字的曼哈顿距离相加，得到当前状态的启发式函数值：将步骤2中计算的所有数字的曼哈顿距离相加，得到当前状态的启发式函数值。

4. 让搜索算法根据启发式函数值优先选择具有较小启发式函数值的状态进行搜索。

使用曼哈顿距离作为启发式计算的方法可以在一定程度上优化搜索算法的效率，使得更有希望到达目标状态的路径更有可能被优先选择。

但需要注意的是，曼哈顿距离只是一种启发式函
数，不能保证一定能找到最优解，可能存在剪枝路径的情况。

若需要保证找到最优解，可以使用A*算法结合曼哈顿距离进行搜索。

#include"stdio.h"int goal[9]={1,2,3,8,0,4,7,6,5},sgoal[9];//goal为棋盘的目标布局,并用中间状态sgoal与之比较struct Board{int pos[9];int d,f,e;//d:深度;f:启发函数;e:记录前一次的扩展节点};struct NodeLink{Board boardstate;NodeLink *parent;NodeLink *previous;NodeLink *next;NodeLink *path;};//更新纪录八数码的状态void setboard(int a[],int b[],int flag) //flag=0,写棋子;flag=1,写棋盘{for(int i=0;i<=8;i++)if(flag)a[b[i]]=i;elseb[a[i]]=i;}//计算启发值的函数int calvalue(int a[]) //不在位棋子数{int c=0;for(int i=0;i<=8;i++)if(a[i]!=goal[i])if(goal[i]!=0)c++;return c;}//生成一个新节点的函数NodeLink *makenode(NodeLink *TEM,int depth,int flag){NodeLink *temp=new NodeLink;for(int i=0;i<=8;i++)temp->boardstate.pos[i]=TEM->boardstate.pos[i];switch(flag){case 1:{temp->boardstate.pos[0]--;temp->boardstate.pos[sgoal[temp->boardstate.pos[0]]]++; //向左移break;}case 2:{temp->boardstate.pos[0]++;temp->boardstate.pos[sgoal[temp->boardstate.pos[0]]]--; //向右移break;}case 3:{temp->boardstate.pos[0]-=3;temp->boardstate.pos[sgoal[temp->boardstate.pos[0]]]+=3; //向上移break;}case 4:{temp->boardstate.pos[0]+=3;temp->boardstate.pos[sgoal[temp->boardstate.pos[0]]]-=3; //向下移break;}}temp->boardstate.d=depth+1;setboard(sgoal,temp->boardstate.pos,1);temp->boardstate.f=temp->boardstate.d+calvalue(sgoal);temp->boardstate.e=flag;temp->parent=TEM;return temp;}//把新节点加入OPEN队列NodeLink *addnode(NodeLink *head,NodeLink *node) //把node插入到head链中{NodeLink *TEM;TEM=head;head=node;head->next=TEM;head->previous=NULL;if(TEM)TEM->previous=head; //TEM已为空,无需操作return head;}//求启发值最小的结点NodeLink *minf(NodeLink *head){NodeLink *min,*forward;min=head;forward=head;while(forward){if(min->boardstate.f>forward->boardstate.f)min=forward;forward=forward->next;}return min;}int main( ){int depth=0;int source[9];int i,j;NodeLink *OPEN=new NodeLink;NodeLink *TEMP,*TEM;printf("请输入初始状态：\n");for(i=0;i<9;i++)scanf("%d",&source[i]);setboard(source,OPEN->boardstate.pos,0);OPEN->boardstate.d=depth;OPEN->boardstate.e=0;OPEN->boardstate.f=depth+calvalue(source);OPEN->next=NULL;OPEN->previous=NULL;OPEN->parent=NULL;while(OPEN){TEMP=minf(OPEN); //求具有最小启发值的节点setboard(sgoal,TEMP->boardstate.pos,1); //写棋盘if(!calvalue(sgoal))break;if(TEMP!=OPEN) //如果不是第一个节点{TEMP->previous->next=TEMP->next;TEMP->next->previous=TEMP->previous;}else//是第一个节点{if(OPEN->next) //如果还有节点{OPEN=OPEN->next;OPEN->previous=NULL;}else OPEN=NULL; //否则置为空}if(TEMP->boardstate.pos[0]-1>=0&&TEMP->boardstate.e!=2) //防止棋子回到原状态 OPEN=addnode(OPEN,makenode(TEMP,depth,1));if(TEMP->boardstate.pos[0]+1<=8&&TEMP->boardstate.e!=1)OPEN=addnode(OPEN,makenode(TEMP,depth,2));if(TEMP->boardstate.pos[0]-3>=0&&TEMP->boardstate.e!=4)OPEN=addnode(OPEN,makenode(TEMP,depth,3));if(TEMP->boardstate.pos[0]+3<=8&&TEMP->boardstate.e!=3)OPEN=addnode(OPEN,makenode(TEMP,depth,4));depth++;}if(OPEN) //如有解,则打印出解的步骤{printf("共需%d 步即可完成。

#include<stdlib.h>#include<stdio.h>#include<math.h>typedef struct Node{//节点结构体int data[9];double f,g;struct Node * parent;}Node,*Lnode;typedef struct Stack{//OPEN CLOSED 表结构体Node * npoint;struct Stack * next;}Stack,* Lstack;Node * Minf(Lstack * Open){//选取OPEN表上f值最小的节点，返回该节点地址Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open);Node * minx;while(temp->next != NULL){if((temp->next ->npoint->f) < (min->npoint->f)){min = temp->next;minp = temp;}temp = temp->next;}minx = min->npoint;temp = minp->next;minp->next = minp->next->next;free(temp);return minx;}int Canslove(Node * suc, Node * goal){//判断是否可解int a = 0,b = 0,i,j;for(i = 1; i< 9;i++)for(j = 0;j < i;j++){if((suc->data[i] > suc->data[j]) && suc->data[j] != 0)a++;if((goal->data[i] > goal->data[j]) && goal->data[j] != 0)b++;}if(a%2 == b%2)return 1;else return 0;}int Equal(Node * suc,Node * goal){//判断节点是否相等，相等，不相等for(int i = 0; i < 9; i ++ )if(suc->data[i] != goal->data[i])return 0;return 1;}Node * Belong(Node * suc,Lstack * list){//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstack temp = (*list) -> next ;if(temp == NULL)return NULL;while(temp != NULL){if(Equal(suc,temp->npoint))return temp -> npoint;temp = temp->next;}return NULL;}void Putinto(Node * suc,Lstack * list){//把节点放入OPEN 或CLOSED 表中Stack * temp;temp =(Stack *) malloc(sizeof(Stack));temp->npoint = suc;temp->next = (*list)->next;(*list)->next = temp;}///////////////计算f值部分-开始//////////////////////////////double Fvalue(Node suc, Node goal, float speed){//计算f值double Distance(Node,Node,int);double h = 0;for(int i = 1; i <= 8; i++)h = h + Distance(suc, goal, i);return h*speed + suc.g; //f = h + g;(speed值增加时搜索过程以找到目标为优先因此可能不会返回最优解)}double Distance(Node suc, Node goal, int i){//计算方格的错位距离int k,h1,h2;for(k = 0; k < 9; k++){if(suc.data[k] == i)h1 = k;if(goal.data[k] == i)h2 = k;}return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3));}///////////////计算f值部分-结束/////////////////////////////////////////////////////扩展后继节点部分的函数-开始/////////////////int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed) {//判断子节点是否属于OPEN或CLOSED表并作出相应的处理Node * temp = NULL;int flag = 0;if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL)){if(Belong(*suc,Open) != NULL) temp = Belong(*suc,Open);else temp = Belong(*suc,Closed);if(((*suc)->g) < (temp->g)){temp->parent = (*suc)->parent;temp->g = (*suc)->g;temp->f = (*suc)->f;flag = 1;}}else{Putinto(* suc, Open);(*suc)->f = Fvalue(**suc, goal, speed);}return flag;}int Canspread(Node suc, int n){//判断空格可否向该方向移动，，，表示空格向上向下向左向右移int i,flag = 0;for(i = 0;i < 9;i++)if(suc.data[i] == 0)break;switch(n){case 1:if(i/3 != 0)flag = 1;break;case 2:if(i/3 != 2)flag = 1;break;case 3:if(i%3 != 0)flag = 1;break;case 4:if(i%3 != 2)flag = 1;break;default:break;}return flag ;}void Spreadchild(Node * child,int n){//扩展child节点的字节点n表示方向，，，表示空格向上向下向左向右移int i,loc,temp;for(i = 0;i < 9;i++)child->data[i] = child->parent->data[i];for(i = 0;i < 9;i++)if(child->data[i] == 0)break;if(n==0)loc = i%3+(i/3 - 1)*3;else if(n==1)loc = i%3+(i/3 + 1)*3;else if(n==2)loc = i%3-1+(i/3)*3;elseloc = i%3+1+(i/3)*3;temp = child->data[loc];child->data[i] = temp;child->data[loc] = 0;}void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed) {//扩展后继节点总函数int i;Node * child;for(i = 0; i < 4; i++){if(Canspread(**suc, i+1)) //判断某个方向上的子节点可否扩展{child = (Node *) malloc(sizeof(Node)); //扩展子节点 child->g = (*suc)->g +1; //算子节点的g值 child->parent = (*suc); //子节点父指针指向父节点Spreadchild(child, i); //向该方向移动空格生成子节点if(BelongProgram(&child, Open, Closed, goal, speed)) // 判断子节点是否属于OPEN或CLOSED表并作出相应的处理free(child);}}}///////////////////////扩展后继节点部分的函数-结束//////////////////////////////////Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed) {//总执行函数while(1){if((*Open)->next == NULL)return NULL; //判断OPEN表是否为空，为空则失败退出Node * minf = Minf(Open); //从OPEN表中取出f 值最小的节点Putinto(minf, Closed); //将节点放入CLOSED表中if(Equal(minf, *goal))return minf; //如果当前节点是目标节点，则成功退出Spread(&minf, Open, Closed, **goal, speed); //当前节点不是目标节点时扩展当前节点的后继节点}}int Shownum(Node * result){//递归显示从初始状态到达目标状态的移动方法if(result == NULL)return 0;else{int n = Shownum(result->parent);for(int i = 0; i < 3; i++){printf("\n");for(int j = 0; j < 3; j++){if(result->data[i*3+j] != 0)printf(" %d ",result->data[i*3+j]);else printf(" ");}}printf("\n");return n+1;}}void Checkinput(Node *suc){//检查输入int i = 0,j = 0,flag = 0;char c;while(i < 9){while(((c = getchar()) != 10)){if(c == ' '){if(flag >= 0)flag = 0;}else if(c >= '0' && c <= '8'){if(flag == 0){suc->data[i] = (c-'0');flag = 1;for(j =0; j < i; j++)if(suc->data[j] == suc->data[i])flag = -2;i++;}else if(flag >= 0)flag = -1;}elseif(flag >= 0)flag = -1;}if(flag <0 || i < 9){if(flag < 0){if(flag == -1)printf("含有非法字符或数字!\n请重新输入:\n");else if(flag == -2)printf("输入的数字有重复!\n请重新输入:\n");}else if(i < 9)printf("输入的有效数字不够!\n请重新输入:\n");i = 0;flag = 0;}}}void main(){//主函数 //初始操作，建立open和closed表Lstack Open = (Stack *) malloc(sizeof(Stack));Open->next = NULL;Lstack Closed = (Stack *) malloc(sizeof(Stack));Closed->next = NULL;Node * org = (Node *) malloc(sizeof(Node));org->parent = NULL; //初始状态节点org->f =1;org->g =1;Node * goal = (Node *) malloc(sizeof(Node)); //目标状态节点Node * result;float speed = 1;//speed搜索速度char c;printf("=================================\n");printf("说明:状态矩阵由0-8 九个数字表示,\n请依次按照九宫格上的行列顺序输入,每个数字间用空格隔开。

/*用启发式算法——A*搜索来解决八数码问题*/#include <stdio.h>#define MAX_BOARD 3*3#define MAX_DEPTH 22typedef struct BroadNode {int array[MAX_BOARD];int g;int h;int f;int depth;struct BroadNode *parent;}BNode, *BiNode;/*估计函数h(n)的计算，等于错置的图块数*/int evaluateBoard(BiNode T){int i, score;const int test[MAX_BOARD-1]={1,2,3,4,5,6,7,8};score = 0;for(i=0; i<MAX_BOARD-1; i++)score += (T->array[i] != test[i]);return score;}/*A*搜索，解决八数码问题*/void astarEightNumber(){int i;BiNode cur_board_p, child_p, temp;while(listEmpty(&openList_p)==false){/*从OPEN优先队列中，选取第一个，即f(n)最小的结点*/cur_board_p = getListBest(&openList_p);putList(&closedList_p, cur_board_p);if(cur_board_p->h == 0) /*h(n)==0，则表示找到了目标结点*/{/*输出路径过程，即从初始结点到目标结点路径上的每个结点*/showSolution(cur_board_p);return;}else{/*由于平均22步，就应该能找到解，故h(n)>22，则放弃该结点，继续查看其他的*/if(cur_board_p->depth > MAX_DEPTH)continue;/*列举从当前状态(结点)出发，所有可能的移动(子结点)，最多4种移法*/for(i=0; i<4; i++){ /*找到下一个子结点*/child_p = getChildBoard(cur_board_p, i);if(child_p == (BiNode)0)continue;/*如果child_p在CLOSED表中，则抛弃child_p，继续循环*/if(onList(&closedList_p, child_p->array, NULL)){nodeFree(child_p);continue;}child_p->depth = cur_board_p->depth+1;child_p->h = evaluateBoard(child_p);child_p->g = child_p->depth;child_p->f = child_p->h + child_p->g;/*如果child_p在OPEN表上，则*/if(onList(&openList_p, child_p->array, NULL)) {temp = getList(&openLisy_p, child_p->array);if(temp->f < child_p->f) {nodeFree(child_p);putList(&openList_p, temp);continue;}nodeFree(temp);child_p->parent = cur_board_p;putList(&openList_p, child_p);}else {/*child_p既不在CLOSED表上，也不在OPEN表上，则将其插入OPEN 表即可*/child_p->parent = cur_board_p;putList(&openList_p, child_p);}}}};}。

1、程序源代码#include <stdio.h>#include<malloc.h>struct node{int a[3][3];//用二维数组存放8数码int hx;//函数h（x）的值，表示与目标状态的差距struct node *parent;//指向父结点的指针struct node *next;//指向链表中下一个结点的指针};//------------------hx函数-------------------//int hx(int s[3][3]){//函数说明：计算s与目标状态的差距值int i,j;int hx=0;int sg[3][3]={1,2,3,8,0,4,7,6,5};for(i=0;i<3;i++)for(j=0;j<3;j++)if(s[i][j]!=sg[i][j])hx++;return hx;}//-------------hx函数end----------------------////-------------extend扩展函数----------------//struct node *extend(node *ex){ //函数说明：扩展ex指向的结点，并将扩展所得结点组成一条//单链表，head指向该链表首结点，并且作为返回值int i,j,m,n; //循环变量int t; //临时替换变量int flag=0;int x[3][3];//临时存放二维数组struct node *p,*q,*head;head=(node *)malloc(sizeof(node));//headp=head;q=head;head->next=NULL;//初始化for(i=0;i<3;i++)//找到二维数组中0的位置{for(j=0;j<3;j++)if(ex->a[i][j]==0){flag=1;break;}if(flag==1)break;}for(m=0;m<3;m++)//将ex->a赋给xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];//根据0的位置的不同，对x进行相应的变换//情况1if(i-1>=0){t=x[i][j];x[i][j]=x[i-1][j];x[i-1][j]=t;flag=0;for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n])flag++;if(flag!=9){q=(node *)malloc(sizeof(node));for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);q->next=NULL;p->next=q;p=p->next;}}//情况2for(m=0;m<3;m++)//将ex->a重新赋给x，即还原x for(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(i+1<=2){t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t; flag=0;for(m=0;m<3;m++)for(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n])flag++;if(flag!=9){q=(node *)malloc(sizeof(node));for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);q->next=NULL;p->next=q;p=p->next;}}//情况3for(m=0;m<3;m++)//将ex->a重新赋给x，即还原x for(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(j-1>=0){t=x[i][j];x[i][j]=x[i][j-1];x[i][j-1]=t;flag=0;for(m=0;m<3;m++)for(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n])flag++;if(flag!=9){q=(node *)malloc(sizeof(node));for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);q->next=NULL;p->next=q;p=p->next;}}//情况4for(m=0;m<3;m++)//将ex->a重新赋给x，即还原xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(j+1<=2){t=x[i][j];x[i][j]=x[i][j+1];x[i][j+1]=t;flag=0;for(m=0;m<3;m++)for(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n])flag++;if(flag!=9){q=(node *)malloc(sizeof(node));for(m=0;m<3;m++)for(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);q->next=NULL;p->next=q;p=p->next;}}head=head->next;return head;}//---------------extend函数end-----------------------////----------------insert函数-------------------------//node* insert(node *open,node * head){ //函数说明：将head链表的结点依次插入到open链表相应的位置， //使open表中的结点按从小到大排序。

图搜索与问题求解实验报告一实验题目图搜索与问题求解二实验目的1熟悉和掌握启发式搜索/A*搜索的定义、估价函数和算法过程；2 理解和掌握搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3 比较并分析图搜索策略的实质，通过实验理解启发式搜索/A*搜索的意义。

三实验要求1以九宫问题/八数码问题为例，以某种启发式搜索/A*搜索策略编程演示其搜索过程；2 定义启发式函数,能正确求解出从初始状态到目标状态的移动路线；3 对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。

四数据结构typedef struct Qnode{ //队列的节点类型定义long a; //将8数码转化为长整型后入队列int dnum; //与目标状态数码不同的位置的个数Qnode *next;}*QueuePtr;typedef struct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针}LinkQueue; //链式队列五实验算法1 说明有解和无解如何判定；int NiXu(int a[][3]) //求出所给状态的逆序数{i nt i,j,k=0,sum=0;i nt b[8];f or(i=0;i<3;i++)for(j=0;j<3;j++)if(a[i][j]) //空格用0代替，逆序不计空格b[k++]=a[i][j];for(i=1;i<8;i++)for(j=0;j<i;j++)if(b[i]<b[j])sum++;return sum;}if(NiXu(start)%2 != NiXu(end)%2)printf("无法到达！\n");e lse{printf("广度优先搜索如下：\n\n");search();}2 说明启发式函数如何设定；int h(long x){i nt sum=0;i nt b[3][3];u_trans(x,b);f or (int i=0;i<3;i++)for (int j=0;j<3;j++)if (end[i][j]!=b[i][j])sum++;r eturn sum;}3说明实验中采用的搜索算法。

实验报告姓名：***学号：**********班级：软件二班实验名称：启发式搜索课程名称：人工智能实验日期：2015.11.09实验环境：Visual C++实验目的以及内容：1、实验内容：使用启发式搜索算法求解八数码问题。

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

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

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

3. 实验原理：八数码问题是在3行和3列构成的九宫棋盘上放置数码为1到8的8个棋盘，剩下一个空格的移动来不断改变棋盘的布局，求解这类问题的方法是：给定初始布局（即初始状态）和目标布局（即目标状态），定义操作算子的直观方法是为每个棋牌制定一套可能的走步》上，下，左，右四种移动，再根据所定义的启发式搜索函数在搜索过程中选择最合适的操作算子，得到最优的路径。

代码：#include"stdio.h"#define num 3void show(int begin[num][num]){for(int i = 0; i < num; i++){for(int j = 0; j < num; j++)printf("%d ", begin[i][j]);printf("\n");}printf("\n");}void exchange(int begin[num][num], int row_one, int column_one, int row_two, int column_two){int temp;temp = begin[row_two][column_two] ;begin[row_two][column_two] = begin[row_one][column_one];begin[row_one][column_one] = temp;}int judge(int begin[num][num], int end[num][num]){int count=0;for(int i = 0; i < num; i++)for(int j = 0; j < num; j++){if(begin[i][j] == end[i][j] && end[i][j] != 0)count++;}return count;}int yidong(int begin[num][num], int end[num][num], int right, int jishu, int ji_shu[50][3][3], int biaoji, int row, int column){int temp_zhi;show(begin);if(jishu >= 20)return 0;int node;int temp;for(int q=0; q<jishu; q++){node = 1;for(int w=0; w<num && node; w++)for(int r=0; r<num && node; r++)if(ji_shu[q][w][r] != begin[w][r])node = 0;if(node == 1){return 0;}}for(int i = 0; i < num; i++)for(int j = 0; j < num; j++)ji_shu[jishu][i][j] = begin[i][j];if(right == num * num - 1)return 1;if(row > 0 && biaoji != 0){exchange(begin, row - 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row - 1, column, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column);if( temp_zhi == 1)return 1;exchange(begin, row - 1, column, row , column);}}if(column > 0 && biaoji != 1){exchange(begin, row, column - 1, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row, column - 1, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column -1);if(temp_zhi == 1)return 1;exchange(begin, row, column - 1, row , column);}}if(row < num-1 && biaoji != 2){exchange(begin, row + 1, column, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row + 1, column, row , column);else if(temp >= right){temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column);if(temp_zhi == 1)return 1;exchange(begin, row + 1, column, row , column);}}if(column < num-1 && biaoji != 3){exchange(begin, row, column + 1, row , column);temp = judge(begin, end);if(temp < right)exchange(begin, row, column + 1, row , column);else if(temp >= right){temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1);if(temp_zhi == 1)return 1;exchange(begin, row, column + 1, row , column);}}return 0;}void shuru(int begin[][num],int blank[]){int temp, node, zero = 0;for (int i = 0; i < num; i++)for(int j = 0; j < num; j++){node = 1;printf("请输入第%d行，第%d列的元素的值：", i+1, j+1);scanf("%d", &temp);for (int q = 0; q <= i && node == 1; q++)for (int w = 0; w < j; w++)if(temp == begin[q][w]){printf("输入重复，请重新输入\n");node = 0;j--;break;}if(temp < 0 || temp > num*num-1){printf("请输入从%d到%d的数\n", zero, num*num-1);node = 0;j--;}if(node == 1){if(temp == 0){blank[0] = i;blank[1] = j;}begin[i][j] = temp;}}}int main(){int jishu = 0, ji_shu[50][3][3];int row;int column;int begin[num][num], blank[2],count=1;int end[num][num] = {1, 2, 3, 8, 0, 4, 7, 6, 5};printf ("-------8数码游戏开始！--------\n");shuru(begin, blank);row = blank[0];column = blank[1];if(yidong (begin, end,judge(begin,end),jishu,ji_shu,4,row,column) == 0)printf("\n此8数码的问题可能无解！");elseshow(begin);getchar();getchar();return 0;}实验截图：实验总结：1、A*搜索算法：取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中每一个数码牌与其目标位置之间的距离（不考虑夹在其间的数码牌）的总和，由于从结点n转换成目标结点至少需要w(n)步，所以对任意n，恒有w(n) ≤h*(n)。

人工智能基础大作业----八数码难题学院:数学与计算机科学学院2016.12.20一、实验名称八数码难题的启发式搜索二、实验目的八数码问题：在3×3的方格棋盘上，摆放着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<stdio.h># include<string.h># include<malloc.h># include<stdlib.h>typedef struct node {int i,cost,degree,exp,father;int a[3][3];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; }else{position(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;j<3;j++)for(k=0;k<3;k++)scanf("%d",&s->a[j][k]); };int cmpnode(treenode *s1,treenode *s2){ int j,k;for(j=0;j<3;j++)for(k=0;k<3;k++) {if(s1->a[j][k]!=s2->a[j][k])return 0; };return 1; }int test(treenode *s1,treenode *s2) { int j,k,n=0;for(j=0;j<3;j++)for(k=0;k<3;k++) {if(s1->a[j][k]!=s2->a[j][k])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;j<3;j++)for(k=0;k<3;k++)s1->a[j][k]=s2->a[j][k];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;j<3;j++) {for(k=0;k<3;k++) {printf("%2d",s->a[j][k]); }if(j==1) printf(" n=%2d d=%2df=%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;m<3;m++) {for(n=0;n<3;n++) {k=s->a[m][n];if(k==0)break; };if(k==0) break; }if(m+1<=2&&flag==0) {r1=(treenode*)malloc(sizeof(treenode));cpynode(r1,s);t=r1->a[m+1][n];r1->a[m+1][n] = r1->a[m][n];r1->a[m][n]=t;extend(r1,s,s1,open,close); };if(m-1>=0&&flag==0) {r1=(treenode*)malloc(sizeof(treenode));cpynode(r1,s);t=r1->a[m-1][n];r1->a[m-1][n]=r1->a[m][n];r1->a[m][n]=t;extend(r1,s,s1,open,close); };if(n-1>=0 && flag==0) {r1=(treenode*)malloc(sizeof(treenode));cpynode(r1,s);t=r1->a[m][n-1];r1->a[m][n-1]=r1->a[m][n];r1->a[m][n]=t;extend(r1,s,s1,open,close); };if(n+1<=2 && flag==0) {r1=(treenode*)malloc(sizeof(treenode));cpynode(r1,s);t=r1->a[m][n+1];r1->a[m][n+1]=r1->a[m][n];r1->a[m][n]=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.搜索过程请输入八数码的初始状态：（以空格为分隔）2 8 31 0 47 6 5请输入八数码的目标状态：（以空格为分隔）1 2 38 0 47 6 5搜索过程如下：2 8 31 0 4 n= 1 d= 0 f= 07 6 52 0 31 8 4 n= 3 d= 1 f= 17 6 50 2 31 8 4 n= 8 d=2 f= 37 6 51 2 30 8 4 n=10 d= 3 f= 87 6 51 2 38 0 4 n=12 d= 4 f=107 6 55 步,12 个节点Press any key to continue六、实验分析：在进行搜索的过程中，同时记录了扩展新节点的个数。

启发式搜索实验报告2015-2016第1学期《人工智能基础》实验报告实验名称:启发式搜索算法专业班级学号姓名1、实验环境Visual C++ 6.02、实验目的和要求(复述问题)使用启发式算法求解8数码问题(1) 编制程序实现求解8数码问题A*算法，采用估价函数f(n)=d(n)+p(n)其中:d(n)是搜索树中结点n的深度;w(n)为节点n的数据库中错放的旗子个数;p(n)为结点n的数据库中每个棋子与其目标位置之间的距离总和。

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

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

3、解题思路、代码3.1解题思路八数码问题的求解算法(1) 盲目搜索宽度优先搜索算法、深度优先搜索算法(2) 启发式搜索启发式搜索算法的基本思想是:定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

先定义下面几个函数的含义:f*(n)=g*(n)+h*(n) (1)式中g*(n)表示从初始节点s到当前节点n的最短路径的耗散值;h*(n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n)表示从初始节点s经过n到目标节点g的最短路径的耗散值。

评价函数的形式可定义如(2)式所示:f(n)=g(n)+h(n) (2)其中n是被评价的当前节点。

f(n)、g(n)和h(n)分别表示是对f*(n)、g*(n)和h*(n)3个函数值的估计值。

利用评价函数f(n)=g(n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。

在A算法中，如果对所有的x，h(x)<=h*(x) (3)成立，则称好h(x)为h*(x)的下界，它表示某种偏于保守的估计。

采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法针对八数码问题启发函数设计如下:F(n)=d(n)+p(n) (4)1 / 112015-2016第1学期《人工智能基础》实验报告其中A*算法中的g(n)根据具体情况设计为d(n)，意为n节点的深度，而h(n)设计为p(n)，意为放错的数码与正确的位置距离之和。

c++算法八数码问题八数码问题是一种经典的智力游戏，其规则是在有限的格子中，按照一定的顺序将数字旋转移动到目标位置。

为了解决这个问题，我们可以使用算法的思想来设计一种有效的解决方案。

一、问题描述八数码问题是一个有N×N的棋盘，其中每个格子代表一个数字。

玩家需要按照一定的顺序旋转数字，将它们移动到目标位置。

目标位置是预先设定好的，玩家需要按照规则移动数字，使得棋盘上的数字按照正确的顺序排列。

二、算法思想为了解决八数码问题，我们可以使用贪心算法的思想。

首先，我们需要找到一个初始状态，这个状态应该是最简单、最容易解决的问题。

然后，我们通过循环迭代的方式，不断尝试不同的旋转方式，直到找到一个能够满足目标位置的解决方案。

三、C语言实现下面是一个简单的C语言实现，用于解决八数码问题。

这个程序使用了递归和回溯的方法，通过穷举所有可能的旋转方式来找到解决方案。

```c#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#define N 3// 定义棋盘状态结构体typedef struct {int nums[N][N];int num_count[N][N]; // 记录每个数字出现的次数} Board;// 判断两个数字是否相邻bool is_adjacent(int num1, int num2) {int dx[] = {-1, 0, 1};int dy[] = {0, -1, 1};for (int i = 0; i < 3; i++) {if (abs(nums[num1][i] - nums[num2][i]) <= 1) {return true;}}return false;}// 寻找最优解函数bool find_optimal_solution(Board& board, int target_row, int target_col) {// 初始化最优解为空状态bool optimal_solution = false;int optimal_score = INT_MAX; // 最优解的得分初始化为最大整数int best_score = INT_MAX; // 最优解的当前得分初始化为最大整数加一// 对当前棋盘进行遍历for (int row = 0; row < N; row++) {for (int col = 0; col < N; col++) {// 如果当前状态为空状态，则直接跳过if (board.nums[row][col] == 0) {continue;}// 记录当前状态的信息，包括得分和旋转次数等int score = calculate_score(board, row, col); // 计算得分函数在实现中定义了旋转方式的选择和得分计算规则等具体细节，这里省略了具体实现细节。