采用A算法解决八数码问题

1、人工智能实验一报告题目：采用 A* 算法解决八数码问题姓名：张博涵学号：081110317专业：信息与计算科学提交日期：2014-05-22目录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 实验结果 - 5 -3.4 系统中间及最终输出结果 - 7 -4 参考文献 - 8 -5 附录源代码及其注释 - 8 -1 问

2、题描述所谓八数码问题是指这样一种游戏：将分别标有数字 1，2，3， 8 的八 块正方形数码牌任意地放在一块 3×3 的数码盘上。 放牌时要求不能重叠。 于是， 在 3× 3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数 码牌与空格交换的原则， 不断移动该空格方块以使其和相邻的方块互换， 直至达 到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4个方向可移动， 在四个角落上有 2个方向可移动， 在其他位置上有 3个方向可移动， 问题描述如下 图1-1所示：1.1 待解决问题的解释首先，八数码问题包括一个初始状态 (START) 和目标状态 (END

3、) ，所谓解决 八数码问题就是在两个状态间寻找一系列可过渡状态： (START>STATE1>STATE2>.>END) 这个状态是否存在就是我们要解决的第一个问题： Q1：每一个状态及每一次操 作的表示方法？有许多表示方法，比如一个 3*3 的八数码盘可以压缩成一个 int 值表示，但不适用于 15 puzzle或大于 8 的 puzzle 问题。如果对空间要求很高，应 该还可以再压缩。本文采用一个 int 表示的方法。表示方法如下：由于 int 的表 示范围大于 1e9，所以我们取一个 int 的低 9 位，为了方便寻找空格的位置， int 的 个位我们用来放空格的

4、位置( 19)。而前 8 位，按照行从上到下，列从左到右的 顺序依次记录对应位置上的数字。1.2 问题的搜索形式描述八数码问题形式化描述：初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把 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,2,3,4,5,6,7,8,0>是目标

5、状态？ 路径耗散函数：每次移动代价为 1，每执行一条规则后总代价加 1。1.3 解决方案介绍(原理)该问题是一个搜索问题。 它是一种状态到另一种状态的变换。 要解决这个问 题，必须先把问题转化为数字描述。 由于八数码是一个 3*3 的矩阵， 但在算法中 不实用矩阵， 而是将这个矩阵转化为一个一维数组， 使用这个一维数组来表示八 数码，但是移动时要遵守相关规则。(1) 可用如下形式的规则来表示数字通过空格进行移动：<a1,a2,a3,a4,a5,a6,a7,a8,a9> <b1,b2,b3,b4,b5,b6,b7,b8,b9>(2) 共 24 条移动规则，对应与每个位置的

6、移动规则。(3) 搜索顺序举例：<1>优先移动行数小的棋子 (数字 )<2>同一行中优先移动列数大的棋子(4) 约束规则：不使离开既定位置的数字数增加八数码的节点扩展应当遵循棋子的移动规则。 按规则，每一次可以将一个与 空格相邻的棋子移动到空格中， 实际上也可以看做空格的相反方向移动。 空格的 移动方向可以是上下左右， 当然不能出边界。 棋子的位置， 也就是保存状态的数 组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格 向右，下，左，上移动后，新位置是原位置分别加上1,3，-1， -3。在这里，空格可以用任意数字表示。操作本文用 u r d l 分

7、别表示空格的向上向右向下向左 四个操作。图的搜索策略：经分析， 8 数码问题的搜索策略共有： 1.广度优先搜索、 2. 深度优先搜索、 3.有界深度优先搜索、 4.最好优先搜索、 5.局部择优搜索，等等。 其中广度优先搜索法是可采纳的， 有界深度优先搜索法是不完备的， 最好优先和 局部择优搜索法是启发式搜索法。本实验采用启发式 A* 搜索算法来实现。2 算法介绍问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。 这个寻 找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。 广度 优先是从初始状态一层一层向下找， 直到找到目标为止。 深度优先是按照一定的 顺序前查找完一

8、个分支，再查找另一个分支，以至找到目标为止。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估， 得到最 好的位置，再从这个位置进行搜索直到目标。 这样可以省略大量无畏的搜索路径， 提高了效率。2.1A* 搜索算法一般介绍A* 算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数 评估每次的的决策的价值， 决定先尝试哪一种方案， 这样可以极大的优化普通的 广度优先搜索。一般来说，从出发点 (A)到目的地 (B)的最短距离是固定的，我们 可以写一个函数 judge() 估计 A 到 B 的最短距离，如果程序已经尝试着从出 发点 A 沿着某条路线移动到了 C 点 , 那么我们认为

