“八”数码问题的宽度优先搜索与深度优先搜索

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

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==八数码实验报告篇一：八数码实验报告利用人工智能技术解决八数码游戏问题1．八数码游戏问题简介九宫排字问题（又称八数码问题）是人工智能当中有名的难题之一。

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

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

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

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

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

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

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

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

八数码问题启发函数和代价函数八数码问题作为经典的搜索问题，其解决过程中启发函数和代价函数的选择对搜索效率有着重要的影响。

本文将针对八数码问题中启发函数和代价函数的选择进行探讨，并分析它们在搜索过程中的作用和影响。

一、启发函数的选择启发函数是在搜索过程中用来评估节点的“接近程度”的函数，它可以指导搜索算法朝着离目标更近的方向前进，从而提高搜索效率。

在八数码问题中，常用的启发函数有误放置数目、曼哈顿距离和线性冲突等。

1. 误放置数目误放置数目是指当前状态与目标状态中不同数字的个数，它可以作为启发函数来评估当前状态与目标状态的“距离”。

当误放置数目越小，说明当前状态距离目标状态越近，因此误放置数目可以作为一种简单而有效的启发函数。

2. 曼哈顿距离曼哈顿距离是指当前状态的每个数字到目标状态的正确位置之间的曼哈顿距离之和。

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

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

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

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

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

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

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

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

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

八数码问题实验报告八数码问题实验报告引言：八数码问题是一种经典的数学难题，在计算机科学领域有着广泛的研究和应用。

本实验旨在通过探索八数码问题的解法，深入理解该问题的本质，并通过实验结果评估不同算法的效率和准确性。

一、问题描述：八数码问题是一个在3×3的棋盘上，由1至8的数字和一个空格组成的拼图问题。

目标是通过移动棋盘上的数字，使得棋盘上的数字排列按照从小到大的顺序排列，最终形成如下的目标状态：1 2 34 5 67 8二、解法探索：1. 深度优先搜索算法：深度优先搜索算法是一种经典的解决拼图问题的方法。

该算法通过不断尝试所有可能的移动方式，直到找到目标状态或者无法再继续移动为止。

实验结果显示，该算法在八数码问题中能够找到解，但由于搜索空间庞大，算法的时间复杂度较高。

2. 广度优先搜索算法：广度优先搜索算法是另一种常用的解决八数码问题的方法。

该算法通过逐层扩展搜索树，从初始状态开始，逐步扩展所有可能的状态，直到找到目标状态。

实验结果显示，该算法能够找到最短路径的解，但同样面临搜索空间庞大的问题。

3. A*算法：A*算法是一种启发式搜索算法，结合了深度优先搜索和广度优先搜索的优点。

该算法通过使用一个估价函数来评估每个搜索状态的优劣，并选择最有希望的状态进行扩展。

实验结果显示，A*算法在八数码问题中表现出色，能够高效地找到最优解。

三、实验结果与分析：通过对深度优先搜索、广度优先搜索和A*算法的实验，得出以下结论：1. 深度优先搜索算法虽然能够找到解，但由于搜索空间庞大，时间复杂度较高，不适用于大规模的八数码问题。

2. 广度优先搜索算法能够找到最短路径的解，但同样面临搜索空间庞大的问题，对于大规模问题效率较低。

3. A*算法在八数码问题中表现出色，通过合理的估价函数能够高效地找到最优解，对于大规模问题具有较好的效果。

四、结论与展望：本实验通过对八数码问题的解法探索，深入理解了该问题的本质，并评估了不同算法的效率和准确性。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

它的目标是将一个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.将初始状态加入队列和哈希表中。

人工智能实验报告一.八数码问题及分析：八数码问题也称为九宫问题。

在3×3的棋盘，摆有八个数码，分别为1至8的某一数字，数字各不相同。

棋盘上还有一个空格，与空格相邻的数码可以移到空格中。

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

其中，问题的一个状态就是数码在棋盘上的一种摆法。

数码移动后，状态就会发生改变。

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

八数码问题一般使用搜索法来解。

搜索法有广度优先搜索法、深度优先搜索法、A*算法等。

本次试验采用局部择优A算法（即启发函数的有界深度搜索算法）。

二.实验说明：因为在学生社团工作，中间一段时间一直不能够和大家一起准备本次实验，也不好意思拖延大家的进度，于是，我选在工作之后自己一个人做本次试验，但因为技术方面的不够成熟，实际上我查找了许多资料，同时向学长请教用C++builder实现了局部最优的算法。

在算法分析中主要比较讨论了广度优先算法和A*算法，也是由A*算法得到的灵感利用启发函数，但最终的搜索却选择了有界深度的方式。

这是因为八数码问题相对简单，利用有界能够很好的控制算法的中止。

