多种方法解决八数码难题

启发式搜索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)以此新值取代旧值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⼋数码问题解析⼋数码的问题描述为：在3×3的棋盘上，摆有⼋个棋⼦，每个棋⼦上标有1⾄8的某⼀数字。

棋盘中留有⼀个空格，空格⽤-1来表⽰。

空格周围的棋⼦可以移到空格中。

要求解的问题是：给出⼀种初始布局（初始状态）和⽬标布局，找到⼀种最少步骤的移动⽅法，实现从初始布局到⽬标布局的转变。

解决⼋数码的⽅法很多，本⽂采⽤1.⼴度优先搜索的策略，和A星算法两种⽐较常⽤的算法思想解决此问题⼴度优先搜索的策略⼀般可以描述为以下过程：状态空间的⼀般搜索过程OPEN表：⽤于存放刚⽣成的节点CLOSE表：⽤于存放将要扩展或已扩展的节点1. 把初始节点S0放⼊OPEN表,并建⽴只含S0的图,记为GOPEN：=S0,G：=G0（G0=S0）2. 检查OPEN表是否为空,若为空则问题⽆解,退出LOOP：IF（OPEN）=（） THEN EXIT（FAIL）3. 把OPEN表的第⼀个节点取出放⼊CLOSE表,记该节点为节点nN：=FIRST（OPEN）,REMOVE（n,OPEN）,ADD（n,CLOSE）4. 观察节点n是否为⽬标节点,若是,则求得问题的解,退出IF GOAL（n） THEN EXIT（SUCCESS）5. 扩展节点n,⽣成⼀组⼦节点.把其中不是节点n先辈的那些⼦节点记作集合M,并把这些节点作为节点n的⼦节点加⼊G中.EXPAND（n）-->M（mi）,G：=ADD（mi,G）6. 转第2步下⾯贴出代码：import timeimport copyclass list():def __init__(self,info): = infoself.front = Noneclass Solution():def __init__(self):self.open = []self.closed = []self.co = 0def msearch(self,S0, Sg):head = list(S0)self.open.append(head)while self.open:n = self.open.pop(0)self.co += 1print('取得节点n:',)if == Sg:print('得到问题的解!')print('⼀共进⾏了',self.co,'次查找')print('该问题的解为：') #对n进⾏while n:print()n = n.frontreturnif n in self.closed:#节点判定是否为扩展问题print('该结点不可扩展')else:print('该节点可扩展')#扩展节点n，#将其⼦节点放⼊open的尾部，#为每⼀个⼦节点设置指向⽗节点的指针nkongdi, nkongdj = 0, 0for i in range(3):for j in range(3):if [i][j] == -1:nkongdi = inkongdj = jln,un,rn,dn =copy.deepcopy(),copy.deepcopy(),copy.deepcopy(),copy.deepcopy()if nkongdj != 0: #rightrn[nkongdi][nkongdj],rn[nkongdi][nkongdj-1] = rn[nkongdi][nkongdj-1],rn[nkongdi][nkongdj]rn = self.link(n,rn)if rn not in self.closed:self.open.append(rn)if nkongdi != 0: #downdn[nkongdi][nkongdj],dn[nkongdi-1][nkongdj] = dn[nkongdi-1][nkongdj],dn[nkongdi][nkongdj]dn = self.link(n,dn)if dn not in self.closed:self.open.append(dn)if nkongdj != 2: #leftln[nkongdi][nkongdj],ln[nkongdi][nkongdj+1] = ln[nkongdi][nkongdj+1],ln[nkongdi][nkongdj]ln = self.link(n,ln)if ln not in self.closed:self.open.append(ln)if nkongdi != 2: #upun[nkongdi][nkongdj],un[nkongdi+1][nkongdj] = un[nkongdi+1][nkongdj],un[nkongdi][nkongdj]un = self.link(n,un)if un not in self.closed:self.open.append(un)self.closed.append(n)def link(self, n ,willn):willnn = list(willn)willnn.front = nreturn willnnif __name__ == '__main__':S0 = [[2,8,3],[1,-1,4],[7,6,5]]S1 = [[1,2,3],[8,-1,4],[7,6,5]]Solution().msearch(S0,S1)代码的⼀些问题：1.对于⼋数码这种状态，可以采⽤⼀些常⽤的压缩策略来减少对内存空间的使⽤。

