八数码实验报告

利用人工智能技术解决八数码游戏问题 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表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到open表末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。

流程图： 性质：

当问题有解时，一定能找到解。 当问题为单位消耗值，且问题有解时，一定能找到最优解。 算法与问题无关，具有通用性。 时间效率和空间效率都比较低。 深度优先搜索：

1、定义

在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这

种盲目(无信息)搜索叫做深度优先搜索(depth-first search)。 2、特点

首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进

行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。 3、深度界限 为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。

4、深度优先搜索算法

(1) 把起始节点放到open表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从open表移出，并把它放入closed的扩展节点表中。 (4) 考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出 （5）如果没有后继节点，则转向上述第(2)步。 (6) 扩展节点n，把n的所有后继节点放到open表前端，并提供从这些后继节点回到n

的指针。转向第(2)步。

流程图： 性质：

一般不能保证找到最优解。 当深度限制不合理时，可能找不到解。 最坏情况时，搜索空间等同于穷举。 4．八数码游戏问题的启发式搜索技术 （给出你所采用估价函数，并介绍算法的基本原理和流程图） 估价函数:

f(n) = g(n) + h(n)是对下列函数的一种估计或近似： f*(n) = g*(n) + h*(n) f*(n)：从初始节点到节点n的一条最佳路径的实际代价加上从节点n到目标节点的最佳路径的代价之和。

g*(n)：从初始节点到节点n之间最小路径的实际代价 h*(n)：从节点n到目标节点的最小代价路径上代价 定义

利用与问题有关的知识（即：启发信息）来引导搜索，达到减少搜索范围，降低问题复

杂度的搜索过程称为启发式搜索方法。 核心问题：

启发信息应用，启发能力度量和如何获得启发信息。 启发信息的强度

强：降低搜索工作量，但可能导致找不到最优解。 弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。 全局最佳优先搜索 ：

(1) 把起始节点放到open表中，并计算估价函数f(s0)。 (2) 如果open是个空表，则没有解，失败退出；否则继续。 (3) 把open表中的第一个节点（股价函数最小的节点n），移入closed表。

(4) 如果n是目标节点，问题得解，退出。否则继续。 (5) 判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。 (6) 对节点n进行扩展，并对其所有后继节点计算估价函数f（n）的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入open表，然后对open表中的全部节点

按照估价函数值从小到大的顺序排序。 (7) 转向第(2)步。

流程图： 5．例子及分析

双向宽度优先搜索： 深度优先搜索： 启发式搜索：篇二：人工智能实验报告 八数码问题 实验一 启发式搜索算法 姓名：徐维坚 学号：2220103484 日期：2012/6/29 一、实验目的：

熟练掌握启发式搜索a?算法及其可采纳性。 二、实验内容：

使用启发式搜索算法求解8数码问题。 1) 编制程序实现求解8数码问题a?算法，采用估价函数 ??w?n?， f?n??d?n?????p?n? 其中：d?n?是搜索树中结点n的深度；w?n?为结点n的数据库中错放的棋子个数；p?n?

为结点n的数据库中每个棋子与其目标位置之间的距离总和。 2) 分析上述⑴中两种估价函数求解8数码问题的效率差别，给出一个是p?n?的上界 的

h?n?的定义，并测试使用该估价函数是否使算法失去可采纳性。 三、实验原理： 1. 问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格

相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状

态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初

始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述：

2.1 有序搜索算法： （1）原理： 在搜索过程中，open表中节点按照其估价函数值以递增顺序排列，选择open表中具有

最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。 在本例中，估价函数中的g(n)取节点深度d(n)，h(n)为节点n的状态与目标状态之间错

放的个数，即函数?(n)。 （2）算法描述：

① 把起始节点s放到open表中，并计算节点s的f(s)； ② 如果open是空表，则失败退出，无解； ③ 从open表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个 为

目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i；

④ 把节点i从 open 表中移出，并把它放入 closed 的已扩展节点表中； ⑤ 如果i是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： 计算f(j)；如果j 既不在open表中，又不在cloced表中，则用估价函数f把 它添入open表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解答路径；如果j已在open表或closed表中，则比较刚刚对j计算过的f和前面计算过的该节点在表

中的f值。如果新的f较小，则 (i)以此新值取代旧值。

(ii)从j指向i，而不是指向他的父节点。 (iii)如果节点j在closed表中，则把它移回open表中。 ⑦ 转向②，即goto②。

（3）算法流程图： 2.2启发式搜索技术

（1）原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发

式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 （2）估价函数

计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n的估价函数f(n)定义为从初始节点、经过n、到达目标节点的路径的最小代价的

