深度宽度优先搜索 - 八数码

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. 曼哈顿距离曼哈顿距离是指当前状态的每个数字到目标状态的正确位置之间的曼哈顿距离之和。

曼哈顿距离可以更准确地评估当前状态与目标状态的“距离”，因此在某些情况下，比误放置数目更适合作为启发函数。

3. 线性冲突线性冲突是指在某一行或某一列中有两个数字的目的位置相互交叉，这种情况下移动其中一个数字就会导致另一个数字也需要移动。

线性冲突可以影响搜索的效率，因此考虑线性冲突可以使启发函数更精确地评估当前状态与目标状态的“距离”。

二、代价函数的选择代价函数是指在搜索过程中用来评估节点的“代价”的函数，它可以指导搜索算法在选择候选节点时进行排序，从而提高搜索效率。

在八数码问题中，常用的代价函数有实际代价和估计代价等。

1. 实际代价实际代价是指从初始状态到当前状态的实际代价，它可以作为代价函数来评估当前状态的“代价”。

通过记录从初始状态到当前状态的实际代价，搜索算法可以更准确地评估每个候选节点的“代价”，从而更有针对性地选择下一个节点。

2. 估计代价估计代价是指从当前状态到目标状态的估计代价，它可以作为代价函数来评估当前状态的“代价”。

估计代价通常是通过启发函数来估计的，因此选择合适的启发函数对于估计代价的准确性非常重要。

