人工智能实验报告 八数码问题
实验一 启发式搜索算法
姓名：徐维坚 学号：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 表中具有最小估价函数值的节点作为下一个待扩展的节点，这种搜索方法称为有序搜索。
在本例中，估价函数中的)(n g 取节点深度)(n d ，)(n h 为节点n 的状态与目标状态之间错放的个数，即函数)(n ω。
（2）算法描述：
① 把起始节点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）算法流程图：
2.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 的比重越大，表示启发性能就越强。
本实验中我们使用函数)(n p ，其值是节点n 与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然)(n p 比)(n ω更接近于)(*n h ，因为)(n p 不仅考虑了错位因素，还考虑了错位的距离。
（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 ω和)(n p 。
5）LNode* extend(LNode *Node,int depth,int zero[2],int moveflag,int Choose)
树形方式扩展节点。Node 为要扩展的当前节点，depth 为当前深度，zero 存放该节点空格位置信息，moveflag 即扩展节点的移动方式，Choose 为选择函数)(n ω还是)(n p 。
6）void InitList(LNode* &Open,LNode* &Close)和int ListInsert(List &L,LNode* NewNode)
分别为表OPEN 、CLOSE 的创建和表的插入操作。
7）LNode* Getminf(List &L)
主要是实现从OPEN 表中选择一个f 值最小的节点i 。如果有几个节点值相同，当其中 有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i 。
五、实验小结
通过本次试验，我对启发式搜索有了更加深入的了解。
在实验中，通过对两种启发式搜索所扩在的节点数来看，)(n p 看来比)(n ω更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。但是对于估价函数)(*n h 来说，它的定义趋向多元化，)(n p 只是它的一个比较好的特例，对一复杂的搜索问题，如国际象棋问题，他就显得较简单。所以，要更好地定义一个估价函数还有待深入讨论。
在寻找最佳扩展路径的过程中我发现，最佳扩展路基上的节点均在CLOSED 表中，利用标志flag ，以及它们之间的父子关系，我很容易的就找到了扩展路径，避免了再用一个路径指针path 来找到路径，这样节省了存储空间，更利于搜索。
通过实验结果来看，这两个函数都是可采纳的，尽管)(n ω存在不必要的扩展。
六、实验代码及输出结果
1. 源代码：
#include
#include
#include
#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 for(j=0;j if(Node->board.pos[i][j]==0){ zr[0]=i+1; zr[1]=j+1; break; } } } return z; } int Wrong(LNode *Node) { int w=0,i,j; for(i=0;i for(j=0;j if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0) w++; } } return w; } int pick(LNode *Node) { int w=0,i,j,ii,jj; for(i=0;i for(j=0;j if(Node->board.pos[i][j]!=goal[i][j]&&Node->board.pos[i][j]!=0){ for(ii=0;ii for(jj=0;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 for(int j=0;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; } NewNode->board.d=depth+1; switch(Choose){ case 1:NewNode->board.f=NewNode->board.d+Wrong(NewNode);break; case 2: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) { List p=L,q=L->next,r=L,min; min=q;//p,q寻找f最小值的指针，r指向表L中min前一个元素 if(!q) return NULL; while(q) { if(min->board.f>q->board.f){ r=p; min=q; } p=q; q=q->next; } r->next=min->next; min->next=NULL; return min; } int main() { int i,j,choose; List Open,Close; LNode *Best,*current; LNode *Start=new LNode; printf("\t\t\t八数码问题求解\n"); printf("\n请输入初始状态："); for(i=0;i for(j=0;j scanf("%d",&(Start->board.pos[i][j])); } } printf("(注:The flag of movement--1:左移;2:右移;3:上移;4:下移)\n"); printf("初始棋盘状态：\n"); for(i=0;i for(j=0;j printf("|%d",Start->board.pos[i][j]); } printf("|\n"); } InitList(Open,Close); printf("请选择(1:A算法;2:A*算法):"); scanf("%d",&choose); Start->board.d=0; switch(choose){ case 1:Start->board.f=Start->board.d+Wrong(Start);break; case 2:Start->board.f=Start->board.d+pick(Start);break; } // Start->board.f=0+Wrong(Start); Start->board.move=0; Start->parent=NULL; Start->next=NULL; Start->flag=1; ListInsert(Open,Start);//将S加入到Open表中 while(Open->next){ Best=Getminf(Open); ListInsert(Close,Best); if(!(Best->board.f-Best->board.d)){ printf("$$$******有解！******$$$\n"); break; } z=Findzero(Best); zero[0]=*(z+0);zero[1]=*(z+1); if(zero[1]>=N-1&&Best->board.move!=2) ListInsert(Open,extend(Best,Best->board.d,zero,1,choose)); if(zero[1]<=N-1&&Best->board.move!=1) ListInsert(Open,extend(Best,Best->board.d,zero,2,choose)); if(zero[0]>=N-1&&Best->board.move!=4) ListInsert(Open,extend(Best,Best->board.d,zero,3,choose)); if(zero[0]<=N-1&&Best->board.move!=3) ListInsert(Open,extend(Best,Best->board.d,zero,4,choose)); } printf("本算法搜索图中总共扩展的节点数为：%d\n",NodeQTY); printf("\t最佳路径如下所示：\n"); if(Open->next) { while(Best->parent){ Best->flag=1; Best=Best->parent; } List p=Close->next,q=Close->next; if(p==Start) q=p->next; else exit(1); int Step=0; while(p&&q)//在Close表中依标记找到路径 { if(q->flag==1&&q->parent==p){ printf("Step %d:0 move as the %d-flag of movement.\n",++Step,q->board.move); for(i=0;i for(j=0;j printf("|%d",q->board.pos[i][j]); } printf("|\n"); } p=q;//记住父节点 } q=q->next; } printf("到达目标状态！\n"); } else printf("该问题无法求解！\n"); } 2.输出结果： 2.1 A算法： 2.2 A*算法： 实验报告 一、实验问题 八数码问题求解 二、实验软件 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*算法解决八数码问题 一、 题目：八数码问题也称为九宫问题。在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. 提供全部源程序及软件的可执行程序。 附：实验报告格式 一、实验问题 二、实验目的 三、实验原理 四、程序框图 五、实验结果及分析 六、结论 人工智能实验报告实验名称：八数码问题 姓名：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){ 一、实验内容和要求 八数码问题：在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）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 四、程序框图 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 //------------------------------------------------------------------------ //添加节点函数入口，方法：通过插入排序向指定表添加 //------------------------------------------------------------------------ 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; } 学生实验报告 实验课名称：人工智能 实验名称: 八数码 专业名称：计算机科学与技术 班级： 学号： 学生姓名： 教师姓名： 2010 年10 月20日 一．实验内容 用OPEN表和CLOSED表解决搜索问题。 二．实验题目 采用启发式算法（如A*算法）求解八数码问题。 三．实验要求 1.必须使用OPEN表和CLOSED表。 2.明确给出问题描述。系统初始状态。目标状态和启发式函数。 3.除了初始状态以外，至少搜索四层。 4.给出解路径（解图）。 四．实验过程 ①问题：初始状态到目标状态是否可解如何判断？ 答：实验过程自己给出的初始状态使用A*算法求解，并不是所有的初始状态都可解到达目标状态。因为八数码问题其实是0~9的一个排列，而排列有奇排列和偶排列，从奇排列不能转化为偶排列或者相反。例如：函数f(s)表示s前比s 小的数字的数目（s 则当f(a8)+f(a7)+……+f(a1)为偶数时才能重排成，所以嘛,上面那个有解的. ②问题描述： 在3X3的九宫格棋盘上，摆有8个将牌，每一个将牌都刻有1~8数码中的某一个数码。棋盘中留有一个空格，允许周围的某一个将牌向空格移动，这样通过移动将牌就可以不断地改变将牌的布局。这种游戏的求解的问题是：给定一种处 世的将牌布局或结构和一个目标的布局，问如何移动将牌，实现从从初始状态到目标状态的转变。 下面给出初始状态和目标状态： 初始状态：Array 目标状态： 评价函数f(n)形式为：f(n)=g(n)+h(n),其中g(n)是节点所处的深度， h(n)是启发式函数，这里启发式函数h(n)表示“不在位”的将牌个数，这时f(n) 注意：移动规则为左-→上→右→下。 ③搜索过程： 因此可得解路径：S(4)→B(4)→D(5)→E(5)→I(5)→K(5)→L(5). ④得到OPEN表和CLOSED表 OPEN表 八数码问题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，并将初始结点入队，设置队列头和尾指针。 1、程序源代码 #include 人工智能作业八数码问题 一、题目 八数码问题： 初始状态图：目标状态图： 二、算符与状态空间 算符：左、上、右、下 状态空间： 状态：A=(X0,X1,X2,X3,X4,X5,X6,X7,X8) 初始状态：S0=(0,4,1,5,2,8,3,6,7); 目标状态：Sg=(0,1,7,5,2,8,3,6,4)。 三、搜索树 22 求解: 四、Open 表，Closed 表 Open 表： Closed 表： 五、程序代码 /* 3_13.pro eight puzzle */ trace DOMAINS state=st(in,in,in,in,in,in,in,in,in) in=integer DATABASE-mydatabase open(state,integer) closed(integer,state,integer) res(state) mark(state) fail_ PREDICATES solve search(state,state) result searching step4(integer,state) step56(integer,state) equal(state,state) repeat resulting(integer) rule(state,state) GOAL solve. CLAUSES solve:-search(st(0,4,1,5,2,8,3,6,7),st(0,1,7,5,2,8,3,6,4)),result. search(Begin,End):-retractall(_,mydatabase), assert(closed(0,Begin,0)),assert(open(Begin,0)), 人工智能实验报告 实验名称：八数码问题 姓名：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 ②。 八数码问题分析 班级：计算机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*算法以及可采纳性 ; 昆明理工大学信息工程与自动化学院学生实验报告 （2012 —2013 学年第 1 学期） 课程名称：人工智能开课实验室：信自楼442 2012 年10月 24日 一、上机目的及内容 1.上机内容 用确定性推理算法求解教材65-66页介绍的八数码难题。 2.上机目的 （1）复习程序设计和数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并实现在小规模状态空间中进行图搜索的方法； （3）理解并掌握图搜索的技术要点。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）设计并实现程序，求解出正确的解答路径； （2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析； （3）对一般图搜索的技术要点和技术难点进行评述性分析。 问题描述： 在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以 不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状 态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。 后继函数： 通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。 目标测试： 比较当前状态和目标状态的格局是否一致。 路径消耗： 每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 数据结构 static int target[9]={1,2,3,8,0,4,7,6,5}; 全局静态变量，表示目标状态class eight_num { private: int num[9]; 定义八数码的初始状态 int not_in_position_num; 定义不在正确位置八数码的个数 int deapth; 定义了搜索的深度 int eva_function; 评价函数的值，每次选取最小的进行扩展public: 人工智能上机实验二八数码问题的求解策略1、广度优先算法程序截图： 2、最佳优先算法程序截图： （接上图） 3、程序代码： ①广度优先算法： (defun init-search (start goal) (declare (special *open*)) (declare (special *closed*)) (declare (special *moves*)) (declare (special *start*)) (declare (special *goal*)) (let (tuple) (setq tuple (cons start '(nil)) ) (setq *open* (list tuple) ) (setq *closed* nil ) (setq *start* start) (setq *goal* goal) (setq *moves* '(blank-left blank-up blank-right blank-down)) (breadth-first-search))) (defun breadth-first-search () (declare (special *open*)) (declare (special *closed*)) (declare (special *goal*)) (declare (special *moves*)) (let (state tuple children path) (cond ((null *open*) 'FAIL!) (t (setq tuple (car *open*) ) (setq state (car tuple) ) (setq *open* (cdr *open*) ) (setq *closed* (cons tuple *closed*)) (cond ((equal state *goal*) (setq path (get-path-from *goal*)) (setq path (reverse path)) (print-path path) 人工智能实验一报告题目：采用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 -八数码问题求解--实验报告讲解
用A算法解决八数码问题演示教学
八数码问题人工智能实验报告
A星算法求八数码问题试验报告
八数码问题C语言A星算法详细实验报告含代码
C语言实现8数码问题
八数码实验报告人工智能课设报告
八数码问题C语言A星算法详细实验报告含代码
启发式搜索算法解决八数码问题(C语言)
人工智能 八数码实验
A星算法求八数码问题实验报告
用盲目搜索技术解决八数码问题
八数码问题实验报告讲解
启发式搜索 八数码问题
八数码问题报告
人工智能试验-八数码难题
人工智能实验八数码问题的求解策略
采用A算法解决八数码问题