下载文档原格式
a星算法求解八数码问题python一、介绍八数码问题是一种经典的智力游戏，也是人工智能领域中的经典问题之一。
在这个问题中，有一个3×3的棋盘，上面摆着1至8这8个数字和一个空格，初始状态和目标状态都已知。
要求通过移动数字，将初始状态变换成目标状态。
其中空格可以和相邻的数字交换位置。
为了解决这个问题，我们可以使用A*算法。
本文将详细介绍如何用Python实现A*算法来求解八数码问题。
二、A*算法简介A*算法是一种启发式搜索算法，常用于寻找最短路径或最优解等问题。
它基于Dijkstra算法，并加入了启发式函数来加速搜索过程。
在A*算法中，每个节点都有两个估价值：g值和h值。
g值表示从起点到该节点的实际代价，h值表示从该节点到目标节点的估计代价。
启发式函数f(n) = g(n) + h(n) 表示从起点到目标节点的估计总代价。
A*算法采用优先队列来保存待扩展的节点，并按照f(n)值从小到大排序。
每次取出队头元素进行扩展，并将扩展出来的新节点按照f(n)值插入队列中。
当扩展出目标节点时，算法结束。
三、八数码问题的状态表示在八数码问题中，每个状态都可以表示为一个3×3的矩阵。
我们可以用一个一维数组来表示这个矩阵，其中0表示空格。
例如，初始状态可以表示为[2, 8, 3, 1, 6, 4, 7, 0, 5]，目标状态可以表示为[1, 2, 3, 8, 0, 4, 7, 6, 5]。
四、A*算法求解八数码问题的步骤1.将初始状态加入优先队列中，并设置g值和h值为0。
2.从队头取出一个节点进行扩展。
如果该节点是目标节点，则搜索结束；否则，将扩展出来的新节点加入优先队列中。
3.对于每个新节点，计算g值和h值，并更新f(n)值。
如果该节点已经在优先队列中，则更新其估价值；否则，将其加入优先队列中。
4.重复第2步至第3步直到搜索结束。
五、Python实现以下是用Python实现A*算法求解八数码问题的代码：```import heapqimport copy# 目标状态goal_state = [1,2,3,8,0,4,7,6,5]# 启发式函数：曼哈顿距离def h(state):distance = 0for i in range(9):if state[i] == 0:continuerow = i // 3col = i % 3goal_row = (state[i]-1) // 3goal_col = (state[i]-1) % 3distance += abs(row - goal_row) + abs(col - goal_col)return distance# A*算法def A_star(start_state):# 初始化优先队列和已访问集合queue = []visited = set()# 将初始状态加入优先队列中，并设置g值和h值为0heapq.heappush(queue, (h(start_state), start_state, 0))while queue:# 取出队头元素进行扩展f, state, g = heapq.heappop(queue)# 如果该节点是目标节点，则搜索结束；否则，将扩展出来的新节点加入优先队列中。
用A*算法解决八数码问题1 问题描述1.1 待解决问题的解释八数码游戏（八数码问题）描述为：在3×3组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。
棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。
这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。
1.2 问题的搜索形式描述（4要素）初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。
其中，状态空间中的任一种状态都可以作为初始状态。
后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。
目标测试：比较当前状态和目标状态的格局是否一致。
路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。
1.3 解决方案介绍（原理）对于八数码问题的解决，首先要考虑是否有答案。
每一个状态可认为是一个1×9的矩阵，问题即通过矩阵的变换，是否可以变换为目标状态对应的矩阵？由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。
这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。
如果初始状态可以到达目标状态，那么采取什么样的方法呢？常用的状态空间搜索有深度优先和广度优先。
广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。
广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。
这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。
他的效率实在太低，甚至不可完成。
由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。
八数码问题（一）问题描述在一个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; 所屏蔽方向：一个屏蔽方向，防止回推。
实验四 A*算法求解8数码问题一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解8数码难题，理解求解流程和搜索顺序。
二、实验原理A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。
对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。
因此，f 是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n 到达目标节点的估价代价h(n)，且h(n)<=h*(n)，h*(n)为n节点到目标节点的最优路径的代价。
八数码问题是在3×3的九宫格棋盘上，排放有8个刻有1～8数码的将牌。
棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。
针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。
如图1所示表示了一个具体的八数码问题求解。
图1 八数码问题的求解三、实验内容1、参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语言不限），要求设计两种不同的估价函数。
2、在求解8数码问题的A*算法程序中，设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。
3、对于8数码问题，设置与图1所示相同的初始状态和目标状态，用宽度优先搜索算法（即令估计代价h(n)＝0的A*算法）求得问题的解，记录搜索过程中的扩展节点数、生成节点数。
4、提交实验报告和源程序。
四.实验截图五．源代码#include<iostream>#include"stdio.h"#include"stdlib.h"#include"time.h"#include"string.h"#include<queue>#include<stack>using namespace std;const int N=3;//3*3棋?盘ìconst int Max_Step=32;//最?大洙?搜?索÷深?度èenum Direction{None,Up,Down,Left,Right};//方?向ò，?分?别纄对?应畖上?下?左哩?右?struct Chess//棋?盘ì{int chessNum[N][N];//棋?盘ì数簓码?int Value;//评à估à值μDirection BelockDirec;//所ù屏á蔽?方?向òstruct Chess * Parent;//父?节ú点?};void PrintChess(struct Chess *TheChess);//打洙?印?棋?盘ìstruct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess);//移?动ˉ棋?盘ì数簓字?int Appraisal(struct Chess * TheChess,struct Chess * Target);//估à价?函ˉ数簓struct Chess * Search(struct Chess* Begin,struct Chess * Target);//A*搜?索÷函ˉ数簓int main(){//本?程ì序ò的?一?组哩?测a试?数簓据Y为a/*初?始?棋?盘ì*1 4 0**3 5 2**6 7 8**//*目?标括?棋?盘ì*0 1 2**3 4 5**6 7 8**/Chess Target;Chess *Begin,*ChessList;Begin=new Chess;int i;cout<<"请?输?入?初?始?棋?盘ì，?各÷数簓字?用?空?格?隔?开a：阰"<<endl;for(i=0;i<N;i++){for(int j=0;j<N;j++){cin>>Begin->chessNum[i][j];}}cout<<"请?输?入?目?标括?棋?盘ì，?各÷数簓字?用?空?格?隔?开a：阰"<<endl;for(i=0;i<N;i++){for(int j=0;j<N;j++){cin>>Target.chessNum[i][j];}}//获?取?初?始?棋?盘ìAppraisal(Begin,&Target);Begin->Parent=NULL;Begin->BelockDirec=None;Target.Value=0;cout<<"初?始?棋?盘ì:";PrintChess(Begin);cout<<"目?标括?棋?盘ì:";PrintChess(&Target);ChessList=Search(Begin,&Target);//搜?索÷//打洙?印?if(ChessList){/*将?返う?回?的?棋?盘ì列表括?利?用?栈?将?其?倒?叙e*/Chess *p=ChessList;stack<Chess *>Stack;while(p->Parent!=NULL){Stack.push(p);p=p->Parent;}cout<<"搜?索÷结á果?:"<<endl;int num=1;while(!Stack.empty()){cout<<"第台?<<num<<"步?: ";num++;PrintChess(Stack.top());Stack.pop();}cout<<"\n完?成é!"<<endl;}elsecout<<"搜?索÷不?到?结á果?，?搜?索÷深?度è大洙?于?2\n"<<endl;return 0;}//打洙?印?棋?盘ìvoid PrintChess(struct Chess *TheChess){cout<<"(评à估à值μ为a";cout<<TheChess->Value;cout<<")"<<endl;for(int i=0;i<N;i++){cout<<" ";for(int j=0;j<N;j++){cout<<TheChess->chessNum[i][j]<<" ";}cout<<endl;}}//移?动ˉ棋?盘ìstruct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) {struct Chess * NewChess;//获?取?空?闲D格?位?置?int i,j;for(i=0;i<N;i++){bool HasGetBlankCell=false;for(j=0;j<N;j++){if(TheChess->chessNum[i][j]==0){HasGetBlankCell=true;break;}}if(HasGetBlankCell)break;}int ii=i,jj=j;bool AbleMove=true;//判D断?是?否?可é以?移?动ˉswitch(Direct){case Up:i++;if(i>=N)AbleMove=false;break;case Down:i--;if(i<0)AbleMove=false;break;case Left:j++;if(j>=N)AbleMove=false;break;case Right:j--;if(j<0)AbleMove=false;break;};if(!AbleMove)//不?可é以?移?动ˉ则ò返う?回?原-节ú点?{return TheChess;}if(CreateNewChess){NewChess=new Chess();for(int x=0;x<N;x++){for(int y=0;y<N;y++)NewChess->chessNum[x][y]=TheChess->chessNum[x][y];//创洹?建¨新?棋?盘ì，?此?时骸?值μ与?原-棋?盘ì一?致?}}elseNewChess=TheChess;NewChess->chessNum[ii][jj] = NewChess->chessNum[i][j];//移?动ˉ数簓字?NewChess->chessNum[i][j]=0;//将?原-数簓字?位?置?设Θ?置?为a空?格?return NewChess;}//估à价?函ˉ数簓int Appraisal(struct Chess * TheChess,struct Chess * Target){int Value=0;for(int i=0;i<N;i++){for(int j=0;j<N;j++){if(TheChess->chessNum[i][j]!=Target->chessNum[i][j])Value++;}}TheChess->Value=Value;return Value;}//A*搜?索÷函ˉ数簓struct Chess * Search(struct Chess* Begin,struct Chess * Target){Chess *p1,*p2,*p;int Step=0;//深?度èp=NULL;queue<struct Chess *> Queue;Queue.push(Begin);//初?始?棋?盘ì入?队ó//搜?索÷do{p1=(struct Chess *)Queue.front();Queue.pop();//出?队ófor(int i=1;i<=4;i++)//分?别纄从洙?四?个?方?向ò推?导?出?新?子哩?节ú点? {Direction Direct=(Direction)i;if(Direct==p1->BelockDirec)//跳?过y屏á蔽?方?向òcontinue;p2=MoveChess(p1,Direct,true);//移?动ˉ数簓码?if(p2!=p1)//数簓码?是?否?可é以?移?动ˉ{Appraisal(p2,Target);//对?新?节ú点?估à价?if(p2->Value<=p1->Value)//是?否?为a优?越?节ú点?{p2->Parent=p1;switch(Direct)//设Θ?置?屏á蔽?方?向ò,防え?止1往?回?推?{case Up:p2->BelockDirec=Down;break;case Down:p2->BelockDirec=Up;break;case Left:p2->BelockDirec=Right;break;case Right:p2->BelockDirec=Left;break;}Queue.push(p2);//存?储洹?节ú点?到?待鋣处鋦理え?队ó列if(p2->Value==0)//为a0则ò,搜?索÷完?成é{p=p2;i=5;}}else{delete p2;//为a劣ⅷ?质ê节ú点?则ò抛×弃úp2=NULL;}}}Step++;if(Step>Max_Step)return NULL;}while(p==NULL || Queue.size()<=0);return p;}六、实验报告要求1、分析不同的估价函数对A*搜索算法性能的影响等。
实验一 启发式搜索算法姓名：徐维坚 学号：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 ，生成其全部后继节点。
⼈⼯智能结课作业-DFSBFSAstar解决⼋数码问题如果帮到你了，希望给个star⿎励⼀下1 深度优先遍历搜索(DFS)1.1算法介绍深度优先搜索算法（Depth-First-Search，DFS）是⼀种⽤于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分⽀。
当节点v的所在边都⼰被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
这⼀过程⼀直进⾏到已发现从源节点可达的所有节点为⽌。
如果还存在未被发现的节点，则选择其中⼀个作为源节点并重复以上过程，整个进程反复进⾏直到所有节点都被访问为⽌。
属于盲⽬搜索。
以上图为例，简述DFS的过程。
⾸先从根节点"1"出发，按⼀定的顺序遍历其⼦节点，这⾥我们假设优先遍历左边的。
所以，在遍历"1"之后，我们到了节点"2"，此时"2"仍有⼦节点，所以应继续向下遍历，下⼀个节点是"3"，然后是"4"。
到了"4"之后，没有⼦节点了，说明我们已经将这⼀条路遍历完了，接着我们应该回溯，应该回到"4"的⽗节点，也就是"3"。
因为"3"还有⼀个⼦节点"5"没有遍历，所以下⼀个我们应该遍历的是"5"。
遍历完"5"之后⼜发现⼀条路到头了，再次回溯依然回溯到其⽗节点"3"，此时"3"的所有⼦节点都已经遍历完了，因该接着回溯到"3"的⽗节点"2"，然后检查"2"是否有没有遍历完的⼦节点。
按照这样的规则，完成所有节点的遍历。
最终得到的遍历顺序是"1-2-3-4-5-6-7-8-9-10-11-12"在介绍了DFS在遍历树的应⽤后，我们将其应⽤于⼋数码问题的解决。
实验报告课程名称人工智能_____________实验项目八数码难题______________实验仪器电脑、visual C++_________系别____________ 专业__ _____班级/学号学生姓名_ _________实验日期____成绩_______________________指导教师_________一、实验目的理解并熟悉掌握深度优先搜索和广度优先搜索地方法。
二、实验内容九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数【算法分析】解决此类问题的办法是宽度搜索，深度搜索耗时太大无法接受。
当需要移动的步数很多时，普通的宽度搜索仍旧无法满足需要，需要对其进行优化。
这个问题也可以推广到流行的拼图游戏。
【具体步骤】一、确定问题规模（考虑搜索的时间代价）二、确定产生式规则（如果规则太多，则时间代价会很大）三、套用经典宽度搜索框架写程序三、代码和结果#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);/** === FUNCTION ======================================================================* Name: 主函數* Description: 程序入口*=============================================================================== ======*/intmain ( 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;}}四．实验心得这次试验让我更加深入了解了什么是人工智能，让我了解了人工智能的作用以及含义和人工智能的使用范围以及对于我们未来生活得作用的广大。
实验报告一、实验问题八数码问题求解二、实验软件VC6.0 编程语言或其它编程语言三、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。
四、实验数据及步骤（一、）实验内容八数码问题：在3 ×3 的方格棋盘上，摆放着1 到8 这八个数码，有1 个方格是空的，其初始状态如图1 所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
2 83 1 2 31 4 8 47 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 数码问题的隐式图的生成问题。
人工智能实验报告八数码人工智能实验报告八数码引言：人工智能（Artificial Intelligence，简称AI）作为一门前沿的学科，已经在各个领域展现出了巨大的应用潜力。
其中，八数码问题作为一个经典的算法问题，被广泛应用于人工智能领域。
本文将对八数码问题进行实验研究，探讨其在人工智能中的应用。
一、八数码问题的定义八数码问题是指在一个3x3的棋盘上，摆放有1至8这8个数字，其中一个格子为空。
玩家需要通过移动数字，使得棋盘上的数字按照从小到大的顺序排列，空格在最后。
八数码问题可以被抽象为一个搜索问题，即找到从初始状态到目标状态的最短路径。
二、实验方法为了解决八数码问题，我们采用了A*算法作为实验方法。
A*算法是一种启发式搜索算法，通过估计目标状态与当前状态之间的代价函数，选择最优的路径进行搜索。
在本次实验中，我们将使用曼哈顿距离作为代价函数进行搜索。
三、实验结果我们使用Python编程语言实现了八数码问题的求解算法，并进行了多组实验。
实验结果表明，A*算法在解决八数码问题上表现出了较好的效果。
在大部分情况下，A*算法能够在较短的时间内找到最优解。
四、实验讨论尽管A*算法在解决八数码问题上表现出了较好的效果，但我们也发现了一些问题。
首先，A*算法在面对复杂的八数码问题时，搜索时间会显著增加。
其次，A*算法在面对某些特定情况时，可能会陷入局部最优解，无法找到全局最优解。
这些问题需要进一步的研究和改进。
五、应用前景八数码问题作为人工智能领域的经典问题，有着广泛的应用前景。
首先，八数码问题可以被应用于游戏设计中，作为一种智能对手的算法。
其次，八数码问题的解决方法可以被应用于路径规划、图像识别等领域，提高算法的效率和准确性。
六、结论通过本次实验，我们对八数码问题进行了深入的研究和探讨。
A*算法作为一种启发式搜索算法，在解决八数码问题上表现出了较好的效果。
然而，八数码问题仍然存在一些挑战和问题，需要进一步的研究和改进。