/*程序利用C++程序设计语言，在VC6.0下采用宽度优先的搜索方式，成功的解决了八数码问题。

程序中把OPEN表和CLOSED表用队列的方式存储，大大地提高了效率，开始的时候要输入目标状态和起始状态，由于在宽度优先搜索的情况下，搜索过程中所走过的状态是不确定且很庞大的，所以程序最后输出宽度优先情况下最少步数的搜索过程以及程序运行所需要的时间*/#include "iostream"#include "stdio.h"#include "stdlib.h"#include "time.h"#include "string.h"#include <queue>#include <stack>using namespace std;constint N = 3;//3*3图enum Direction{None,Up,Down,Left,Right};//方向staticint n=0;staticint c=0;struct Map//图{int cell[N][N];//数码数组Direction BelockDirec;//所屏蔽方向struct Map * Parent;//父节点};//打印图voidPrintMap(struct Map *map){cout<<"*************************************************"<<endl;for(int i=0;i<N;i++){for(int j=0;j<N;j++){cout<<map->cell[i][j]<<" ";}cout<<endl;}cout<<"*************************************************"<<endl;}//移动图struct Map * MoveMap(struct Map * map,DirectionDirect,boolCreateNewMap){struct Map * NewMap;//获取空闲格位置inti,j;for(i = 0; i < N; i++){ boolHasGetBlankCell = false; for(j = 0; j < N; j++){if(map->cell[i][j] == 0){ HasGetBlankCell = true; break;}}if(HasGetBlankCell) break;}//移动数字intt_i = i,t_j = j; boolAbleMove = true; switch(Direct){case Down:t_i++;if(t_i>= N)AbleMove=false;break;case Up:t_i--;if(t_i< 0)AbleMove=false;break;case Left:t_j--;if(t_j< 0)AbleMove=false;break;case Right:t_j++;if(t_j>= N)AbleMove=false;break;};if(!AbleMove)//不可以移动则返回原节点{return map;}if(CreateNewMap){NewMap = new Map();for(int x = 0; x < N; x++)for(int y = 0; y < N; y++)NewMap->cell[x][y] = map->cell[x][y];}elseNewMap = map;NewMap->cell[i][j] = NewMap->cell[t_i][t_j];NewMap->cell[t_i][t_j] = 0;returnNewMap;}boolIsSuccess(struct Map * map,struct Map * Target){boolIsSuc = true;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){if(map->cell[i][j] != Target->cell[i][j]){IsSuc = false;break;}}if(!IsSuc)break;}returnIsSuc;}struct Map * BNF_Search(struct Map * begin,struct Map * Target) {struct Map * p1, *p2, *p=NULL;boolIsSucc = false;queue<struct Map *> Queue;if(IsSuccess(begin,Target))return begin;Queue.push(begin);do{p1 = Queue.front();Queue.pop();for (int i = 1; i <= 4; i++){Direction Direct=(Direction)i;if(Direct == p1->BelockDirec)//跳过屏蔽方向continue;p2 = MoveMap(p1,Direct,true);if(p2 != p1) //数码是否可以移动{p2->Parent = p1;switch(Direct)//设置屏蔽方向,防止往回推{case Up:p2->BelockDirec = Down;break;case Down:p2->BelockDirec = Up;break;case Left:p2->BelockDirec = Right;break;case Right:p2->BelockDirec = Left;break;}if (IsSuccess(p2,Target)){p = p2;return p;}Queue.push(p2);n++;}}}while(!Queue.empty() || p == NULL);return p;}intJou(struct Map *map) //将八数码转换成一个数列，并计算其逆序数{int a=0;char b[9];for(int i=0;i<N;i++){for(int j=0;j<N;j++)b[i*3+j]=map->cell[i][j];}for(int k=0;k<9;k++){for(int h=0;h<k;h++){if((b[h]<b[k])&&b[h]!=0)a++;}}return a%2;}int main(){int a1,a2;inti,j,m,n;int target[9];int flag;Map Target;Map *begin,*T;begin=new Map;cout<<"请输入八数码的目标状态(用0代替空格):"<<endl;//输入目标状态for (i=0;i<9;i++) //此for循环用来把输入的数存入到target数组中{flag=0;cin>>target[i];for(j=0;j<i;j++)if(target[i]==target[j])flag=1;if (target[i]<0||target[i]>8||flag==1) //判断输入是否正确{i--;cout<<"输入错误，请关闭重新运行!\n";}}int k=0;for (m=0;m<3;m++) //把数组target中的数传给图Target {for (n=0;n<3;n++){Target.cell[m][n]=target[k];k++;}}//输入起始状态cout<<"请输入八数码的起始状态(用0代替空格):"<<endl;for (i=0;i<9;i++){flag=0;cin>>target[i];for(j=0;j<i;j++)if(target[i]==target[j]) //判断输入的数是否正确flag=1;if (target[i]<0||target[i]>8||flag==1){i--;cout<<"输入错误，请关闭重新运行!\n";}}k=0;for (m=0;m<3;m++){for (n=0;n<3;n++){begin->cell[m][n]=target[k];k++;}}begin->Parent = NULL;begin->BelockDirec = None;cout<<"目标图:"<<endl;PrintMap(&Target);cout<<"起始图:"<<endl;PrintMap(begin);a1=Jou(&Target);a2=Jou(begin);if(a1!=a2){cout<<"无解"<<endl;exit(0); //无解的话就退出，重新运行}else{double start=clock();cout<<"有解"<<endl;//图搜索T=BNF_Search(begin,&Target);//打印if(T != NULL){//把路径倒序Map *p=T;stack<Map *> Stack1;while(p->Parent != NULL){Stack1.push(p);p = p->Parent;}cout<<"宽度优先最少步数的搜索过程为:"<<endl;while(!Stack1.empty()){PrintMap(Stack1.top());c++;Stack1.pop();}cout<<"\n完成!"<<endl;cout<<"找到目标状态所需要的最少步数为:"<<c<<endl;double end=clock();cout<<"程序运行的时间为:"<<end-start<<"ms"<<endl;}}return 0;}。

八数码实验报告八数码实验报告引言：八数码，也被称为滑块拼图，是一种经典的益智游戏。

在这个实验中，我们将探索八数码问题的解决方案，并分析其算法的效率和复杂性。

通过这个实验，我们可以深入了解搜索算法在解决问题中的应用，并且探讨不同算法之间的优劣势。

1. 问题描述：八数码问题是一个在3x3的方格上进行的拼图游戏。