用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表的估价值 ){把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN //取最小路径的估价值}}if(X not inboth){把n设置为X的父亲;求X的估价值;并将X插入OPEN表中; //还没有排序}}//end for将n节点插入CLOSE表中;按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。

八数码难题一、问题简介八方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。

空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动。

例如，假设一个3x3矩阵的初始状态为：8 0 32 1 47 6 5目标状态为：1 2 38 0 47 6 5二、算法分析1、问题表示：问题表示的核心是如何存储搜索过程中得到的状态。

本人是这样存储的：对每个状态用一个9位数存储，例如：把初始状态：8 0 32 1 47 6 5存储为一个9位数：8032147652、问题分析想法一：采用插入排序的方法，八数码问题好比是一列数，将各个行列的数字按大小排列，在插入的时候考虑方向性和比较性，对每个数字节点设置前后左右四个属性，分别在初始状态比较各自队列的大小，比如按照左前右后顺时针的方向依次比较和移动，设置哨兵，循环比较，最后得到的序列也就是八数码问题迎刃而解了。

想法二：采用prolog语言表示，Prolog（Programming in Logic的缩写）是一种逻辑编程语言。

它建立在逻辑学的理论基础之上，最初被运用于自然语言等研究领域。

现在它已广泛的应用在人工智能的研究中，它可以用来建造专家系统、自然语言理解、智能知识库等。

2、解题算法：广度搜索常用的优化方法：哈希表法——记录队列中已有节点，用于判断是否需要扩展节点。

A*算法——构造估价函数。

双向广度优先搜索——从源节点、目标节点一起开始搜索。

三、算法实现本程序用了广度优先搜索这种策略进行搜索，且其搜索深度限制在1000内，其代码实现如下：#include "stack1.h"#include<time.h>stack open,closed;//表的基本操作void swap(int &a,int &b)//比较数字{int bak=a; a=b; b=bak;}int isok(int pos)//界限判断{return pos>=0&&pos<3*3;}int isdiff(int ch[])//判断输入数码是否合法{for(int i=0;i<3*3-1;i++)for(int j=i+1;j<3*3;j++)if(ch[i]==ch[j]||!isok(i)||!isok(j))return 0;return 1;}void init(int ch[],int flag)//初始化数码,键盘输入{cout<<"请输入目标状态:("<<3*3<<"个)"<<endl;for( int j=0;j<3*3;j++)cin>>chdes[j];while(!(isdiff(chdes))){cout<<"初始化错误,数据不合理!"<<endl;cout<<"请输入目标状态:("<<3*3<<"个)"<<endl;for( j=0;j<3*3;j++)cin>>chdes[j];}cout<<"请输入初始状态:("<<3*3<<"个)"<<endl;for(j=0;j<3*3;j++)cin>>ch[j];while(!(isdiff(ch))){cout<<"初始化错误,数据不合理!"<<endl;cout<<"请输入初始状态:("<<3*3<<"个)"<<endl;for(j=0;j<3*3;j++)cin>>ch[j];}for(j=0;j<3*3;j++)chbak[j]=ch[j];}int findnext(int pos,int step)//找到移动位置{if(step>=0&&step<4) //四个方向移动{switch(step){case 0:if(isok(pos-3))return pos-3;return -1;break;case 1:if(isok(pos+1)&&pos/3==(pos+1)/3)return pos+1;return -1;break;case 2:if(isok(pos+3))return pos+3;return -1;break;case 3:if(isok(pos-1)&&pos/3==(pos-1)/3)return pos-1;return -1;break;}}return -1;}int getnum(int pos){if(isok(pos)){for(int i=0;i<3*3;i++)if(chdes[i]==ch[pos])return(abs(i/3-pos/3)+abs(i%3-pos%3));}return 0;}int getallnum(){int sum=0;for(int i=0;i<3*3;i++)sum+=getnum(i);return sum;}int findzero(int ch[]){for(int i=0;i<3*3;i++)if(ch[i]==0)return i;return -1;}void showparent(node *root)//递归方式显示结果路径{if(root->pre!=-1){showparent(&arr[root->pre]);root->show();cout<<"--第"<<root->precost+1<<"步--"<<endl;}}void showchar(int ch[])//显示一个状态{for(int i=0;i<3*3;i++){cout<<ch[i]<<" ";if((i+1)%3==0)cout<<endl;}}int getpath(node *thisnode,int &sums)//递归方式搜索最优路径{if(sums>=9*maxsize/10){cout<<"应该是没有解路径,需要太多空间!(需存储"<<jiecheng(3*3)<<" 个状态!)"<<endl;return 0;}else{for(int i=0;i<3*3;i++)ch[i]=thisnode->ch1[i];for(i=0;i<4;i++)//从四个方位搜索{int pos1=findnext(thisnode->pos,i);//搜索的位置if(pos1!=-1)//搜索的位置合法{swap(ch[pos1],ch[thisnode->pos]);//移动数码int hn=getallnum();if(hn==0){cout<<"a solution is :"<<endl;showchar(chbak);cout<<"--第1步--"<<endl;showparent(thisnode);showchar(chdes);return 1;}elseif(hn>0)//如果没有到达目标状态{arr[sums].nextcost=hn;arr[sums].precost=thisnode->precost+1;//已经走过的路程arr[sums].pos=findzero(ch);//空格的位置for(int j=0;j<3*3;j++)//当前的状态arr[sums].ch1[j]=ch[j];arr[sums].pre=thisnode->id;if(!(open.cmp(&arr[sums])||closed.cmp(&arr[sums]))){open.insert(&arr[sums]);sums++;}}swap(ch[pos1],ch[thisnode->pos]);}}if(!open.isempty()){node *tem=open.del();closed.insert1(tem);getpath(tem,sums);}else{cout<<"没有解路径!"<<endl;return 0;}}return 0;}void main(){char cls[4]="cls",input='1';int flag=1,sum=1;while(input>='1'&&input<='4'){open.clear();closed.clear();sum=1;flag=1;select();cin>>input;if(input>='1'&&input<='4'){switch(input){case '1':init(ch,0);break;case '2':system(cls);flag=2;}if(flag==1){for(int i=0;i<maxsize;i++)arr[i].id=i;arr[0].precost=0;arr[0].pre=-1;arr[0].pos=findzero(ch);arr[0].nextcost=getallnum();for(i=0;i<3*3;i++)arr[0].ch1[i]=ch[i];open.insert(&arr[0]);node *p=open.del();closed.insert1(p);cout<<"目标状态:"<<endl;showchar(chdes);cout<<"初始状态:"<<endl;showchar(chbak);if(arr[0].nextcost>0)getpath(&arr[0],sum);elsecout<<"初始状态为目标状态！"<<endl;}}}}四、实验分析实验界面为：本实验采取表的排序，并利用广度优先搜索来查找路径，基本实现了实验要求，仍有不完善之处，仍需继续改正。

A＊算法求解八数码问题1、八数码问题描述所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8，其中一个单元格是空的.将任意摆放的数码盘（城初始状态）逐步摆成某个指定的数码盘的排列（目标状态），如图1所示图1 八数码问题的某个初始状态和目标状态对于以上问题，我们可以把数码的移动等效城空格的移动.如图1的初始排列，数码7右移等于空格左移.那么对于每一个排列,可能的一次数码移动最多只有4中,即空格左移、空格右移、空格上移、空格下移。

最少有两种（当空格位于方阵的4个角时）.所以,问题就转换成如何从初始状态开始，使空格经过最小的移动次数最后排列成目标状态。

2、八数码问题的求解算法2。

1 盲目搜索宽度优先搜索算法、深度优先搜索算法2。

2 启发式搜索启发式搜索算法的基本思想是：定义一个评价函数f,对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。

先定义下面几个函数的含义：f＊（n）=g*(n）+h*（n) (1)式中g*（n)表示从初始节点s到当前节点n的最短路径的耗散值；h*（n)表示从当前节点n到目标节点g的最短路径的耗散值，f*(n）表示从初始节点s经过n到目标节点g 的最短路径的耗散值。

评价函数的形式可定义如(2）式所示:f(n)=g（n)+h(n) （2）其中n是被评价的当前节点。

f(n）、g(n)和h(n）分别表示是对f＊（n）、g*（n）和h*(n）3个函数值的估计值。

利用评价函数f(n)=g（n)+h(n)来排列OPEN表节点顺序的图搜索算法称为算法A。

在A算法中，如果对所有的x，h(x)<=h*(x）（3)成立,则称好h（x）为h＊(x)的下界,它表示某种偏于保守的估计。

采用h＊(x）的下界h（x）为启发函数的A算法,称为A*算法.针对八数码问题启发函数设计如下：f（n)=d（n)+p(n) (4)其中A＊算法中的g(n)根据具体情况设计为d(n），意为n节点的深度，而h(n）设计为图2 A＊算法流程图p(n),意为放错的数码与正确的位置距离之和。

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

在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）取出队列头（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列。

人工智能实验一报告题目：采用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问题描述所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。

课程论文摘要八数码问题也称为九宫问题。

在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。

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

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

所谓问题的一个状态就是棋子在棋盘上的一种摆法。

棋子移动后，状态就会发生改变。

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

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

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

这里详细讲述A*算法。

关键词:八数码问题；空间状态；搜索法；A*算法一、实验目的理解并熟悉掌握A*算法。

二、实验内容九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数三、问题的搜索形式描述（4要素）初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。

其中，状态空间中的任一种状态都可以作为初始状态。

后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。

目标测试：比较当前状态和目标状态的格局是否一致。

路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。

四、解决方案介绍（原理）常用的状态空间搜索有深度优先和广度优先。

广度优先是从初始状态一层一层向下找，直到找到目标为止。

深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。

广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。

这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。

由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。

⼈⼯智能结课作业-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在遍历树的应⽤后，我们将其应⽤于⼋数码问题的解决。

八数码的几种解决帖子关于是八数码的，是前段时间写的，为了给别人一些搜索的样例。

现在，事差不多完了，代码还留着，觉着放着浪费，又想自己水平过于欠缺，再加上看在C吧的初学者还是占主要，就觉得发在此处共他们学习还是不错的，仅此而已。

如果有不知道八数码的问题的，可以上网一搜，就什么都明白了。

在这里我只用了几种算法实现，其实还有其他方法，我并没有写（如果有人需要，可能我会重新完成）。

首先分析下八数码的一些算法吧。

1：深度优先（DFS）：这个方法起始对八数码非常不好，问题在于搜索过于盲目，搜索深度如果没有限制，有些是根本没必要的（因为八数码的解，大部分集中在20~30步之间）。

而且即使搜索到一个解，很可能不是最优解。

所以用DFS解决这个问题并不明智，不过为了显示其不好，我仍然实现，不过在程序中设置最大深度限制为100。

2：宽度优先搜索（BFS）宽度优先搜索，解决的还不错，经过对hash函数的优化，能使一个20~30步的解在200~300MS内解决（不过其还可以做进一步的优化）。

3：迭代加深搜索迭代加深搜索，可以说是吸取了宽搜和深搜的优点，同时避免了深搜搜到第一个解的不最优性，和宽搜的使用较大的内存空间。

在这里我也用迭代加深搜索，仔细一看的人就发现，起使他只是在深搜上稍微做点“手脚”就完毕，但是其思想，虽然显而易见，可我觉得并不容易想到（指当初提出这个算法的时候）。

4：爬山法爬山法，经常在人工只能里面见得到，由于其高效，实现简单，所以其有时也是很有用的。

但是爬山法，也有缺点，就是搜到的解只是局部最优解，而且有陷入“无解”的风险。

爬山法，顾名思意就是一直沿着“最好的方向走”直到“山顶”，就找到解。

爬山法，不像回溯，在遍历节点时不保存其他非当前最优节点，也就是说，一旦走错了，就不能再后头搜索其他方向。

所以在我写的爬山法中，对于一个解，虽然很多100多步，但是所需的时间确实0MS左右。

5：双向搜索双向搜索，前后来搜，碰到头，然后一拼接就出了路径。

八数码问题——A*算法0810505班问题描述：有一个3×3的棋盘，其中有0~8九个数字，0表示空格，其他的数字可以和0交换位置。

求由初始状态到达目标状态步数最少的解。

解决八数码问题的常用方法为图搜索法，可用A*算法实现，其又因估价函数的不同而有着不同的搜索时间。

程序说明：在本程序中，用A*算法实现了八数码问题，其估价函数选择的是“不在位”数和当前层数之和，初始状态和目标状态均可由用户设定，目标状态默认为：1 2 34 5 67 8 0在它可执行程序中，由用户输入一组数码，如：8 3 51 2 74 6 0然后程序会询问用户是否要更改目标，输入N即可。

等一会儿（几秒到几十秒）后便可得到结果以及消耗的时间和空间。

程序中的Block是指生成的8数码块，以此来衡量空间消耗的多少。

程序清单：#include "stdafx.h"#include "iostream.h"#include <time.h>#include <stdio.h>#include <dos.h>#include <conio.h>static int target[9]={1,2,3,4,5,6,7,8,0};//定义classclass eight_num{private:int num[9];int not_in_position_num;int deapth;int eva_function;public:eight_num* parent;eight_num* leaf_next;eight_num* leaf_pre;eight_num(int init_num[9]);eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9){num[0]=num1;num[1]=num2;num[2]=num3;num[3]=num4;num[4]=num5;num[5]=num6;num[6]=num7;num[7]=num8;num[8]=num9;}eight_num(void){for (int i=0;i<9;i++)num[i]=i;}void cul_para(void);void get_numbers_to(int other_num[9]);int get_nipn(void){return not_in_position_num;}int get_deapth(void){return deapth;}int get_evafun(void){return eva_function;}void set_num(int other_num[9]);void show(void);eight_num& operator=(eight_num&);eight_num& operator=(int other_num[9]);int operator==(eight_num&);int operator==(int other_num[9]);};void eight_num::cul_para(void){int i;int temp_nipn=0;for (i=0;i<9;i++)if (num[i]!=target[i])temp_nipn++;not_in_position_num=temp_nipn;if (this->parent==NULL)deapth=0;elsedeapth=this->parent->deapth+1;eva_function=not_in_position_num+deapth;}eight_num::eight_num(int init_num[9]){for (int i=0;i<9;i++)num[i]=init_num[i];}void eight_num::show(){cout<<num[0];cout<<" ";cout<<num[1];cout<<" ";cout<<num[2];cout<<"\n";cout<<num[3];cout<<" ";cout<<num[4];cout<<" ";cout<<num[5];cout<<"\n";cout<<num[6];cout<<" ";cout<<num[7]cout<<" ";cout<<num[8];cout<<"\n";}void eight_num::get_numbers_to(int other_num[9]){for (int i=0;i<9;i++)other_num[i]=num[i];}void eight_num::set_num(int other_num[9]){for (int i=0;i<9;i++)num[i]=other_num[i];}eight_num& eight_num::operator=(eight_num& another_8num) {for (int i=0;i<9;i++)num[i]=another_8num.num[i];not_in_position_num=another_8num.not_in_position_num;deapth=another_8num.deapth+1;eva_function=not_in_position_num+deapth;return *this;}eight_num& eight_num::operator=(int other_num[9]){for (int i=0;i<9;i++)num[i]=other_num[i];return *this;}int eight_num::operator==(eight_num& another_8num){int match=1;for (int i=0;i<9;i++)if(num[i]!=another_8num.num[i]){match=0;break;}if (match==0)return 0;elsereturn 1;}int eight_num::operator==(int other_num[9]){int match=1;for (int i=0;i<9;i++)if(num[i]!=other_num[i]){match=0;break;}if (match==0)return 0;elsereturn 1;}//定义class结束//空格向上移int move_up(int num[9]) {for (int i=0;i<9;i++)if (num[i]==0)break;if (i<3)return 0;else{num[i]=num[i-3];num[i-3]=0;return 1;}}//空格向下移int move_down(int num[9]) {for (int i=0;i<9;i++)if (num[i]==0)break;if (i>5)return 0;else{num[i]=num[i+3];num[i+3]=0;return 1;}}//空格向左移int move_left(int num[9]) {for (int i=0;i<9;i++)if (num[i]==0)break;if (i==0||i==3||i==6)return 0;else{num[i]=num[i-1];num[i-1]=0;return 1;}}//空格向右移int move_right(int num[9]){for (int i=0;i<9;i++)if (num[i]==0)break;if (i==2||i==5||i==8)return 0;else{num[i]=num[i+1];num[i+1]=0;return 1;}}//判断可否解出int icansolve(int num[9],int target[9]){int i,j;int count_num,count_target;for (i=0;i<9;i++)for (j=0;j<i;j++){if(num[j]<num[i]&&num[j]!=0)count_num++;if(target[j]<target[i]&&target[j]!=0)count_target++;}count_num=count_num-2*(count_num/2);count_target=count_target-2*(count_target/2);if ((count_num==1&&count_target==1)||(count_num==0&&count_target==0)) return 1;elsereturn 0;}//判断有无重复int existed(int num[9],eight_num *where){eight_num *p;for(p=where;p!=NULL;p=p->parent)if(*p==num)return 1;return 0;}//寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start){eight_num *p,*OK;p=OK=start;int min=start->get_evafun();for(p=start;p!=NULL;p=p->leaf_next)if(min>p->get_evafun()){OK=p;min=p->get_evafun();}return OK;}//主函数开始int main(void){double time;clock_t Start,Finish;int memery_used=0,step=0;int num[9];int flag=0;//是否输入错误标志，1表示输入错误int bingo=0;//是否查找成功标志，1表示成功int i,j;cout<<"Please input the number(0 for the blank):\n";for (i=0;i<9;i++){flag=0;cin>>num[i];for(j=0;j<i;j++)if(num[i]==num[j])flag=1;if (num[i]<0||num[i]>8||flag==1){i--;cout<<"Illegle number!\tReinput!\n";}}cout<<"Do you want to modify the target(Y/N)?"; char input;cin>>input;if (input=='y'||input=='Y'){cout<<"\nPlease input the new target:\n";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<<"Illegle number!\tReinput!\n";}}}eight_num S(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used++;cout<<"Now the initial numbers are:\n";S.show();cout<<"And the Target is:\n";Target.show();if(!icansolve(num,target)){cout<<"No one can solve it!\n";cin>>i;return 1;}Start=clock( );eight_num *OK_leaf=&S,*leaf_start=&S,*new_8num,*p; while(OK_leaf!=NULL&&bingo!=1){OK_leaf=find_OK_leaf(leaf_start);if(*OK_leaf==Target){bingo=1;break;}p=OK_leaf->leaf_pre;OK_leaf->get_numbers_to(num);if(move_up(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf->get_numbers_to(num);if(move_down(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf->get_numbers_to(num);if(move_left(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf->get_numbers_to(num);if(move_right(num)&&!existed(num,OK_leaf)){new_8num=new eight_num;new_8num->set_num(num);new_8num->parent=OK_leaf;new_8num->cul_para();new_8num->leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep->leaf_next=new_8num;p=new_8num;memery_used++;}p->leaf_next=OK_leaf->leaf_next;if(OK_leaf->leaf_next!=NULL)OK_leaf->leaf_next->leaf_pre=p;OK_leaf->leaf_next=OK_leaf->leaf_pre=NULL;}Finish=clock( );if(bingo==1){time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC;eight_num *p;for (p=OK_leaf->parent;p!=NULL;p=p->parent){cout<<" ^\n";p->show();step++;}cout<<"Time cost:";cout<<time;cout<<"ms\n";cout<<"Memery cost:";cout<<memery_used;cout<<"blocks\n";cout<<"Totaly covered steps:";cout<<step;cout<<"\n";}elsecout<<"Fail to find!";cin>>i;return 0;}结果：A*算法实际上就是一种启发式搜索，其内容如下：(1)生成一个只包含开始结点n。

八数码问题,实验报告八数码实验报告利用人工智能技术解决八数码游戏问题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 的扩展节点表中。