估计值，即f*(n) = g*(n)+ h*(n)。 g*(n)是从初始节点到达当前节点n的实际代价； h*(n)是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。 g*(n)所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h*(n)的比重越大，表示启发性能就越强。 本实验中我们使用函数p(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然p(n)比?(n)

更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离。 （3）算法描述：

参考有序搜索算法描述，基本相同。流程图亦参考有序算法流程图。 四、实验程序及其说明：

1）int goal[n][n]，struct chessboard： 试验中我定义goal数组为目标状态——{1,2,3,8,0,4,7,6,5}。结构体chessboard记录棋盘信息，其中变量pos数组坐标记录每个数码a的位置，其值为数码a。d表示该棋盘的深度，f为启发函数值，move为父节点移动到该节点的方式，以便在输出时告诉用户该如何移

动棋子知道目标状态。 2）struct lnode： 定义节点lnode结构体，存放该节点状态时的棋盘信息board，和指向父节点、下一节点的指针(*parent,*next)，以及标记量flag——值为true时表示该节点是最佳路径上的节点。

3）int* findzero(lnode* &node)：

为方便找到空格，我设计了找到该函数findzero(*&node)，以便找到当前节点空格

所在位置以利于接下来的程序执行。返回值为空格所在的行和列。 4）int wrong(lnode *node)和int pick(lnode *node)： 分别为函数?(n)和p(n)。

5）lnode* extend(lnode *node,int depth,int zero[2],int moveflag,int choose) 树形方式扩展节点。node为要扩展的当前节点，depth为当前深度，zero存放该节点空

格位置信息，moveflag即扩展节点的移动方式，choose为选择函数?(n)还是p(n)。 6）void initlist(lnode* &open,lnode* &close)和int listinsert(list

&l,lnode* newnode)

分别为表open、close的创建和表的插入操作。 7）lnode* getminf(list &l) 主要是实现从open表中选择一个f值最小的节点i。如果有几个节点值相同，当其中 有

一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i。 五、实验小结

通过本次试验，我对启发式搜索有了更加深入的了解。 在实验中，通过对两种启发式搜索所扩在的节点数来看，p(n)看来比?(n)更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数h*(n)来说，它的定义趋向多元化，p(n)只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋

问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。 在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在closed表中，利用标志flag，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指

针path来找到路径，这样节省了存储空间，更利于搜索。 通过实验结果来看，这两个函数都是可采纳的，尽管?(n)存在不必要的扩展。 六、实验代码及输出结果 1. 源代码：

#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define overflow 1 #define n 3

int goal[n][n]={1,2,3,8,0,4,7,6,5}; int zero[2],nodeqty=0;

int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列 typedef int piece;

struct chessboard{//棋盘信息 };

struct lnode{ };

typedef lnode* list;

int* findzero(lnode* &node) { chessboard board; lnode *parent,*next; bool flag; piece pos[n][n];//记录每个数码a的位置r行c列 int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该

节点的方式 } int i,j,zr[2]; int *z=zr; for(i=0;i<n;i++){ } return z;

for(j=0;j<n;j++){ } if(node->board.pos[i][j]==0){ } zr[0]=i+1; zr[1]=j+1; break;

int wrong(lnode *node) { }

int pick(lnode *node) { int w=0,i,j,ii,jj; for(i=0;i<n;i++){ for(j=0;j<n;j++){ if(node->board.pos[i][

j]!=goal[i][j]&&node->board.pos[i][j]!=0){ for(ii=0;ii<n;ii++) for(jj=0;jj<n;jj++)

if(node->board.pos[i][j]==goal[ii][jj]){ w=w+abs(ii-i)+abs(jj-j); break; int w=0,i,j; for(i=0;i<n;i++){ } return w; for(j=0;j<n;j++){ } if(node->board.pos[i][j]!=goal[i][j]&&node->board.pos[i][j]!=0)

w++;篇三：八数码实验报告53 华 中 师 范 大 学 计 算 机 学 院 实 验 报 告 书 实验题目 ：

八数码问题求解 课程名称 ： 人工智能 主讲教师 ： 金聪 班 级 ： 试验时间 ： 1.问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格

相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状

态的移动棋子步数最少的移动步骤。 2.初始状态 1 0 3 7 2 4 6 8 5 3.目标状态 1 2 3, 8 0 4, 7 6 5 4.搜索策略 启发式搜索技术

（1） 原理：启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估， 得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

（2） 估价函数

计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n的估价函数f(n)定义为从初始节点、经过n、到达目标节点的路径的最小代价的

估计值，即f(n) = g(n)+ h(n)。 *** g*(n)是从初始节点到达当前节点n的实际代价； 体现出搜索过程中采用的启发式信h*(n)是从节点n到目标节点的最佳路径的估计代价，

息（背景知识），称之为启发函数。 g*(n)所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h*(n)的比重越大，表示启发性能就越强。 本实验中我们使用函数p(n)，其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然p(n)比?(n)

更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离。 5.算法 begin：

读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； if(问题可解)

把初始状态假如open表中； while（未找到解&&状态表非空） ①在open表中找到评价值最小的节点，作为当前结点； ②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③； ③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结

点的评价值f并记录其父节点； ④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中； ⑤把

当前结点从open表中移除； end while end if 输出结果； end

6.源代码

#include<stdio.h> #include<malloc.h> #include<stdlib.h> #define overflow 1 #define n 3

int goal[n][n]={1,2,3,8,0,4,7,6,5}; int zero[2],nodeqty=0;

int *z=zero;//记录0的位置，zero[0]:r行；zero[1]:c列 typedef int piece;

struct chessboard{//棋盘信息 piece pos[n][n];//记录每个数码a的位置r行c列 int d,f,move;//d:深度；f:启发函数值 ；move:父节点移动到该节点的方式 }; struct lnode{ chessboard board; lnode *parent,*next; bool flag; };

typedef lnode* list;

int* findzero(lnode* &node) {

int i,j,zr[2]; int *z=zr;

for(i=0;i<n;i++){ for(j=0;j<n;j++){

if(node->board.pos[i][j]==0){ zr[0]=i+1; zr[1]=j+1; break; }

} }

return z;

} int pick(lnode *node) {

int w=0,i,j,ii,jj; for(i=0;i<n;i++){ for(j=0;j<n;j++){

if(node->board.pos[i][j]!=goal[i][j]&&node->board.pos[i][j]!=0){

for(ii=0;ii<n;ii++) for(jj=0;jj<n;jj++)

if(node->board.pos[i][j]==goal[ii][jj]){ w=w+abs(ii-i)+abs(jj-j); break; } } } }

return w; }

lnode* extend(lnode *node,int depth,int zero[2],int moveflag,int choose) { lnode* newnode=new lnode; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ newnode->board.pos[i][j]=node->board.pos[i][j]; } }

switch(moveflag) {

case 1: //向左移，不能出界：zero[1]>=2

newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]-1][zero

[1]-2];

newnode->board.pos[zero[0]-1][zero[1]-2]=0; break;

case 2: //向右移，不能出界：zero[1]<=2

newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]-1][zero

[1]];

newnode->board.pos[zero[0]-1][zero[1]]=0; break; case 3: //向上移，不能出界：zero[0]>=2

newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]-2][zero

[1]-1];

newnode->board.pos[zero[0]-2][zero[1]-1]=0; break;

case 4: //向下移，不能出界：zero[0]<=2

newnode->board.pos[zero[0]-1][zero[1]-1]=newnode->board.pos[zero[0]][zero[1]-1];

newnode->board.pos[zero[0]][zero[1]-1]=0; break; }

newnode->board.d=depth+1; switch(choose){

case 1:newnode->board.f=newnode->board.d+pick(newnode);break; } newnode->board.move=moveflag; newnode->parent=node; nodeqty++;

return newnode; }