方格中有8个方块，分别标有1到8的数字，还有一个空方块。

游戏的目标是通过移动方块，将它们按照从左上角到右下角的顺序排列。

2. 算法一：深度优先搜索（DFS）深度优先搜索是一种经典的搜索算法，它从初始状态开始，不断地向前搜索，直到找到目标状态或者无法继续搜索为止。

在八数码问题中，深度优先搜索会尝试所有可能的移动方式，直到找到解决方案。

然而，深度优先搜索在解决八数码问题时存在一些问题。

由于搜索的深度可能非常大，算法可能会陷入无限循环，或者需要很长时间才能找到解决方案。

因此，在实际应用中，深度优先搜索并不是最优的选择。

3. 算法二：广度优先搜索（BFS）广度优先搜索是另一种常用的搜索算法，它从初始状态开始，逐层地向前搜索，直到找到目标状态。

在八数码问题中，广度优先搜索会先尝试所有可能的一步移动，然后再尝试两步移动，依此类推，直到找到解决方案。

与深度优先搜索相比，广度优先搜索可以保证找到最短路径的解决方案。

然而，广度优先搜索的时间复杂度较高，尤其是在搜索空间较大时。

因此，在实际应用中，广度优先搜索可能不太适合解决八数码问题。

4. 算法三：A*算法A*算法是一种启发式搜索算法，它在搜索过程中利用了问题的启发信息，以提高搜索效率。

在八数码问题中，A*算法会根据每个状态与目标状态之间的差异，选择最有可能的移动方式。

A*算法通过综合考虑每个状态的实际代价和启发式估计值，来评估搜索路径的优劣。

通过选择最优的路径，A*算法可以在较短的时间内找到解决方案。

然而，A*算法的实现较为复杂，需要合适的启发函数和数据结构。

八数码实验报告范文利用人工智能技术解决八数码游戏问题1．八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。

问题是在3某3方格盘上，放有八个数码，剩下第九个为空，每一空格其上下左右的数码可移至空格。

问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始位置转化为目标位置。

2．八数码游戏问题的状态空间法表示①建立一个只含有初始节点0的搜索图g，把0放入open表中②建立cloed表，且置为空表③判断open表是否为空表，若为空，则问题无解，退出④选择open表中的第一个节点，把它从open表移出，并放入cloed表中，将此节点记为节点n⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。

问题的解就是沿着n到0的路径得到。

若不是转⑥⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合m，将m中的这些节点作为n的后继节点加入图g中⑦对未在g中出现过的（open和cloed表中未出现过的）集合m中的节点,设置一个指向父节点n的指针，并把这些节点放入open表中；对于已在g中出现过的m中的节点，确定是否需要修改指向父节点的指针；对于已在g中出现过并已在cloed表中的m中的节点，确定是否需要修改通向他们后继节点的指针。

⑧按某一任意方式或某种策略重排open表中节点的顺序⑨转③3．八数码游戏问题的盲目搜索技术宽度优先搜索：1、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firtearch)。

2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

3、宽度优先搜索算法(1)把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。

(2)如果open是个空表，则没有解，失败退出；否则继续。

(3)把第一个节点(节点n)从open表移出，并把它放入cloed的扩展节点表中。

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

一、“八”数码问题的宽度优先搜索步骤如下：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个节点时得到了目标节点。

宽度优先算法求解八数码问题介绍八数码问题是一种经典的数学问题，在计算机科学中常用于算法研究和图搜索算法的测试。

它的目标是将一个3×3的九宫格中的数字从初始状态通过交换移动到目标状态。

宽度优先算法是一种常用的图搜索算法，适用于求解八数码问题。

它通过广度优先搜索图中的所有节点，直到找到目标节点。

本文将详细介绍宽度优先算法在求解八数码问题中的应用，包括算法原理、示例演示和应用场景。

算法原理宽度优先算法是一种盲目搜索算法，它使用队列（FIFO）数据结构来实现搜索过程。

它从初始状态开始，将其加入队列中，并继续搜索与初始状态相邻的所有状态。