9、这个方案的 A B 间的估 计距离为 A 到 C 实际已经行走了的距离 H 加上用 judge() 估计出的 C 到 B 的距离。如此，无论我们的程序搜索展开到哪一步， 都会算出一个评估值， 每一次决 策后，将评估值和等待处理的方案一起排序， 然后挑出待处理的各个方案中最有 可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地， 或所有方案都尝试过却没有找到一条通向目的地的路径则结束。A* 算法是一个可采纳的最好优先算法。 A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n) 这里， f'(n) 是估价函数， g'(n)

10、是起点到终点的最短路径值， h'(n)是 n 到目标的最 断路经的启发值。 由于这个 f'(n)其实是无法预先知道的， 所以我们用前面的估价 函数 f(n)做近似。 g(n)代替 g'(n)，但 g(n)>=g'(n)才可(大多数情况下都是满足的， 可以不用考虑)，h(n)代替 h'(n)，但 h(n)<=h'(n)才可。可以证明应用这样的估价 函数是可以找到最短路径的，也就是可采纳的。2.2 算法伪代码首先定义两个表， open 表用于存放已经生成，且已用启发式函数进行过估 计或评价，但尚未产生它们的后继节点的那些结点，这些结点也称

11、未考察结点；closed表用于存放已经生成， 且已考察过的结点。 设 S0为初态， Sg 为目标状态。 具体过程如下：(1) 把 S0 放入 open表，记为 f=h，令 closed为空表；(2) 重复下列过程，直至找到目标结点为止。若 open 为空表，则失败；(3) 选取 open 表中未设置过的具有最小 f 值的结点为最佳节点，并放入 closed表 中(4) 若最佳节点不是目标节点，则扩展之，产生后继节点。(5) 对每个后继结点进行下列过程：? 建立从该后继结点返回最佳节点的指针；? 计算 g(后继结点) =g(最佳节点) +k (最佳节点，后继结点) ；? Ss：如果该后继节点 o

12、pen，则称此节点为 old ，并把它添加至最佳节点 的后继节点中? 比较新旧路径代价，如果个 g(后继节点) <g(old), 则重新确定 old 的父 亲节点? 若至 old 节点的代价比较低或一样，则停止扩展节点? 若后继节点不再 open 表中，则看其是否在 closed中? 若后继节点在 open 表中，则转向 Ss；? 若后继节点既不在 open 表中，又不在 closed 表中，则把它放入 open 表 中，并填入最佳节点的后裔表，然后走下一步(6) 计算 f 值(7) GO LOOP3 算法实现3.1 实验环境与问题规模(1)实验环境： Windows XP(2)实验编程

13、工具： VC+6.03.2 数据结构1) 定义状态图中的结点数据结构typedef struct Nodestatus data;/结点所存储的状态struct Node *parent;/ 指向结点的父亲结点struct SpringLink *child;/ 指向结点的后继结点struct Node *next;/ 指向 open 或者 closed 表中的后一个结点int fvalue;/ 结点的总的路径int gvalue;/ 结点的实际路径int hvalue;/ 结点的到达目标的苦难程度NNode , *PNode;2) 定义存储指向结点后继结点的指针的地址typedef stru

14、ct SpringLinkstruct Node *pointData;/ 指向结点的指针struct SpringLink *next;/ 指向兄第结点SPLink , *PSPLink;3) 初始化一个空链表void initLink(PNode &Head)3.3 实验结果经测试，程序运行良好，结果正确。输入测试数据，初试状态 <0,1,2,3,4,5,6,7， 8>，目标状态 <,1,4,2,3,5,8,6,7,0>，运行结果有解，共经过四步。3.4 系统中间及最终输出结果图 3-1 程序运行中间结果图 3-2 程序运行最终结果4 参考文献1Artifi

15、cial intelligence :;a modern approach 人工智能 : 一种现代方法 作者： Russell, Stuart J. 出版社：清华大学出版社2 CSDN 博客5 附录源代码及其注释#include "iostream"#include "stdlib.h"#include "conio.h"#define size 3using namespace std;/定义二维数组来存储数据表示某一个特定状态typedef int statussizesize;struct SpringLink;/定义状态图中的

16、结点数据结构typedef struct Nodestatus data;/结点所存储的状态struct Node *parent;/ 指向结点的父亲结点struct SpringLink *child;/ 指向结点的后继结点struct Node *next;/ 指向 open 或者 closed 表中的后一个结点int fvalue;/ 结点的总的路径int gvalue;/ 结点的实际路径int hvalue;/ 结点的到达目标的苦难程度NNode , *PNode;/定义存储指向结点后继结点的指针的地址typedef struct SpringLinkstruct Node *poin

