八数码问题C语言A星算法详细实验报告含代码

A*算法求解八数码问题●open 表、closed 表数据结构的选择：1)把s放入open表，记f=h，令closed为空表。

2)重复下列过程，直到找到目标节点为止。

若open表为空表，则宣告失败。

3)选取open表中未设置过的具有最小f值的节点为最佳节点bestnode，并把它放入closed表。

4)若bestnode为一目标节点，则成功求得一解。

5)若bestnode不是目标节点，则扩展之，产生后继节点succssor。

6)对每个succssor进行下列过称：a)对每个succssor返回bestnode的指针。

b)计算g（suc）=g（bes）+k（bes，suc）。

c)如果succssore open，称此节点为old，并填到bestnode的后继节点表中。

d)比较新旧路劲代价。

如果g（suc）<g(old)，则重新确定old的父辈节点为bestnode，记下较小代价g（old），并修真f（old）值。

e)若至old节点的代价较低或一样，则停止扩展节点。

f)若succssore不再closed表中，则看其是否在closed表中。

g)若succssore在closed表中，则转向（c）。

h)若succssore既不在open表中，又不在closed表中，则把它放入open表中，并添入bestnode后裔表中，然后转向（7）。

i)计算f值j)Go loop●节点的数据结构：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:eight_num* parent; 指向节点的父节点eight_num* leaf_next; 指向open表的下一个节点eight_num* leaf_pre; 指向open 表的前一个节点初始状态的构造函数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){}eight_num(void){ }计算启发函数g(n)的值void eight_num::cul_para(void){}显示当前节点的状态void eight_num::show(){}复制当前节点状态到一个另数组中void eight_num::get_numbers_to(int other_num[9]){}设置当前节点状态(欲设置的状态记录的other数组中)void eight_num::set_num(int other_num[9]){}eight_num& eight_num::operator=(eight_num& another_8num){} eight_num& eight_num::operator=(int other_num[9]){}int eight_num::operator==(eight_num& another_8num){}int eight_num::operator==(int other_num[9]){}空格向上移int move_up(int num[9]){}空格向下移int move_down(int num[9]){}空格向左移int move_left(int num[9]){}空格向右移int move_right(int num[9]){}判断可否解出int icansolve(int num[9],int target[9]){}判断有无重复int existed(int num[9],eight_num *where){}寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start){}}A*算法求解框图：●分析估价函数对搜索算法的影响：估价函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。

A*算法解决八数码问题1 问题描述什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。

与空位相邻的棋子可以滑动到空位中。

游戏的目的是要达到一个特定的目标状态。

标注的形式化如下：问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