然后，将与初始状态相邻的状态加入队列，并依次搜索下去。

直到找到目标状态，或者搜索完所有可能的状态。

为了避免重复搜索相同的状态，我们需要使用一个哈希表来记录已经访问过的状态。

每次搜索时，我们首先检查当前状态是否已经访问过，如果已经访问过则跳过，否则将其加入队列中并标记为已访问。

宽度优先算法的时间复杂度为 O(b^d)，其中 b 是分支因子，d 是目标状态的深度。

在八数码问题中，分支因子为 4，深度一般不会超过 30，因此宽度优先算法具有较高的效率。

算法步骤宽度优先算法的求解步骤如下：1.初始化队列和哈希表，并将初始状态加入队列和哈希表中。

2.当队列不为空时，执行以下步骤：2.1 弹出队列的第一个状态。

2.2 检查当前状态是否为目标状态，如果是则结束搜索。

2.3 遍历当前状态的所有相邻状态。

2.4 对于每个相邻状态，检查是否已经访问过，如果没有则将其加入队列和哈希表中，并标记为已访问。

3.如果队列为空且没有找到目标状态，则无解。

示例演示为了更好地理解宽度优先算法在求解八数码问题中的应用，我们通过一个实际的例子来演示算法的执行过程。

假设我们有一个初始状态如下的八数码问题：2 8 31 47 6 5我们的目标是将其移动到如下的目标状态：1 2 38 47 6 5下面是宽度优先算法在求解该问题时的执行步骤：1.将初始状态加入队列和哈希表中。

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.五、实验结果六、实验总结通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。

⼈⼯智能结课作业-DFSBFSAstar解决⼋数码问题如果帮到你了，希望给个star⿎励⼀下1 深度优先遍历搜索(DFS)1.1算法介绍深度优先搜索算法（Depth-First-Search，DFS）是⼀种⽤于遍历或搜索树或图的算法。

沿着树的深度遍历树的节点，尽可能深的搜索树的分⽀。

当节点v的所在边都⼰被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

这⼀过程⼀直进⾏到已发现从源节点可达的所有节点为⽌。

如果还存在未被发现的节点，则选择其中⼀个作为源节点并重复以上过程，整个进程反复进⾏直到所有节点都被访问为⽌。

属于盲⽬搜索。

以上图为例，简述DFS的过程。

⾸先从根节点"1"出发，按⼀定的顺序遍历其⼦节点，这⾥我们假设优先遍历左边的。

所以，在遍历"1"之后，我们到了节点"2"，此时"2"仍有⼦节点，所以应继续向下遍历，下⼀个节点是"3"，然后是"4"。

到了"4"之后，没有⼦节点了，说明我们已经将这⼀条路遍历完了，接着我们应该回溯，应该回到"4"的⽗节点，也就是"3"。

因为"3"还有⼀个⼦节点"5"没有遍历，所以下⼀个我们应该遍历的是"5"。

遍历完"5"之后⼜发现⼀条路到头了，再次回溯依然回溯到其⽗节点"3"，此时"3"的所有⼦节点都已经遍历完了，因该接着回溯到"3"的⽗节点"2"，然后检查"2"是否有没有遍历完的⼦节点。

按照这样的规则，完成所有节点的遍历。

最终得到的遍历顺序是"1-2-3-4-5-6-7-8-9-10-11-12"在介绍了DFS在遍历树的应⽤后，我们将其应⽤于⼋数码问题的解决。

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

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

举个简单的例⼦，“机器学习（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个棋牌，剩下⼀个空格，只能通过棋牌向空格的移动来改变棋盘的布局。

八数码的几种解决帖子关于是八数码的，是前段时间写的，为了给别人一些搜索的样例。

现在，事差不多完了，代码还留着，觉着放着浪费，又想自己水平过于欠缺，再加上看在C吧的初学者还是占主要，就觉得发在此处共他们学习还是不错的，仅此而已。

如果有不知道八数码的问题的，可以上网一搜，就什么都明白了。