17、tData;/ 指向结点的指针struct SpringLink *next;/ 指向兄第结点 SPLink , *PSPLink;PNode open;PNode closed;/开始状态与目标状态status startt = 0,1,2,3,4,5,6,7,8;status target = 1,4,2,3,5,8,6,7,0;/初始化一个空链表void initLink(PNode &Head)Head = (PNode)malloc(sizeof(NNode);Head->next = NULL;/判断链表是否为空 bool isEmpty(PNode Head) if

18、(Head->next = NULL) return true;elsereturn false;/从链表中拿出一个数据void popNode(PNode &Head , PNode &FNode) if(isEmpty(Head)FNode = NULL; return;FNode = Head->next;Head->next = Head->next->next;FNode->next = NULL;/向结点的最终后继结点链表中添加新的子结点 void addSpringNode(PNode &Head , PNode new

19、Data) PSPLink newNode = (PSPLink)malloc(sizeof(SPLink); newNode->pointData = newData;newNode->next = Head->child; Head->child = newNode;/释放状态图中存放结点后继结点地址的空间void freeSpringLink(PSPLink &Head)PSPLink tmm;while(Head != NULL)tmm = Head;Head = Head->next;free(tmm);/释放 open表与 closed 表中的

20、资源 void freeLink(PNode &Head)PNode tmn;tmn = Head; Head = Head->next; free(tmn);while(Head != NULL) /首先释放存放结点后继结点地址的空间 freeSpringLink(Head->child);tmn = Head;Head = Head->next; free(tmn);/向普通链表中添加一个结点void addNode(PNode &Head , PNode &newNode) newNode->next = Head->next; He

21、ad->next = newNode;/向非递减排列的链表中添加一个结点void addAscNode(PNode &Head , PNode &newNode) PNode P;PNode Q;P = Head->next;Q = Head;while(P != NULL && P->fvalue < newNode->fvalue) Q = P;P = P->next;/上面判断好位置之后，下面就是简单的插入了 newNode->next = Q->next;Q->next = newNode;/计算结点

22、额 h 值int computeHValue(PNode theNode)int num = 0;for(int i = 0 ; i < 3 ; i+)for(int j = 0 ; j < 3 ; j+)if(theNode->dataij != targetij) num+;return num;/计算结点的 f，g，h 值void computeAllValue(PNode &theNode , PNode parentNode) if(parentNode = NULL)theNode->gvalue = 0;elsetheNode->gvalue

23、 = parentNode->gvalue + 1;theNode->hvalue = computeHValue(theNode);theNode->fvalue = theNode->gvalue + theNode->hvalue;/初始化函数，进行算法初始条件的设置void initial()/初始化 open 以及 closed 表initLink(open);initLink(closed);/初始化起始结点，令初始结点的父节点为空结点 PNode NULLNode = NULL;PNode Start = (PNode)malloc(sizeof(N

24、Node); for(int i = 0 ; i < 3 ; i+)for(int j = 0 ; j < 3 ; j+)Start->dataij = starttij;Start->parent = NULL;Start->child = NULL;Start->next = NULL;computeAllValue(Start , NULLNode);/起始结点进入 open 表 addAscNode(open , Start);/将 B 节点的状态赋值给 A 结点void statusAEB(PNode &ANode , PNode BNod

25、e) for(int i = 0 ; i < 3 ; i+)for(int j = 0 ; j < 3 ; j+)ANode->dataij = BNode->dataij;/两个结点是否有相同的状态bool hasSameStatus(PNode ANode , PNode BNode) for(int i = 0 ; i < 3 ; i+)for(int j = 0 ; j < 3 ; j+)if(ANode->dataij != BNode->dataij) return false; return true;/结点与其祖先结点是否有相同的

26、状态 bool hasAnceSameStatus(PNode OrigiNode , PNode AnceNode) while(AnceNode != NULL)if(hasSameStatus(OrigiNode , AnceNode) return true;AnceNode = AnceNode->parent;return false;/取得方格中空的格子的位置void getPosition(PNode theNode , int &row , int &col) for(int i = 0 ; i < 3 ; i+)for(int j = 0 ; j

27、 < 3 ; j+)if(theNode->dataij = 0)row = i;col = j;return;/交换两个数字的值void changeAB(int &A , int &B)int C;C = B;B = A;A = C;/检查相应的状态是否在某一个链表中bool inLink(PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode) preNode = theLink; theLink = theLink->next;while(theLink

28、!= NULL)if(hasSameStatus(spciNode , theLink)theNodeLink = theLink;return true;preNode = theLink;theLink = theLink->next;return false;/产生结点的后继结点 (与祖先状态不同 )链表 void SpringLink(PNode theNode , PNode &spring) int row;int col;getPosition(theNode , row , col);/空的格子右边的格子向左移动 if(col != 2)PNode rlNewNo

29、de = (PNode)malloc(sizeof(NNode); statusAEB(rlNewNode , theNode);changeAB(rlNewNode->datarowcol , rlNewNode->datarowcol + 1); if(hasAnceSameStatus(rlNewNode , theNode->parent)free(rlNewNode);/ 与父辈相同，丢弃本结点elserlNewNode->parent = theNode;rlNewNode->child = NULL;rlNewNode->next = NULL

30、;computeAllV alue(rlNewNode , theNode);/将本结点加入后继结点链表addNode(spring , rlNewNode);/空的格子左边的格子向右移动if(col != 0)PNode lrNewNode = (PNode)malloc(sizeof(NNode); statusAEB(lrNewNode , theNode);changeAB(lrNewNode->datarowcol , lrNewNode->datarowcol - 1); if(hasAnceSameStatus(lrNewNode , theNode->pare

31、nt)free(lrNewNode);/ 与父辈相同，丢弃本结点elselrNewNode->parent = theNode;lrNewNode->child = NULL;lrNewNode->next = NULL;computeAllV alue(lrNewNode , theNode);/将本结点加入后继结点链表addNode(spring , lrNewNode);/空的格子上边的格子向下移动if(row != 0)PNode udNewNode = (PNode)malloc(sizeof(NNode); statusAEB(udNewNode , theNod

32、e);changeAB(udNewNode->datarowcol , udNewNode->datarow - 1col); if(hasAnceSameStatus(udNewNode , theNode->parent)free(udNewNode);/ 与父辈相同，丢弃本结点elseudNewNode->parent = theNode; udNewNode->child = NULL; udNewNode->next = NULL;computeAllV alue(udNewNode , theNode); /将本结点加入后继结点链表 addNod

33、e(spring , udNewNode);/空的格子下边的格子向上移动if(row != 2)PNode duNewNode = (PNode)malloc(sizeof(NNode); statusAEB(duNewNode , theNode);changeAB(duNewNode->datarowcol , duNewNode->datarow + 1col); if(hasAnceSameStatus(duNewNode , theNode->parent)free(duNewNode);/ 与父辈相同，丢弃本结点elseduNewNode->parent =

34、 theNode; duNewNode->child = NULL; duNewNode->next = NULL;computeAllV alue(duNewNode , theNode); /将本结点加入后继结点链表 addNode(spring , duNewNode);/输出给定结点的状态void outputStatus(PNode stat)for(int i = 0 ; i < 3 ; i+)for(int j = 0 ; j < 3 ; j+)cout << stat->dataij << " "cout

35、 << endl;/输出最佳的路径void outputBestRoad(PNode goal) int deepnum = goal->gvalue;if(goal->parent != NULL) outputBestRoad(goal->parent);cout << " 第 " << deepnum- << " 层的状态： " << endl; outputStatus(goal);void AStar()PNode tmpNode;/ 指向从 open 表中拿出并放到

36、 closed 表中的结点的指针PNode spring;/tmpNode 的后继结点链PNode tmpLNode;/tmpNode 的某一个后继结点PNode tmpChartNode;PNode thePreNode;/指向将要从 closed 表中移到 open 表中的结点的前一个结点的指针 bool getGoal = false;/ 标识是否达到目标状态 long numcount = 1;/ 记录从 open 表中拿出结点的序号initial();/ 对函数进行初始化initLink(spring);/ 对后继链表的初始化 tmpChartNode = NULL;cout <

37、;< " 从 open 表中拿出的结点的状态及相应的值 " << endl; while(!isEmpty(open)/从 open 表中拿出 f 值最小的元素 ,并将拿出的元素放入 closed 表中 popNode(open , tmpNode);addNode(closed , tmpNode);cout << "第" << numcount+ << " 个状态是： " << endl; outputStatus(tmpNode);cout << &q

38、uot; 其 f 值为： " << tmpNode->fvalue << endl; cout << "其 g值为： " << tmpNode->gvalue << endl; cout << "其 h值为： " << tmpNode->hvalue << endl;/如果拿出的元素是目标状态则跳出循环 if(computeHV alue(tmpNode) = 0) getGoal = true;break;parent 属性/产生当前检测结点的后继 (与祖先不同 )结点列表，产生的后继结点的 指向当前检测的结点SpringLi