.软件环境：Borland C++ Builder 6三.数据结构设计1．用二唯数组定义棋子的变换（空格的左移、右移、上移、下移）2．定义权值3．定义指向父亲和孩子的指针。

程序如下（Tlist.h）:#ifndef KTListH#define KTListH//节点模板类(如KTNode<int>* Paths; 使用)template <class DATATYPE>class KTNode{public:DATATYPE Data; //可变数据类型的节点数据int Weight; //排序用的权重KTNode* Next; //指向下一个节点的指针KTNode* Prior; //指向上一个节点的指针KTNode(){Weight = 0;}//拷贝构造函数KTNode(KTNode& S){Data=S.Data;Weight=S.Weight;Next=S.Next;Prior=S.Prior;}KTNode operator=(KTNode S) //重载运算符，使两个KTNode对象能相互赋值{Data=S.Data;Weight=S.Weight;Next=S.Next;Prior=S.Prior;return *this; //调用拷贝构造函数}};四.算法分析：I）广度优先搜索法1.广度优先搜索算法的基本步骤1）建立一个队列，将初始结点入队，并设置队列头和尾指针2）取出队列头（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列。

第五章搜索策略习题参考解答5.1 练习题5.1 什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？5.2 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最优解？最优解唯一吗？5.3 请写出状态空间图的一般搜索过程。

在搜索过程中OPEN表和CLOSE表的作用分别是什么？有何区别？5.4 什么是盲目搜索？主要有几种盲目搜索策略？5.5 宽度优先搜索与深度优先搜索有何不同？在何种情况下，宽度优先搜索优于深度优先搜索？在何种情况下，深度优先搜索优于宽度优先搜索？5.6 用深度优先搜索和宽度优先搜索分别求图5.10所示的迷宫出路。

图5.10 习题5.6的图5.7 修道士和野人问题。

设有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到河的右岸去。

但该船每次只能装载两个人，在任何岸边野人的数目都不得超过修道士的人数，否则修道士就会被野人吃掉。

假设野人服从任何一种过河安排，请使用状态空间搜索法，规划一使全部6人安全过河的方案。

（提示：应用状态空间表示和搜索方法时，可用(N m,N c)来表示状态描述，其中N m和N c分别为传教士和野人的人数。

初始状态为(3,3)，而可能的中间状态为(0,1),(0,2),(0,3), (1,1),(2,1),(2,2),(3,0),(3,1),(3,2)等。

）5.8 用状态空间搜索法求解农夫、狐狸、鸡、小米问题。

农夫、狐狸、鸡、小米都在一条河的左岸，现在要把它们全部送到右岸去。

农夫有一条船，过河时，除农夫外，船上至多能载狐狸、鸡和小米中的一样。

狐狸要吃鸡，鸡要吃小米，除非农夫在那里。

试规划出一个确保全部安全的过河计划。

（提示：a.用四元组(农夫，狐狸，鸡，米)表示状态，其中每个元素都可为0或1，0表示在左岸，1表示在右岸；b.把每次过河的一种安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。

）5.9 设有三个大小不等的圆盘A 、B 、C 套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，初始状态S 0和目标状态S g 如图5.11所示，用宽度优先搜索法和深度优先搜索法求从S 0到S g 的路径。

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

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

例如：(a) 初始状态 (b) 目标状态图1 八数码问题示意图请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。

本实验选择宽度优先搜索：选择一个起点，以接近起始点的程度依次扩展节点，逐层搜索，再对下一层节点搜索之前，必先搜索完本层节点。

二.实验设备及软件环境Microsoft Visual C++，（简称Visual C++、MSVC、VC++或VC）微软公司的C++开发工具，具有集成开发环境，可提供编辑C语言，C++以及C++/CLI 等编程语言。

三.实验方法算法描述：（1）将起始点放到OPEN表；（2）若OPEN空，无解，失败；否则继续；（3）把第一个点从OPEN移出，放到CLOSE表；（4）拓展节点，若无后继结点，转（2）；（5）把n的所有后继结点放到OPEN末端，提供从后继结点回到n的指针；（6）若n任意后继结点是目标节点，成功，输出；否则转（2）。

流程图：代码：#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);/** Name: 主函數* Description: 程序入口*/Int main ( 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;}}四.结果：下图实验结果中，一步代表一层的搜索结果中的最优解；八数码难题的宽度优先搜索树：五.实验分析宽度优先搜索属于一种盲目搜索算法，可以系统的展开所有节点，理论上一定能达到搜寻目的。

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

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

举个简单的例⼦，“机器学习（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：双向搜索双向搜索，前后来搜，碰到头，然后一拼接就出了路径。

八数码问题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节点，直到目标状态找到或者超过寻找次数。

/*程序利用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;}。