在这里我只用了几种算法实现，其实还有其他方法，我并没有写（如果有人需要，可能我会重新完成）。

首先分析下八数码的一些算法吧。

1：深度优先（DFS）：这个方法起始对八数码非常不好，问题在于搜索过于盲目，搜索深度如果没有限制，有些是根本没必要的（因为八数码的解，大部分集中在20~30步之间）。

而且即使搜索到一个解，很可能不是最优解。

所以用DFS解决这个问题并不明智，不过为了显示其不好，我仍然实现，不过在程序中设置最大深度限制为100。

2：宽度优先搜索（BFS）宽度优先搜索，解决的还不错，经过对hash函数的优化，能使一个20~30步的解在200~300MS内解决（不过其还可以做进一步的优化）。

3：迭代加深搜索迭代加深搜索，可以说是吸取了宽搜和深搜的优点，同时避免了深搜搜到第一个解的不最优性，和宽搜的使用较大的内存空间。

在这里我也用迭代加深搜索，仔细一看的人就发现，起使他只是在深搜上稍微做点“手脚”就完毕，但是其思想，虽然显而易见，可我觉得并不容易想到（指当初提出这个算法的时候）。

4：爬山法爬山法，经常在人工只能里面见得到，由于其高效，实现简单，所以其有时也是很有用的。

但是爬山法，也有缺点，就是搜到的解只是局部最优解，而且有陷入“无解”的风险。

爬山法，顾名思意就是一直沿着“最好的方向走”直到“山顶”，就找到解。

爬山法，不像回溯，在遍历节点时不保存其他非当前最优节点，也就是说，一旦走错了，就不能再后头搜索其他方向。

所以在我写的爬山法中，对于一个解，虽然很多100多步，但是所需的时间确实0MS左右。

5：双向搜索双向搜索，前后来搜，碰到头，然后一拼接就出了路径。

西安电子科技大学课程论文数据结构八数码问题求解班级：071271作者：方正阳学号：07127020时间：2013.12.17摘要：八数码求解问题是人工智能中一个很典型的智力问题。

本文套用经典宽度搜索框架来讨论八数码问题，给出了宽度优先搜索算法与实现的思想。

用链表法来表示邻接点的访问序列，从而完成对图的遍历。

根据宽度优先搜索的策略，被搜索到的顶点上的distance标记就是到源顶点的最短路径的距离，因此可以解决无权图的最短路径问题以及由其抽象而来的最优问题。

引言：八数码游戏（八数码问题）描述为：在3×3方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格（可以看作是空格移动，它最多可以有４个方向的移动，即上、下、左、右），这样通过移动将牌就可以不断改变将牌的布局。

这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。

一、需求分析初始状态：8个数字码和空格在3×3棋盘上的所有格局组成了问题的状态空间。

其中，状态空间中的任一种状态都可以作为初始状态。

后继状态：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。

目标测试：比较当前状态和目标状态的格局是否一致。

路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。

具体要求：1.输入初始状态和目标状态的数据；例：初始状态:2 8 3 1 6 4 7 0 5 最终状态:1 2 3 8 0 4 7 6 52.实现从初始状态到目标状态的转换（如不能实现，程序应输出不能实现的提示信息）；3.输出结果，每移动一步都必须在屏幕上显示:ａ、移动每一步时的序号，最后一步的序号即为移动总步数；ｂ、每一步移动后以3x3表格形式显示状态。

4.要求能使移动步数尽可能少；二、程序设计1.变量说明：int num[9]; //棋盘状态int deepth; //派生的深度g(n)int diffnum; //不在位的数目h(n)int value; //耗散值f(n)=g(n)+h(n)int expand(numNode *item); //扩展节点int chu_shi_zhuang_tai[9]; //棋盘初始状态int mu_biao_zhuang_tai[9]; //棋盘目标状态int numNode_num,total_step; numNode *open,*close; //Open表和Close表2.函数声明：void print_num(int num[9]); //打印棋盘状态int print_result(numNode *item); //打印结果void init(); //初始化，获得棋盘初始状态和目标状态void swap(int *a,int *b);//交换2个数void open_insert(numNode *head,numNode *item); //向Open表中按序插入新节点void close_append(numNode *head,numNode *item); //向Close表中插入新节点3.算法分析：常用的状态空间搜索有深度优先和广度优先。