解决方案介绍算法思想(估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。

估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n 节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。

启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有 h ( t ) = 0，对于结点m和n （n 是m的子结点）有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。

一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

例如：图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*算法解决八数码问题1 问题描述什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。

与空位相邻的棋子可以滑动到空位中。

游戏的目的是要达到一个特定的目标状态。

标注的形式化如下：问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

解决方案介绍算法思想(估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。

估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n 节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。

启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有 h ( t ) = 0，对于结点m和n （n 是m的子结点）有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。

八数码问题1、问题描述所谓八数码问题是指：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。

放牌时要求不能重叠。

于是，在3×3的数码盘上出现了一个空格。

现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。

2、问题分析首先，八数码问题包括一个初始状态(strat) 和 目标状态(goal)，所谓解八数码问题就是在两个状态间寻找一系列可过渡状态（strat-> strat 1-> strat 2->...->goal ）。

这个状态是否存在表示空格）图13、 数据结构 定义结构体Node 如下： typedef struct{int num[9];char cur_expension; //记录是否可以扩展，Y 代表可以扩展，N 代表不可以。

char Operate; //表示不可以执行的操作，'L'代表不能左移，'R'代表不能右移， //'U'代表不能上移，'D'代表不能下移，'C'代表可以任意移动。

int father; //记录父节点的下标。

}Node;Node state[MAXSIZE]; //将搜索过的状态存储于该数组中。

4、广度优先搜索广度优先搜索是指按节点的层次进行搜索,本层的节点没有搜索完毕时,不能对下层节点进行处理,即深度越小的节点越先得到扩展,也就是说先产生的节点先得以扩展处理,直至找到目标为止。

求解八数码问题的搜索过程:如图2所示,把所有可能的算符应用到开始节点(即空格上移、空格左移、空格右移、空格下移),图2只是演示了两个扩展结点，如此继续下去,直到发现目标节点。

图2 变量定义及函数说明：1 2 3 45 6 7 8 01 2 37 4 5 8 0 61 2 34 5 67 8 0#define SUM 100//限定只搜索前50步，50步以后如果仍然没有搜索到结果，认为无解。

实验三：A算法求解8数码问题实验一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程;并利用A算法求解N数码难题;理解求解流程和搜索顺序..二、实验内容1、八数码问题描述所谓八数码问题起源于一种游戏:在一个3×3的方阵中放入八个数码1、2、3、4、5、6、7、8;其中一个单元格是空的..将任意摆放的数码盘城初始状态逐步摆成某个指定的数码盘的排列目标状态;如图1所示图1 八数码问题的某个初始状态和目标状态对于以上问题;我们可以把数码的移动等效城空格的移动..如图1的初始排列;数码7右移等于空格左移..那么对于每一个排列;可能的一次数码移动最多只有4中;即空格左移、空格右移、空格上移、空格下移..最少有两种当空格位于方阵的4个角时..所以;问题就转换成如何从初始状态开始;使空格经过最小的移动次数最后排列成目标状态..2、八数码问题的求解算法2.1 盲目搜索宽度优先搜索算法、深度优先搜索算法2.2 启发式搜索启发式搜索算法的基本思想是：定义一个评价函数f;对当前的搜索状态进行评估;找出一个最有希望的节点来扩展..先定义下面几个函数的含义：fn=gn+hn 1式中gn表示从初始节点s到当前节点n的最短路径的耗散值；hn 表示从当前节点n到目标节点g的最短路径的耗散值;fn表示从初始节点s经过n到目标节点g的最短路径的耗散值..评价函数的形式可定义如2式所示：fn=gn+hn 2其中n是被评价的当前节点..fn、gn和hn分别表示是对fn、gn和hn3个函数值的估计值..利用评价函数fn=gn+hn来排列OPEN表节点顺序的图搜索算法称为算法A..在A算法中;如果对所有的x;hx<=hx 3成立;则称好hx为hx的下界;它表示某种偏于保守的估计..采用hx 的下界hx为启发函数的A算法;称为A算法..针对八数码问题启发函数设计如下：fn=dn+pn 4其中A算法中的gn根据具体情况设计为dn;意为n节点的深度;而hn设计为图2 A算法流程图pn;意为放错的数码与正确的位置距离之和..由于实际情况中;一个将牌的移动都是单步进行的;没有交换拍等这样的操作..所以要把所有的不在位的将牌;移动到各自的目标位置上;至少要移动从他们各自的位置到目标位置的距离和这么多次;所以最有路径的耗散值不会比该值小;因此该启发函数hn满足A算法的条件..3、A算法流程图;如图24、A算法总结4.1;把起始状态添加到开启列表..4.2;重复如下工作：a 寻找开启列表中f值最低的节点;我们称它为BESTNOEb 把它切换到关闭列表中..c 对相邻的4个节点中的每一个如果它不在开启列表;也不在关闭列表;把它添加到开启列表中..把BESTNODE作为这一节点的父节点..记录这一节点的f和g值如果它已在开启或关闭列表中;用g值为参考检查新的路径是否更好..更低的g值意味着更好的路径..如果这样;就把这一节点的父节点改为BESTNODE;并且重新计算这一节点的f和g值;如果保持开启列表的f值排序;改变之后需要重新对开启列表排序..d 停止把目标节点添加到关闭列表;这时候路径被找到;或者没有找到路径;开启列表已经空了;这时候路径不存在..4.3;保存路径..从目标节点开始;沿着每一节点的父节点移动直到回到起始节点..这就是求得的路径..5、数据结构采用结构体来保存八数码的状态、f和g的值以及该节点的父节点；struct Node{int s33;//保存八数码状态;0代表空格int f;g;//启发函数中的f和g值struct Node next;struct Node previous;//保存其父节点};6、实验结果;如图3所示图3 A算法求解八数码问题实验结果7、源代码//-----------------------------------------------------------------------------//代码：利用A算法求解八数码问题..//八数码问题的启发函数设计为：fn=dn+pn;其中A算法中的gn根据具体情况设计为dn;意为n节点的深度;而hn设计为pn;意为放错的数码与正确的位置距离之和..//后继结点的获取：数码的移动等效为空格的移动..首先判断空格上下左右的可移动性;其次移动空格获取后继结点..//-----------------------------------------------------------------------------include<stdio.h>include<stdlib.h>include<math.h>//八数码状态对应的节点结构体struct Node{int s33;//保存八数码状态;0代表空格int f;g;//启发函数中的f和g值struct Node next;struct Node previous;//保存其父节点 };int open_N=0; //记录Open列表中节点数目//八数码初始状态int inital_s33={2;8;3;1;6;4;7;0;5};//八数码目标状态int final_s33={1;2;3;8;0;4;7;6;5};//------------------------------------------------------------------------//添加节点函数入口;方法：通过插入排序向指定表添加//------------------------------------------------------------------------void Add_Node struct Node head; struct Node p{struct Node q;ifhead->next//考虑链表为空{ q = head->next;ifp->f < head->next->f{//考虑插入的节点值比链表的第一个节点值小p->next = head->next;head->next = p;}else {whileq->next//考虑插入节点x;形如a<= x <=b{ifq->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;}ifq->next == NULL //考虑插入的节点值比链表最后一个元素的值更大q->next = p;}}else head->next = p;}//------------------------------------------------------------------------//删除节点函数入口//------------------------------------------------------------------------void del_Nodestruct Node head; struct Node p{struct Node q;q = head;whileq->next{ifq->next == p{q->next = p->next;p->next = NULL;ifq->next == NULL return;// freep;}q = q->next;}}//------------------------------------------------------------------------//判断两个数组是否相等函数入口//------------------------------------------------------------------------int equalint s133; int s233{int i;j;flag=0;fori=0; i< 3 ; i++forj=0; j< 3 ;j++ifs1ij = s2ij{flag = 1; break;}ifflagreturn 1;else return 0;}//------------------------------------------------------------------------//判断后继节点是否存在于Open或Closed表中函数入口//------------------------------------------------------------------------int exit_Nodestruct Node head;int s33; struct Node Old_Node{struct Node q=head->next;int flag = 0;whileqifequalq->s;s {flag=1;Old_Node->next = q;return 1;}else q = q->next;ifflag return 0;}//-------------------------------------------------------------//计算pn的函数入口//其中pn为放错位的数码与其正确的位置之间距离之和//具体方法：放错位的数码与其正确的位置对应下标差的绝对值之和//------------------------------------------------------------------------int wrong_sumint s33{int i;j;fi;fj;sum=0;fori=0 ; i<3; i++forj=0; j<3; j++{forfi=0; fi<3; fi++forfj=0; fj<3; fj++iffinal_sfifj == sij{sum += fabsi - fi + fabsj - fj;break;}}return sum;}//-------------------------------------------------------------//获取后继结点函数入口//检查空格每种移动的合法性;如果合法则移动空格得到后继结点//------------------------------------------------------------------------int get_successorstruct Node BESTNODE; int direction; struct Node Successor//扩展BESTNODE;产生其后继结点SUCCESSOR{int i;j;i_0;j_0;temp;fori=0; i<3; i++forj=0; j<3; j++Successor->sij = BESTNODE->sij;//获取空格所在位置fori=0; i<3; i++forj=0; j<3; j++ifBESTNODE->sij == 0{i_0 = i; j_0 = j;break;}switchdirection{case 0: ifi_0-1>-1 {temp = Successor->si_0j_0;Successor->si_0j_0 = Successor->si_0-1j_0;Successor->si_0-1j_0 = temp;return 1;}else return 0;case 1: ifj_0-1>-1{temp = Successor->si_0j_0;Successor->si_0j_0 = Successor->si_0j_0-1;Successor->si_0j_0-1 = temp;return 1;}else return 0;case 2: if j_0+1<3{temp = Successor->si_0j_0;Successor->si_0j_0 = Successor->si_0j_0+1;Successor->si_0j_0+1 = temp;return 1;}else return 0;case 3: ifi_0+1<3 {temp = Successor->si_0j_0;Successor->si_0j_0 = Successor->si_0+1j_0;Successor->si_0+1j_0 = temp;return 1;}else return 0;}}//------------------------------------------------------------------------//从OPen表获取最佳节点函数入口//------------------------------------------------------------------------struct Node get_BESTNODEstruct Node Open{return Open->next;}//------------------------------------------------------------------------//输出最佳路径函数入口//------------------------------------------------------------------------void print_Pathstruct Node head{struct Node q; q1;p;int i;j;count=1;p = struct Node mallocsizeofstruct Node;//通过头插法变更节点输出次序p->previous = NULL;q = head;whileq{q1 = q->previous;q->previous = p->previous;p->previous = q;q = q1;}q = p->previous;whileq{ifq == p->previousprintf"八数码的初始状态：\n";else ifq->previous == NULLprintf"八数码的目标状态：\n"; else printf"八数码的中间态%d\n";count++;fori=0; i<3; i++forj=0; j<3; j++{printf"%4d";q->sij;ifj == 2printf"\n";}printf"f=%d; g=%d\n\n";q->f;q->g;q = q->previous;}}//------------------------------------------------------------------------//A子算法入口:处理后继结点//------------------------------------------------------------------------void sub_A_algorithmstruct Node Open; struct Node BESTNODE; struct Node Closed;struct Node Successor{struct Node Old_Node = struct Node mallocsizeofstruct Node;Successor->previous = BESTNODE;//建立从successor返回BESTNODE 的指针Successor->g = BESTNODE->g + 1;//计算后继结点的g值//检查后继结点是否已存在于Open和Closed表中;如果存在：该节点记为old_Node;比较后继结点的g值和表中old_Node节点//g值;前者小代表新的路径比老路径更好;将Old_Node的父节点改为BESTNODE;并修改其f;g值;后者小则什么也不做..//即不存在Open也不存在Closed表则将其加入OPen表;并计算其f值if exit_NodeOpen; Successor->s; Old_Node {ifSuccessor->g < Old_Node->g{Old_Node->next->previous = BESTNODE;//将Old_Node的父节点改为BESTNODEOld_Node->next->g = Successor->g;//修改g值Old_Node->next->f = Old_Node->g + wrong_sumOld_Node->s;//修改f值//排序~~~~~~~~~~~~~~~~~~del_NodeOpen; Old_Node;Add_NodeOpen; Old_Node;}}else if exit_NodeClosed; Successor->s; Old_Node{ifSuccessor->g < Old_Node->g{Old_Node->next->previous = BESTNODE;Old_Node->next->g = Successor->g;Old_Node->next->f = Old_Node->g + wrong_sumOld_Node->s;//排序~~~~~~~~~~~~~~~~~~del_NodeClosed; Old_Node;Add_NodeClosed; Old_Node;}}else {Successor->f = Successor->g + wrong_sumSuccessor->s;Add_NodeOpen; Successor;open_N++;}}//------------------------------------------------------------------------//A算法入口//八数码问题的启发函数为：fn=dn+pn//其中A算法中的gn根据具体情况设计为dn;意为n节点的深度;而hn设计为pn;//意为放错的数码与正确的位置距离之和//------------------------------------------------------------------------void A_algorithmstruct Node Open; struct Node Closed //A算法{int i;j;struct Node BESTNODE; inital; Successor;inital = struct Node mallocsizeofstruct Node;//初始化起始节点fori=0; i<3; i++forj=0; j<3; j++inital->sij = inital_sij;inital->f = wrong_suminital_s;inital->g = 0;inital->previous = NULL;inital->next = NULL;Add_NodeOpen; inital;//把初始节点放入OPEN表open_N++;while1{ifopen_N == 0{printf"failure"; return;}else {BESTNODE = get_BESTNODEOpen;//从OPEN表获取f值最小的BESTNODE;将其从OPEN表删除并加入CLOSED表中del_NodeOpen; BESTNODE;open_N--;Add_NodeClosed; BESTNODE;ifequalBESTNODE->s; final_s {//判断BESTNODE是否为目标节点printf"success\n";print_PathBESTNODE;return;}//针对八数码问题;后继结点Successor的扩展方法：空格二维数组中的0上下左右移动;//判断每种移动的有效性;有效则转向A子算法处理后继节点;否则进行下一种移动else{Successor = struct Node mallocsizeofstruct Node; Successor->next = NULL;ifget_successorBESTNODE; 0; Successorsub_A_algorithm Open; BESTNODE; Closed; Successor;Successor = struct Node mallocsizeofstruct Node; Successor->next = NULL;ifget_successorBESTNODE; 1; Successorsub_A_algorithm Open; BESTNODE; Closed; Successor;Successor = struct Node mallocsizeofstruct Node; Successor->next = NULL;ifget_successorBESTNODE; 2; Successorsub_A_algorithm Open; BESTNODE; Closed; Successor;Successor = struct Node mallocsizeofstruct Node; Successor->next = NULL;ifget_successorBESTNODE; 3; Successorsub_A_algorithm Open; BESTNODE; Closed; Successor;}}}}//------------------------------------------------------------------------//main函数入口//定义Open和Closed列表..Open列表：保存待检查节点..Closed列表：保存不需要再检查的节点//------------------------------------------------------------------------void main{struct Node Open = struct Node mallocsizeofstruct Node;struct Node Closed = struct Node mallocsizeofstruct Node;Open->next = NULL ; Open->previous = NULL;Closed->next =NULL; Closed->previous = NULL;A_algorithmOpen; Closed;}三、实验体会通过这次实验;使我对启发式搜索算法有了更进一步的理解;特别是估计函数hn所起到的巨大重用..一个好的估计函数对于启发式搜索算法来说是十分关键的..。

二、程序运行测试A*算法求解八数码问题一、详细设计说明1.评价函数以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。

距离的定义为: “某将牌行下标与目标位置行下标之差的绝对值 + 列下标与目标位置列下标之差的绝对值”。

距离越小, 该节点的效果越好。

某个状态所有将牌到目标位置的距离之和用“h值”表示。

2.主要函数2.1countH（state & st）;countH函数功能是计算st状态的h值。

2.2计算过程中将会用到rightPos数组, 数组里记录的是目标状态下, 0~9每个将牌在九宫格里的位置（位置 = 行下标 * 3 + 列下标）。

2.3f（state * p）;f()=h()+level2.4look_up_dup(vector<state*> & vec, state * p);2.5在open表或close表中, 是否存在指定状态p, 当找到与p完全相等的节点时, 退出函数。

2.6search(state & start)；在open表不为空时, 按f值由小到大对open表中元素进行排序。

调用findZero()函数找到0值元素的位置。

空格可以向上下左右四个方向移动, 前提是移动后不能越过九宫格的边界线。

确定某方向可走后, 空格移动一步, 生成状态p’。

2.7此时, 检查open表中是否已有p’, 若有, 更新p’数据；检查close表中是否已有p’, 若有, 将p’从close表中删除, 添加到open表中。

2.8重复的执行这个过程, 直到某状态的h值为零。

2.9dump_solution(state * q)；在终端输出解路径。

// A*算法八数码问题#include"stdafx.h"#include<iostream>#include<vector>#include<time.h>#include<algorithm>using namespace std;const int GRID = 3; //Grid表示表格的行数(列数), 这是3*3的九宫格int rightPos[9] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 };//目标状态时, 若p[i][j]=OMG,那么3*i+j = rightPos[OMG]struct state{int panel[GRID][GRID];int level; //记录深度int h;state * parent;state(int level) :level(level){}bool operator == (state & q){//判断两个状态是否完全相等（对应位置元素相等）, 完全相等返回true,否则返回falsefor (int i = 0; i<GRID; i++){for (int j = 0; j<GRID; j++){if (panel[i][j] != q.panel[i][j])return false;}}return true;}state & operator = (state & p){ //以状态p为当前状态赋值, 对应位置元素相同for (int i = 0; i<GRID; i++){for (int j = 0; j<GRID; j++){panel[i][j] = p.panel[i][j];}}return *this;}};void dump_panel(state * p){ //将八数码按3*3矩阵形式输出for (int i = 0; i<GRID; i++){for (int j = 0; j<GRID; j++)cout << p->panel[i][j] << " ";cout << endl;}}int countH(state & st){ //给定状态st, 计算它的h值。

#include "Stdio.h"#include "Conio.h"#include "stdlib.h"#include "math.h"void Copy_node(struct node *p1,struct node *p2);void Calculate_f(int deepth,struct node *p);void Add_to_open(struct node *p);void Add_to_closed(struct node *p);void Remove_p(struct node *name,struct node *p);int Test_A_B(struct node *p1,struct node *p2);struct node * Search_A(struct node *name,struct node *temp); void Print_result(struct node *p);struct node // 定义8数码的节点状态{int s[3][3]; //当前8数码的状态int i_0; //当前空格所在行号int j_0; //当前空格所在列号int f; //当前代价值int d; //当前节点深度int h; //启发信息，采用数码"不在位"距离和struct node *father; //指向解路径上该节点的父节点struct node *next; //指向所在open或closed表中的下一个元素} ;struct node s_0={{2,8,3,1,6,4,7,0,5},2,1,0,0,0,NULL,NULL}; //定义初始状态struct node s_g={{1,2,3,8,0,4,7,6,5},1,1,0,0,0,NULL,NULL}; //定义目标状态struct node *open=NULL; //建立open表指针struct node *closed=NULL; //建立closed表指针int sum_node=0; //用于记录扩展节点总数//***********************************************************//********************** **********************//********************** 主函数开始**********************//********************** **********************//***********************************************************void main(){int bingo=0; //定义查找成功标志，bingo=1，成功struct node s; //定义头结点sstruct node *target,*n,*ls,*temp,*same; //定义结构体指针Copy_node(&s_0,&s); //复制初始状s_0态给头结点s Calculate_f(0,&s); //计算头结点的代价值Add_to_open(&s); //将头结点s放入open表while(open!=NULL) //只要open表不为空，进行以下循环{n=open; //n指向open表中当前要扩展的元素ls=open->next;Add_to_closed(n);open=ls; //将n指向的节点放入closed表中if(Test_A_B(n,&s_g)) //当前n指向节点为目标时，跳出程序结束；否则，继续下面的步骤{bingo=1;break;}elseif(n->j_0>=1) //空格所在列号不小于1,可左移{temp=n->father;if(temp!=NULL&&temp->i_0==n->i_0&&temp->j_0-1==n->j_0) //新节点与其祖父节点相同;else //新节点与其祖父节点不同，或其父节点为起始节点{temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间Copy_node(n,temp); //拷贝n指向的节点状态temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0-1]; //空格左移temp->s[temp->i_0][temp->j_0-1]=0;temp->j_0--;temp->d++;Calculate_f(temp->d,temp); //修改新节点的代价值temp->father=n; //新节点指向其父节点if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表{Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else;}else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表{Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else ;}else //新节点为完全不同的新节点，加入open表{Add_to_open(temp);sum_node++;}}}//end左移if(n->j_0<=1) //空格所在列号不大于1,可右移{temp=n->father;if(temp!=NULL&&temp->i_0==n->i_0&&temp->j_0+1==n->j_0) //新节点与其祖父节点相同;else //新节点与其祖父节点不同，或其父节点为起始节点{temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间Copy_node(n,temp); //拷贝p指向的节点状态temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0+1]; //空格右移temp->s[temp->i_0][temp->j_0+1]=0;temp->j_0++;temp->d++;Calculate_f(temp->d,temp); //修改新节点的代价值temp->father=n; //新节点指向其父节点if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表{Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else;}else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表{Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else ;}else //新节点为完全不同的新节点，加入open表{Add_to_open(temp);sum_node++;}}}//end右移if(n->i_0>=1) //空格所在列号不小于1,上移{temp=n->father;if(temp!=NULL&&temp->i_0==n->i_0-1&&temp->j_0==n->j_0) //新节点与其祖父节点相同;else //新节点与其祖父节点不同，或其父节点为起始节点{temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间Copy_node(n,temp); //拷贝p指向的节点状态temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0-1][temp->j_0];//空格上移temp->s[temp->i_0-1][temp->j_0]=0;temp->i_0--;temp->d++;Calculate_f(temp->d,temp); //修改新节点的代价值temp->father=n; //新节点指向其父节点if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表{Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else;}else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表{Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else ;}else //新节点为完全不同的新节点，加入open表{Add_to_open(temp);sum_node++;}}}//end上移if(n->i_0<=1) //空格所在列号不大于1,下移{temp=n->father;if(temp!=NULL&&temp->i_0==n->i_0+1&&temp->j_0==n->j_0) //新节点与其祖父节点相同;else //新节点与其祖父节点不同，或其父节点为起始节点{temp=(struct node *)malloc(sizeof(struct node)); //给新节点分配空间Copy_node(n,temp); //拷贝p指向的节点状态temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0+1][temp->j_0]; //空格下移temp->s[temp->i_0+1][temp->j_0]=0;temp->i_0++;temp->d++;Calculate_f(temp->d,temp); //修改新节点的代价值temp->father=n; //新节点指向其父节点if(same=Search_A(closed,temp)) //在closed表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表{Remove_p(closed,same); //从closed表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else;}else if(same=Search_A(open,temp)) //在open表中找到与新节点状态相同的节点{if(temp->f<same->f) //temp指向的节点,其代价比open表中相同状态节点代价小，加入open表{Remove_p(open,same); //从open表中删除与temp指向节点状态相同的节点Add_to_open(temp);sum_node++;}else ;}else //新节点为完全不同的新节点，加入open表{Add_to_open(temp);sum_node++;}}}//end下移}if(bingo=1) Print_result(n); //输出解路径else printf("问题求解失败！");}//主函数结束//************************************************************************* //********************** ********************** //********************** 计算某个节点状态的代价值********************** //********************** ********************** //*************************************************************************void Calculate_f(int deepth,struct node *p){int i,j,temp;temp=0;for(i=0;i<=2;i++) //计算所有"不在位"数码的距离和{for(j=0;j<=2;j++){if((p->s[i][j])!=(s_g.s[i][j]))temp++;}}p->h=temp;p->f=deepth+p->h;}//*************************************************************************//********************** **********************//********************** 添加p指向的节点到open表中********************** //********************** **********************//*************************************************************************void Add_to_open(struct node *p){struct node *p1,*p2;p1=open; //初始时p1指向open表首部p2=NULL;if(open==NULL) //open表为空时，待插入节点即为open表第一个元素，open 指向该元素{p->next=NULL;open=p;}else //open表不为空时，添加待插入节点，并保证open表代价递增的排序{while(p1!=NULL&&p->f>p1->f){p2=p1; //p2始终指向p1指向的前一个元素p1=p1->next;}if(p2==NULL) //待插入节点为当前open表最小{p->next=open;open=p;}else if(p1==NULL) //待插入节点为当前open表最大{p->next=NULL;p2->next=p;}else //待插入节点介于p2、p1之间{p2->next=p;p->next=p1;}}}//***************************************************************************//********************** **********************//********************** 添加p指向的节点到closed表中**********************//********************** **********************//***************************************************************************void Add_to_closed(struct node *p){if(closed==NULL) //closed表为空时，p指向节点为closed表第一个元素，closed{p->next=NULL;closed=p;}else //closed表不为空时，直接放到closed表首部{p->next=closed;closed=p;}}//************************************************************************************* *************//********************************************//********************** 在open表或closed表中搜索和temp指向的节点相同的节点**********************//********************************************//*************************************************************************************struct node * Search_A(struct node *name,struct node *temp){struct node *p1;p1=name; //p1指向open表或closed表while(p1!=NULL){if(Test_A_B(p1,temp)) //找到相同的节点，返回该节点地址return p1;elsep1=p1->next;}return NULL;}//************************************************************************************* **********//********************************************//********************** 判断两个节点状态是否相同，相同则返回1，否则返回0 **********************//********************************************//************************************************************************************* **********int Test_A_B(struct node *p1,struct node *p2){int i,j,flag;flag=1;for(i=0;i<=2;i++)for(j=0;j<=2;j++){if((p2->s[i][j])!=(p1->s[i][j])) { flag=0; return flag; }else ;}return flag;}//******************************************************************************//********************** **********************//********************** 从open表或closed表删除指定节点********************** //********************** **********************//******************************************************************************void Remove_p(struct node *name,struct node *p){struct node *p1,*p2;p1=NULL;p2=NULL;if(name==NULL) //如果name指向的链表为空，则不需要进行删除return;else if(Test_A_B(name,p)&&name->f==p->f) //指定节点为name指向的链表的第一个元素{open=name->next;name->next=NULL;return;}else{p2=name;p1=p2->next;while(p1){if(Test_A_B(p1,p)&&p1->f==p->f) //找到指定节点{p2->next=p1->next;return;}else{p2=p1; //p2始终指向p1指向的前一个元素p1=p1->next;}}return;}}//************************************************************************************* *//********************************************//********************** 将p1指向的节点状态拷贝到p2指向的节点中**********************//********************************************//************************************************************************************* *void Copy_node(struct node *p1,struct node *p2){int i,j;for(i=0;i<=2;i++){for(j=0;j<=2;j++){ p2->s[i][j]=p1->s[i][j]; }}p2->i_0=p1->i_0;p2->j_0=p1->j_0;p2->f=p1->f;p2->d=p1->d;p2->h=p1->h;p2->next=p1->next;p2->father=p1->father;}//*********************************************************** //********************** ********************** //********************** 输出结果********************** //********************** ********************** //***********************************************************void Print_result(struct node *p){struct node *path[100];struct node *temp,*temp_father;int i,j,k;for(i=0;i<=99;i++) //初始化路径指针数组path[i]=0;temp=p;printf("总共扩展%d 个节点\n",sum_node);printf("总共扩展%d 层\n",temp->d);printf("解路径如下：\n");for(i=p->d;i>=0;i--) //存储解路径上各节点的地址{path[i]=temp;temp=temp->father;}for(k=0;k<=p->d;k++) //输出解路径{temp=path[k]; //建立节点指点指针printf("第%d步",temp->d);if(k-1>=0) //输出移动策略{temp_father=path[k-1];if(temp->i_0<temp_father->i_0) printf("->上移\n");if(temp->i_0>temp_father->i_0) printf("->下移\n");if(temp->j_0<temp_father->j_0) printf("->左移\n");if(temp->j_0>temp_father->j_0) printf("->右移\n");}elseprintf("\n");printf("当前节点状态为：\n");for(i=0;i<=2;i++){for(j=0;j<=2;j++){printf("%d ",temp->s[i][j]);}printf("\n");}printf("\n");}}THANKS !!!致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求欢迎您的下载，资料仅供参考。

A*算法解决八数码问题1 问题描述什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。

与空位相邻的棋子可以滑动到空位中。

游戏的目的是要达到一个特定的目标状态。

标注的形式化如下：问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

解决方案介绍算法思想(估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。

估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n 节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。

启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有 h ( t ) = 0，对于结点m和n （n 是m的子结点）有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。

*文件Chess.h,包含必要的数据结构,全局变量和类声明*/#ifndef _YLQ_CHESS_#define _YLQ_CHESS_#include <algorithm>#include <iostream>#include <vector>#ifndef N#define N 3#endif#define BLANK 0static int g_iId=1;typedef struct tagNode{int node[N][N];int iF,iH,iG;int id,idParent;}NODE,*PNODE;typedef std::vector<NODE> OPEN;#define CLOSED OPEN#define SUCCERSSOR OPENclass Chess{public:Chess(NODE const &nstar,NODE const &nend); private:OPEN m_vOpen,m_vClosed;NODE m_nStart,m_nEnd;bool NodeEuqal(NODE node1,NODE node2);bool NodeExist(NODE node);bool InOpen(NODE node,int &index);bool InClose(NODE node,int &index);SUCCERSSOR ExplortNode(NODE node); protected:virtual int CaculateHV(NODE &node);//计算h值和f值public:bool Algorithms();void Show(int it);//it=1展示Open,2->Closed};#endif*文件Chess.cpp,包含算法实现*/#include "Chess.h"#include <MA TH.H>bool comp(const NODE &n1,const NODE &n2){return n1.iF>n2.iF;}void Chess::Show(int tp){SUCCERSSOR::iterator it,iend;if (tp==1) {it=m_vOpen.begin();iend=m_vOpen.end();}else{it=m_vClosed.begin();iend=m_vClosed.end();}for (;it!=iend;it++){printf("iF=%d;iG=%d;iH=%d\n",(PNODE)it->iF,(PNODE)it->iG,(PNODE)it->iH);printf("id=%d;idParent=%d\n",(PNODE)it->id,(PNODE)it->idParent);for(int i=0;i<N;i++){for (int j=0;j<N;j++){printf("%d ",(PNODE)it->node[i][j]);}std::cout<<std::endl;}}}Chess::Chess(const NODE &nstar,const NODE &nend){m_nStart = nstar;m_nEnd = nend;m_nStart.idParent=0;//初始结点的父节点设为0m_nStart.id = 1;m_nStart.iG=0;//初始结点G设为0,再次结点扩展一次就+1( 表示深度);CaculateHV(m_nStart);//初始化开始结点h和f以及gm_vOpen.push_back(m_nStart);}int Chess::CaculateHV(NODE &node){//用位置差来计算h值node.iH=0;for (int i=0;i<N;i++){for (int j=0;j<N;j++){bool bget=false;for (int m=0;m<N;m++){for (int n=0;n<N;n++){if (node.node[m][n] == m_nEnd.node[i][j]) {node.iH+=abs(m-i)+abs(n-j);bget=true;break;}}if (bget)break;}}}node.iF =node.iG+node.iH;return node.iH;}bool Chess::NodeEuqal(NODE node1,NODE node2){int sum=0;for (int i=0;i<N;i++)for (int j=0;j<N;j++){if (node1.node[i][j] == node2.node[i][j]) {sum++;}}if (sum==N*N) {return true;}elsereturn false;}bool Chess::InOpen(NODE node,int &index){//查找node是否在Open表中,是的返回true并返回指针位置index OPEN::iterator itOpen=m_vOpen.begin();index=0;for (;itOpen!=m_vOpen.end();itOpen++){if (NodeEuqal(node,*(PNODE)itOpen->node)) {return true;}index++;}return false;}bool Chess::InClose(NODE node,int &index){//查找node是否在InClose表中,是的返回true并返回指针位置index CLOSED::iterator itClosed=m_vClosed.begin();index=0;for (;itClosed!=m_vClosed.end();itClosed++){if (NodeEuqal(node,*(PNODE)itClosed->node)) {return true;}index++;}return false;}bool Chess::NodeExist(NODE node){int i;if (InOpen(node,i) || InClose(node,i)) {return true;}return false;}SUCCERSSOR Chess::ExplortNode(NODE node){//扩展结点,并插入到SUCCERSSOR队列中int i,j;SUCCERSSOR temp;for (i=0;i<N;i++)for (j=0;j<N;j++)if (node.node[i][j]==BLANK){//找到空格,开始扩张,按照空格依次往上下左右扩展,判断其合法性if (j>0) {NODE ntemp=node;ntemp.node[i][j]=ntemp.node[i][j-1];ntemp.node[i][j-1]=BLANK;g_iId++;ntemp.id=g_iId;ntemp.idParent = node.id;ntemp.iG=ntemp.iG+1;CaculateHV(ntemp);temp.push_back(ntemp);}if (j<N-1) {NODE ntemp=node;ntemp.node[i][j]=ntemp.node[i][j+1];ntemp.node[i][j+1]=BLANK;g_iId++;ntemp.id=g_iId;ntemp.idParent = node.id;ntemp.iG=ntemp.iG+1;CaculateHV(ntemp);temp.push_back(ntemp);}if (i>0) {NODE ntemp=node;ntemp.node[i][j]=ntemp.node[i-1][j];ntemp.node[i-1][j]=BLANK;g_iId++;ntemp.id=g_iId;ntemp.idParent = node.id;ntemp.iG=ntemp.iG+1;CaculateHV(ntemp);temp.push_back(ntemp);}if (i<N-1) {NODE ntemp=node;ntemp.node[i][j]=ntemp.node[i+1][j];ntemp.node[i+1][j]=BLANK;g_iId++;ntemp.id=g_iId;ntemp.idParent = node.id;ntemp.iG=ntemp.iG+1;CaculateHV(ntemp);temp.push_back(ntemp);}}return temp;}bool Chess::Algorithms(){NODE nTemp;while (m_vOpen.size()!=0){std::sort(m_vOpen.begin(),m_vOpen.end(),comp);//取出f值最小的进行扩展nTemp = *((PNODE)(m_vOpen.end()-1));m_vOpen.pop_back();m_vClosed.push_back(nTemp);if (NodeEuqal(nTemp,m_nEnd))return true;SUCCERSSOR stemp=ExplortNode(nTemp);SUCCERSSOR::iterator isuc=stemp.begin();for (;isuc!=stemp.end();isuc++){int indexOp,indexCl=0;NODE suc=*(PNODE)isuc,*old;if (InOpen(suc,indexOp)) {old = (PNODE)(m_vOpen.begin()+indexOp);if (suc.iG<old->iG){//若G值比原先的小,则直接修改old结点old->iG = suc.iG;//修改其父节点,指向suc结点old->idParent = suc.idParent;old->iF = old->iG+old->iH;}}else if (InClose(suc,indexCl)){old = (PNODE)(m_vClosed.begin()+indexCl);if (suc.iG<old->iG){//若G值比原先的小,则直接修改old结点old->iG = suc.iG;//修改其父节点,指向suc结点old->idParent = suc.idParent;old->iF = old->iG+old->iH;}}else{m_vOpen.push_back(suc);}}}return false;}/**文件main.cpp,如何使用该类*/#include "Chess.h"#include <IOSTREAM>using namespace std;NODE nStart={{2,8,3,0,1,4,7,6,5},0,0,0,g_iId,0};NODE nEnd={{1,2,3,8,0,4,7,6,5},0,0,0,0,0};int main(int argc,char *argv){Chess *chess=new Chess(nStart,nEnd);if (chess->Algorithms()){cout<<"搜索成功:\n";chess->Show(2);}return 0;}。

A*算法解决八数码问题1 问题描述1.1什么是八数码问题×八数码游戏包括一个33的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。

与空位相邻的棋子可以滑动到空位中。

游戏的目的是要达到一个特定的目标状态。

标注的形式化如下：123456781.2问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

1.3解决方案介绍1.3.1 算法思想估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。

估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。

1.3.2 启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有h ( t ) = 0，对于结点m和n （n 是m的子结点）有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。

A*算法解决八数码问题1 问题描述什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。

与空位相邻的棋子可以滑动到空位中。

游戏的目的是要达到一个特定的目标状态。

标注的形式化如下：问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。

初始状态：任何状态都可以被指定为初始状态。

操作符：用来产生4个行动（上下左右移动）。

目标测试：用来检测状态是否能匹配上图的目标布局。

路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。

现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。

解决方案介绍算法思想(估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。

估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n) 是节点n从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n 节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。

保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。

估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。

但能得到最优解。

如果估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。

启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有 h ( t ) = 0，对于结点m和n （n 是m的子结点）有h ( m ) – h ( n ) <= 1 = Cost ( m, n ) 满足单调限制条件。

人工智能实验一报告题目：采用A*算法解决八数码问题成员：李文、郭弯弯学号：、专业：计算机科学与技术完成日期： 2016/04/09一、实验要求、目的及分工1.1实验要求使用A*算法实现八数码问题，并用图形界面展示。

1.2实验目的a. 熟悉人工智能系统中的问题求解过程；b. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；c. 熟悉对八数码问题的建模、求解及编程语言的应用。

1.3实验分工我们小组共两个人，共同查找背景资料，李文同学主要负责源代码，郭弯弯同学主要负责实验报告以及演示文稿的完成。

二、实验问题2.1问题描述所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8 的八块正方形数码牌任意地放在一块3×3 的数码盘上。

放牌时要求不能重叠。

于是，在3×3 的数码盘上出现了一个空格。

现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。

空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如下图所示：(a) 初始状态 (b) 目标状态图1 八数码问题示意图2.2问题解释首先，八数码问题包括一个初始状态(START) 和目标状态(TRAGET)，所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态：（START>STATE1>STATE2>...>TARGET ）这个状态是否存在就是我们要解决的第一个问题；第二个问题是我们要求出走的路径是什么。

2.3八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。

把3×3的棋盘写成一个二维向量。

我们可以设定初始状态：<1,5,2,4,0,3,6,7,8>后继函数：按照某种规则移动数字得到的新向量。

例如：<1,5,2,4,0,3,6,7,8> <1,0,2,4,5,3,6,7,8>路径耗散函数：规定每次移动代价为1，即每执行一条规则后总代价加1。

一、实验容和要求八数码问题：在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)。