八数码实验报告
利用人工智能技术解决八数码游戏问题
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][zer
o
[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][zer
o
[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][zer
o
[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. 熟悉tc
2.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. 提供全部源程序及软件的可执行程序。
八数码问题求解--实验报告讲解
实验报告 一、实验问题 八数码问题求解 二、实验软件 VC6.0 编程语言或其它编程语言 三、实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 四、实验数据及步骤 （一、）实验内容 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 (a) 初始状态(b) 目标状态 图1 八数码问题示意图 （二、）基本数据结构分析和实现 1.结点状态 我采用了struct Node数据类型 typedef struct _Node{
int digit[ROW][COL]; int dist; // distance between one state and the destination一 个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置 } Node; 2.发生器函数 定义的发生器函数由以下的四种操作组成： (1)将当前状态的空格上移 Node node_up; Assign(node_up, index);//向上扩展的节点 int dist_up = MAXDISTANCE; (2)将当前状态的空格下移 Node node_down; Assign(node_down, index);//向下扩展的节点 int dist_down = MAXDISTANCE; (3)将当前状态的空格左移 Node node_left; Assign(node_left, index);//向左扩展的节点 int dist_left = MAXDISTANCE; (4)将当前状态的空格右移 Node node_right; Assign(node_right, index);//向右扩展的节点 int dist_right = MAXDISTANCE; 通过定义结点状态和发生器函数，就解决了8数码问题的隐式图的生成问题。接下来就是搜索了。 3.图的搜索策略 经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索、2.深度优先搜索、2.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。 实验时,采用了广度(宽度)优先搜索来实现。 （三、）广度(宽度)优先搜索原理 1. 状态空间盲目搜索——宽度优先搜索 其基本思想是，从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面。其搜索过程如图（1）所示。
用A算法解决八数码问题演示教学
用A算法解决八数码 问题
用A*算法解决八数码问题 一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个 棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态：任何状态都可以被指定为初始状态。 操作符：用来产生4个行动（上下左右移动）。 目标测试：用来检测状态是否能匹配上图的目标布局。 路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对 于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价 值，即 ()()()()()()**f g n sqrt dx nx dx nx dy ny dy ny =+--+--； 这样估价函数f 在g 值一定的情况下，会或多或少的受估价值h 的制 约，节点距目标点近，h 值小，f 值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。
A star算法在静态路网中的应用 2.算法伪代码 创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。 while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点) {break;} for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的估价值 ) {把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值} } if(X inCLOSE) { if( X的估价值小于CLOSE表的估价值 )
八数码问题人工智能实验报告
基于人工智能的状态空间搜索策略研究 ——八数码问题求解 （一）实验软件 TC2.0 或VC6.0编程语言或其它编程语言 （二）实验目的 1. 熟悉人工智能系统中的问题求解过程； 2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 （三）需要的预备知识 1. 熟悉TC 2.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. 提供全部源程序及软件的可执行程序。 附：实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论
C语言实现8数码问题
1、实验目的 (1)熟悉人工智能系统中的问题求解过程; (2)熟悉状态空间中的盲目搜索策略; (3)掌握盲目搜索算法,重点就是宽度优先搜索与深度优先搜索算法。 2、实验要求 用VC语言编程,采用宽度优先搜索与深度优先搜索方法,求解8数码问题 3、实验内容 (1)采用宽度优先算法,运行程序,要求输入初始状态 假设给定如下初始状态S0 2 8 3 1 6 4 7 0 5 与目标状态Sg 2 1 6 4 0 8 7 5 3 验证程序的输出结果,写出心得体会。 (2)对代码进行修改(选作),实现深度优先搜索求解该问题 提示:每次选扩展节点时,从数组的最后一个生成的节点开始找,找一个没有被扩展的节点。这样也需要对节点添加一个就是否被扩展过的标志。 4 源代码及实验结果截图 #include
//八数码状态对应的节点结构体 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;
A星算法求八数码问题试验报告
人工智能实验报告实验名称：八数码问题 姓名：xx 学号：2012210xx xx计算机学院
2014年1月14日 一．实验目的． 的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一掌握A* 个状态转为另状态的路径。 二．实验内容且要求在有限步的操作内，使其转化为目标状态，给定九宫 格的初始状态，并打印出求解路径。例如(即移动的步数最少)所得到的解是代 价最小解 3 8 2 4 6 1 5 0 7 3 2 8 4 6 1 5 0 7 A*三、算法思想：1、思想：估价值与实际A*算法是一种静态路网中求 解最短路最有效的直接搜索方法。值越接近，估价函数取得就越好、原理：2 f(n)=g(n)+h(n), 估价函数公式表示为：是在状态空g(n) 是从初始点经由节点n到目标点的估价函数，其中 f(n) 到目标节点最佳路径的估计nh(n) 是从间中从初始节点到n节点的实际代价，h(n)的选取：代价。保证找到最短路径（最优解的）条件，关键在于估价函数到目标节点的距离实际值，这种情况下，搜索的点数多，搜索估价值h(n)<= n等于h(n)范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计如
果估那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。最短距离， ,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。价值>实际值 四、算法流程：
1、使用了CreateChild（）函数，求得了任意未拓展九宫格的扩展结点，便于拓展子空间，搜索所有情况。 关键代码： bool CreateChild(NOExtend ns[],NOExtend ne){
八数码问题C语言A星算法详细实验报告含代码
一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： [ (a) 初始状态 (b) 目标状态 图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)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下： & 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。 2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。 3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。 4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。 5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 四、程序框图
八数码问题C语言A星算法详细实验报告含代码
八数码问题C语言A星算法详细实验报告含代 码 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
一、实验内容和要求 八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。 例如： (a) 初始状态 (b) 目标状态 图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)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 *算法的步骤 A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下： 1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。
启发式搜索算法解决八数码问题(C语言)
1、程序源代码 #include
A星算法求八数码问题实验报告
人工智能实验报告 实验名称：八数码问题 姓名：xx 学号：2012210xx xx计算机学院 2014年1月14日
一．实验目的 掌握A*的思想，启发式搜索，来求解在代价最小的情况下将九宫格从一个状态转为另状态的路径。 二．实验内容 给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)并打印出求解路径。例如 2 8 3 1 6 4 7 0 5 2 8 3 1 6 4 7 0 5 三、A*算法思想： 1、思想： A*算法是一种静态路网中求解最短路最有效的直接搜索方法。估价值与实际值越接近，估价函数取得就越好 2、原理： 估价函数公式表示为： f(n)=g(n)+h(n), 其中 f(n) 是从初始点经由节点n到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n) 是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。并且如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行此时的搜索效率是最高的。如果估价值>实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
四、算法流程： 是 是，输出路径 否，生成n 的所有子状态 Heuristic_Search(启发式搜索) While （未拓展表不为空？） 从未拓展表中删除第一个状态n N 为目标状态？ Case:此子状态 不在拓展表和 未拓展表中 Case:此子状态在未拓展表中 Case:此子状态在拓展表 计算该子状态的估价函数值； 记录比已有的路径更短 的路径 记录比已有的路径更短的路径 返回
用盲目搜索技术解决八数码问题
. 用盲目搜索技术解决八数码问题 题目 在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上 标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 算法流程 使用宽度优先搜索 从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜 索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面， 后进入的节点排在后面。 宽度优先算法如下： 把初始结点S0放入OPEN表中 若OPEN表为空，则搜索失败，问题无解 取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n 若目标结点，则搜索成功，问题有解N?Sg若N无子结点，则转2 扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转2 源程序 #include
using namespace std; const int ROW = 3;//行数 const int COL = 3;//列数 const int MAXDISTANCE = 10000;//最多可以有的表的数目const int MAXNUM = 10000; typedef struct _Node{ int digit[ROW][COL]; int dist;//distance between one state and the destination 一个表和目的表的距离 int dep; // the depth of node深度 // So the comment function = dist + dep.估价函数值 int index; // point to the location of parent父节点的位置} Node; Node src, dest;// 父节表目的表 vector
八数码问题实验报告讲解
《八数码问题》实验报告 一、实验目的： 熟练掌握启发式搜索A *算法。 二、实验内容： 使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题A *算法，采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 三、实验原理： 1. 问题描述： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 原理描述： 启发式搜索 （1）原理 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 （2）估价函数
计算一个节点的估价函数，可以分成两个部分： 1、 已经付出的代价（起始节点到当前节点）； 2、 将要付出的代价（当前节点到目标节点）。 节点n 的估价函数)(n f 定义为从初始节点、经过n 、到达目标节点的路径的最小代价 的估计值，即)(* n f = )(* n g + )(* n h 。 )(*n g 是从初始节点到达当前节点n 的实际代价； )(*n h 是从节点n 到目标节点的最佳路径的估计代价。 )(*n g 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，)(*n h 的比重越大， 表示启发性能就越强。 （3）算法描述： ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。 （3）算法流程图：
启发式搜索 八数码问题
启发式搜索 1. 介绍 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。 要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 2. 使用启发式搜索算法求解8数码问题。 1) A ，A 星算法采用估价函数 ()()()()w n f n d n p n ??=+??? ， 其中：()d n 是搜索树中结点n 的深度；()w n 为结点n 的数据库中错放的棋子个数；()p n 为结点n 的数据库中每个棋子与其目标位置之间的距离总和。 2) 宽度搜索采用f(i)为i 的深度，深度搜索采用f(i)为i 的深度的倒数。 3. 算法流程 ① 把起始节点S 放到OPEN 表中，并计算节点S 的)(S f ； ② 如果OPEN 是空表，则失败退出，无解； ③ 从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中有一个 为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ； ④ 把节点i 从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中； ⑤ 如果i 是个目标节点，则成功退出，求得一个解； ⑥ 扩展节点i ，生成其全部后继节点。对于i 的每一个后继节点j ： 计算)(j f ；如果j 既不在OPEN 表中，又不在CLOCED 表中，则用估价函数f 把 它添入OPEN 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在OPEN 表或CLOSED 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，则 (I)以此新值取代旧值。 (II)从j 指向i ，而不是指向他的父节点。 (III)如果节点j 在CLOSED 表中，则把它移回OPEN 表中。 ⑦ 转向②，即GOTO ②。
15数码问题的解决算法算法和具体代码
〈〈人工智能〉〉 题目：15数码问题 实验1： 要求： 采用广度优先算法解决15数码问题，输出扩展结点，步数和最终结果 算法描述： 广度优先搜索,即BFS(Breadth First Search),常常深度优先并列提及。这是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的近邻加入搜索队列（而深度优先搜索则是栈），循环搜索过程直到队列为空。 广度优先搜索算法的基本思想：从初始状态出发，按照给定的结点产生式规则（算符、结点扩展规则）生产第一层结点，每生成一个结点就检查是不是目标结点，如果是目标结点就搜索结束，如果不是目标结点并且前面没出现过就保存该结点（入队列）；再用产生式规则将所有第一层的结点依次扩展，得到第二层结点，同时检查是否为目标结点，是目标搜索停止，不是并且没出现过保存（入队）；再把第二层的结点按产生规则扩展生产第三层结点，直至找到目标或所有的状态找完但找不到目标（队列空）。 特点：先生成深度为1的所有结点，再生产深度为2的所有结点，依次类推。先横向，再纵向。这种方法找到目标，需要的步数一定最少。
程序算法流程图： 描述： (1).把起始结点放到OPEN表中。 (2).如果OPEN表是个空表，则没有解，失败退出；否则继续。 (3).把第一个结点从OPEN表中移出，并把它放入CLOSE表的扩展节点表 中。 (4).扩展结点N。如果没有后继结点，则转向步骤（2）。 (5).把N的所有后继结点放到OPEN表的末端，并提供从这些后继结点回 到N的指针。 (6).如果N的任意个后继结点是个目标结点，则找到一个解答，成功退出； 否则转向步骤（2）. 流程图：
八数码问题报告
八数码问题分析 班级：计算机1041 学号：01 姓名：李守先 2013年9月26日
摘要 八数码问题（Eight-puzzle Problem ）是人工智能中一个很典型的智力问题。 本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Java 算法与实现的思想, 分析了A*算法的可采纳性等及系统的特点。 关键词 九宫重排, 状态空间, 启发式搜索, A*算法 1 引言 九宫重排问题（即八数码问题）是人工智能当中有名的难题之一。问题是在3×3方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。状态转换的规则：空格周围的数移向空格,我们可以看作是空格移动,它最多可以有４个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。 图1 许多学者对该问题进行了有益的探索[1,2,4,6]。给定初始状态,9个数在3×3中的放法共有９！＝362880种,其状态空间是相当大的。因此, 有必要考虑与问题相关的启发性信息来指导搜索,以提高搜索的效率。当然,还有个很重要的问题：每个初始状态都存在解路径吗？文献给出了九宫重排问题是否有解的判别方法：九宫重排问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义把三行数展开排成一行,并且丢弃数字 0 不计入其中,ηi 是第 i 个数之前比该数小的数字的个数,则 η=Σηi 是该状态的逆序数,图2说明了逆序数计算的过程 。 本文介绍用JAVA 编写九宫重排问题游戏。游戏规则是,可随机产生或由用户设置初始状态,由初始状态出发,不断地在空格上下左右的数码移至空格,若能排出目标状态,则成功。为了避免对无解节点进行无用搜索,首先对初始节点进行逆序数分析,对有解的节点进行搜索,从而节省了资源,也提高了效率。本文内容安排: 第2部分介绍几个相关的概念和A*算法以及可采纳性 ;
采用A算法解决八数码问题
人工智能实验一报告题目：采用A*算法解决八数码问题 姓名： XXX 学号： 10S003028 专业：计算机科学与技术 提交日期： 2011-05-04
目录 1问题描述........................................................................................................................... - 2 - 1.1待解决问题的解释............................................................................................... - 2 - 1.2问题的搜索形式描述............................................................................................ - 2 - 1.3解决方案介绍（原理）........................................................................................ - 3 - 2算法介绍........................................................................................................................... - 4 - 2.1A*搜索算法一般介绍............................................................................................ - 4 - 2.2 算法伪代码........................................................................................................... - 4 - 3算法实现........................................................................................................................... - 5 - 3.1 实验环境与问题规模........................................................................................... - 5 - 3.2 数据结构............................................................................................................... - 5 - 3.3 实验结果............................................................................................................... - 6 - 3.4系统中间及最终输出结果.................................................................................... - 6 - 4参考文献........................................................................................................................... - 7 - 5附录—源代码及其注释................................................................................................... - 7 -
八数码实验报告
利用人工智能技术解决八数码游戏问题 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)步。 流程图： 性质： 当问题有解时，一定能找到解。 当问题为单位消耗值，且问题有解时，一定能找到最优解。 算法与问题无关，具有通用性。 时间效率和空间效率都比较低。 深度优先搜索：
人工智能实验报告,包括八数码问题八皇后问题和tsp问题
八数码问题 （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 1、启发式搜索 由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。 启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。 （三）数据结构与算法设计 该搜索为一个搜索树。为了简化问题，搜索树节点设计如下： struct Chess//棋盘 {
int cell[N][N];//数码数组 int Value;//评估值 Direction BelockDirec;//所屏蔽方向 struct Chess * Parent;//父节点 }; int cell[N][N]; 数码数组：记录棋局数码摆放状态。 int Value; 评估值：记录与目标棋局差距的度量值。 Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。 Direction ：enum Direction{None,Up,Down,Left,Right};//方向枚举 struct Chess * Parent; 父节点：指向父亲节点。 下一步可以通过启发搜索算法构造搜索树。 1、局部搜索树样例：
人工智能十五数码实验报告
目录 1 实验概述 (2) 2 十五数码问题分析 (2) 2.1十五数码问题简介 (2) 2.2可行性分析 (3) 3问题的求解策略 (3) 3.1算法分析 (3) 3.2 A*算法设计 (4) 4 实验总结 (5) 4.1 实验可视化界面 (5) 4.2个人体会 (6) 4.3 详细代码： (7)
1 实验概述 十五数码问题来源于美国的科学魔术大师萨姆.洛伊德（Sam I.oyd）在1978年推出的著名的“14-15”智力玩具。这个游戏曾经风靡欧美大陆" 。洛伊德的发明其实只是将重排九宫（即八数码问题）中的3阶方阵扩大到4 阶方阵罢了。由于这个细微的变化，十五数码问题的规模远远大于八数码问题，八数码问题的规模较小，总的状态数为9！（=362880）个，而十五数码问题的状态,数为16！（）个。故十五数码问题更能评价一个算法的“智能”水平。 2 十五数码问题分析 2.1十五数码问题简介 15数码问题又叫移棋盘问题，是人工智能中的一个经典问题。所谓的15数码问题：就是在一个4×4的16宫格棋盘上，摆放有15个将牌，每一个将牌都刻有1～15中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种求解的问题是：给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码，实现从初始状态到目标状态的转变，如下图所示。问题的实质就是寻找一个合法的动作序列
2.2可行性分析 十五数码问题存在无解的情况,当遍历完所有可扩展的状态也没有搜索到目标状态就判断为无解。可以根据状态的逆序数来先验的判断是否有解,当初始状态的逆序数和目标状态的逆序数的奇偶性相同时,问题有解；否则问题无解。状态的逆序数是定义如下：把四行数展开排成一行,并且丢弃数字0 不计入其中,ηi是第i 个数之前比该数小的数字的个数,则η=Σηi 是该状态的逆序数,例如：对于初始状态：5、1、2、4、9、6、3、8、13、15、10、11、14、7、12.其η=0+0+1+2+4+4+2+6+8+9+8+9+11+6+11=81；对于目标状态：1、2、3、4、5、6、7、8、9、10、11、12、13、14、15，其η=0+1+2+3+4+5+6+7+8+9+10+11+12+13+14=105。初始状态和目标状态的奇偶性相同，故存在解路径。 3问题的求解策略 3.1算法分析 十五数码问题的解空间树属排列树，用于排列树搜索的方法主要有两大类：一类是盲目搜索，如深度优先搜索DFS 和广度优先搜索BFS；另一类是启发式搜索，如A* 算法。 对于十五数码问题，深度优先搜索的状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。应用此策略很可能得不到解。宽度优先搜索的优势在于当问题有解时，一定能找到解，且能找到最优解。但其搜索时需要保存所有的待扩展结点，这样很容易扩展那些没有用的结点，造成状态的指数增长，甚至“组合爆炸”。这对宽度优先搜索很不利。这两种搜索方法的共同缺点是结点排序杂乱无章，往往在搜索了大量无关结点后才能得到目的结点，只适合于复杂度较低的问题的求解。 启发式搜索利用特定问题自身所携带的启发信息在一定程度上避免了盲目搜索的不足，适合于解决十五数码问题。其核心思想是引入一个启发式函数（或称为评估函数）利用评估函数为生成的结点估值%并按估值的大小对结点进行排