void initlist(lnode* &open,lnode* &close) {

open=(list)malloc(sizeof(lnode)); close=(list)malloc(sizeof(lnode)); if(!open&&!close) exit(overflow); open->next=null; close->next=null; }

int listinsert(list &l,lnode* newnode) {

list p=l;

while(p->next){ p=p->next; }

newnode->next=p->next; p->next=newnode; return true; }

lnode* getminf(list &l) {篇四：人工智能大作业八数码问题 基于a星算法的八数码问题求解 学号： 姓名： 摘要：在人工智能领域中, 八数码问题一直都是一个游戏难题。介绍了八数码问题, 然后在启发式搜 索算法上对a * 算法定义进行了解释, 并在其旨在提高搜索效率的方面作了比较详尽的介绍,

详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法： a* 算法。再依据这种

算法用可视化编程语言vc+ + 6. 0 来实现八数码问题的求解过程, 取得了预期的搜索解, 提

高了搜索效率。

关键词：八数码问题; 启发式搜索; a* 算法 本组成员： 本人分工：主要负责进行问题分析，提出解决方案，进行系统设计，算法上具体负责主

函数的编写。 1 引言

八数码问题是人工智能的一个经典的问题。文中通过设计一个基于a* 算法的状态空间搜索程

序, 对于给定的初始状态, 采用h ( n ) = p ( n ) 表示以每一个将牌与目标位置之间距离的总和

作为启发函数的度量, 并用可视化编程语言vc+ + 来实现该问题。 2 算法原理与系统设计 1）a*算法思想 a*算法是对a算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法。a*

算法对a算法中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0； 第二，h(n)是最小代价h*(n)的下界，即对任意节点n 均有h(n)≤h*(n)。即满足上述两条限制的a算

法称为a*算法。 2）估价函数 用来估算节点希望程度的量度，叫估价函数f(x)，f(x)=g(x)+h(x)。g(x)为从初始节点到当前节点 已经付出的代价，h(x)为从当前节点到目标节点的最优路径的估计代价。本算法中令g(x)为当前节点

的深度depth，h(x)为当前节点每个数字位与目标节点数字位间距离和dist，进一步考虑当前结点与 目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距

离和（不考虑中 间路径），满足h ( n ) <= h * ( n )， 且对于目标节点有 h ( t ) = 0，对于结

点m和n （n 是m的子结点） 有h ( m ) – h ( n ) <= 1满足单调限制条件。 3）open和closed表的数据结构表示 对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点。closed表存储已扩展的结点间的扩展关系，主要用于输出路径。closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱点的下标位置，可以用数组实现。每个结点记录８数码格局和它的前驱结点的下标。 4）问题分析

首先，八数码问题包括一个初始状态(src) 和 目标状态(dest)，所谓解八数码 问题就是在两个状态间寻找一系列可过渡状态。这个状态是否存在就是我们要解决的第

一个问题。 解决八数码问题，主要面临的问题有： q1）开始状态s到目标状态d是否可解； q2）扩展节点的选择；

q3）扩展待扩展节点，该节点是否已扩展过； q4）判断是否已达目标节点d； 问题q 1）通过逆序数的奇数偶数来判断。因为在空白移动过程中，数码的逆序数不改变。左右移动，数码序列不变。上下移动，数码序列中某个数字则移动了两位。问题的实质就是：如果是n*n的数码盘的话，左右移动，数码序列不变；上下移动则数码序列变动n-1位。若n为奇数则在变动过程中其逆序数不会改变。而八数码问题为3*3矩阵，3为奇数，故逆序数不作改变。故可通过判断当前状态s的逆序数以及目标状态sd的数字序列的逆序数

的奇偶性是否相同来判断该问题是否可解。 问题q2）扩展节点的选择通过getmin函数，根据估价函数f来获得代价最小的节点。 问题q3）扩展节点即为上下左右四个方向移动空格到没有扩展过的节点中去，要判断是

否扩展过，只要跟之前的状态做比较即可。 问题q4）是否达到目标节点，将当前节点和目标节点进行比较。 算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程） 输入：初始状态，目标状态 输出：从初始状态到目标状态的一系列过程 算法描述：

begin： 读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； if(问题可解) 把初始状态假如open表中； while（未找到解

&&状态表非空） ①在open表中找到评价值最小的节点，作为当前结点； ②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③； ③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点， 并计算新扩展结点的评价值f并记录其父节点； ④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中； ⑤把当前结点从open表中移除；

end while end if 输出结果； end

算法流程如下： 3 系统实现 （2）a*算法搜索开始，设置while循环，直到找到目标状态或者open表为空或者无解

的情况下结束。 （3）不同的八数码初始状态和目标状态不一定有解，所以要根据两种状态下的奇偶性是

否一致来判断（详见实验思想的问题分析）。 篇五：c语言解八数码问题之人工智能实验报告 人工智能》上机实验 《 基于人工智能的状态空间搜索策略研究 ——八数码问题求解 （一）实验软件

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

求解及编程语言的应用。 （三）需要的预备知识 1. 熟悉tc2.0 或 vc6.0 编程语言或者其它编程语言； 2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法； 3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用； 4. 熟悉计算机常用人机接口设计。 （四）实验数据及步骤 1. 实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操

作使得棋盘从初始状态到目标状态。 图1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（a 算法或 a* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。 2. 实验步骤

（1）分析算法基本原理和基本流程； 程序采用宽度优先搜索算法，基本流程如下： （2）确定对问题描述的基本数据结构，如 open 表和 closed 表等； （3）编写算符运算、目标比较等函数； （4）编写输入、输出接口； （5）全部模块联调；

（6）撰写实验报告。 （五）实验报告要求 所撰写的实验报告必须包含以下内容： 1. 算法基本原理和流程框图； 2. 基本数据结构分析和实现； 3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出

参数意义和与其它模块联系等； 4. 程序运行结果，含使用的搜索算法及搜索路径等； 5. 实验结果分析； 6. 结论；

7. 提供全部源程序及软件的可执行程序。

本文来源：https://www.bwwdw.com/article/oz5w.html