八数码问题A＊算法的实现及性能分析计算机科学与技术学院专业:计算机科学与技术161210404 杨凯迪目录一、8数码问题 (3)1.问题描述 (3)2.八数码问题形式化描述 (3)3。

解决方案 (4)二、A*算法 (4)1.A＊搜索算法一般介绍 (4)2. A*算法的伪代码 (5)3。

建立合适的启发式 (6)三、算法实现及性能比较 (7)四、算法性能分析 (8)五、结论 (9)六、参考文献 (10)附录 (10)一、8数码问题1。

问题描述八数码问题是指这样一种游戏:将分别标有数字1，2，3,…,8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。

放牌时要求不能重叠。

于是，在3×3 的数码盘上出现了一个空格。

现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态.空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如图1-1所示初始状态过渡状态最终状态图1-1 八数码问题执行过程2.八数码问题形式化描述初始状态：初始状态向量:规定向量中各分量对应的位置，各位置上的数字。

把3×3的棋盘按从左到右，从上到下的顺序写成一个一维向量。

我们可以设定初始状态:〈1，5,2，4，0，3，6，7，8>后继函数：按照某种规则移动数字得到的新向量.例如：〈1,5,2,4,0，3，6，7，8〉 〈1,0,2,4,5，3，6，7，8〉目标测试：新向量是都是目标状态。

即〈1，2，3，4,5，6,7，8，0>是目标状态?路径耗散函数：每次移动代价为1，每执行一条规则后总代价加1。

3。

解决方案该问题是一个搜索问题。

它是一种状态到另一种状态的变换。

要解决这个问题,必须先把问题转化为数字描述.由于八数码是一个3＊3的矩阵，但在算法中不实用矩阵,而是将这个矩阵转化为一个一维数组,使用这个一维数组来表示八数码，但是移动时要遵守相关规则。

广州大学学生实验报告开课学院及实验室：计算机科学与工程实验室 2020年10月14日(***报告只能为文字和图片,老师评语将添加到此处,学生请勿作答***)一、实验内容1. 分别用广度优先搜索策略、深度优先搜索策略和启发式搜索算法（至少两种）求解八数码问题；分析估价函数对启发式搜索算法的影响；探究讨论各个搜索算法的特点。

二、实验设备1. 实验设备：计算机；2. 平台：Windows操作系统，Visual C++ 6.0 / Python Anaconda三、实验步骤1. 随机生成一个八数码问题分布，设计一个可解的目标状态（要求棋盘9个位置都不同）2. 分别用广度优先搜索策略、深度优先搜索策略和至少两种启发式搜索算法求解八数码问题3. 分析估价函数对启发式搜索算法的影响4. 探究讨论各个搜索算法的特点四、分析说明（包括核心代码及解释）广度优先搜索：首先创建一个结构体node，来记录节点移动方向和扩展的节点。

struct node{int ab[3][3];//节点int direction;//方向};struct node sh[102], end;int count = 1;然后创建一个init函数来初始化棋盘起始状态和目标状态，使用for语句填写棋盘数字用loction函数确定0节点的位置，通过for语句和if语句判断sh[num].ab[i / 3][i % 3] == 0，即可得到0节点的位置Sign函数用来获取棋盘状态，将当前棋盘数字顺序生成一个数，即可得知棋盘状态。

Mobile函数用来移动0节点，先用loction函数获取0节点的位置，再通过if语句来判断0节点位置和所能移动方向，然后进行移动。

Display函数使用for语句来打印当前棋盘。

Search函数使用display函数来打印从初始状态移动到目标状态的中间状态棋盘，在while（1）语句下利用mobile函数移动0节点，直到目标状态找到或者超过寻找次数。