人工智能关于八数码问题论文.doc

枣 庄 学 院计算机科学系课程设计任务书 题目： 用A*算法解决八数码问题 学 号： * 姓 名： * 专 业： 计算机科学与技术 课 程： 人工智能 指导教师： * 职称： 讲 师 完成时间：2011年 12月-2011 年 12 月枣庄学院计算机科学系制2011年12 月01日摘要： 八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题，给出了八数码问题的Java算法与实现的思想，分析了A算法的可采纳性等及系统的特点。关键词九宫重排，状态空间，启发式搜索，A算法1引言九宫重排问题是人工智能当中有名的难题之一。问题是在33方格盘上，放有八个数码，剩下一个位置为空，每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置，要求通过一系列的数码移动，将初始状态转化为目标状态。状态转换的规则：空格四周的数移向空格，我们可以看作是空格移动，它最多可以有个方向的移动，即上、下、左、右。九宫重排问题的求解方法，就是从给定的初始状态出发，不断地空格上下左右的数码移至空格，将一个状态转化成其它状态，直到产生目标状态。 一、 问题描述1.1 待解决问题的解释 八数码游戏（八数码问题）描述为：在33组成的九宫格棋盘上，摆有八个将牌，每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动，这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是：给定一种初始的将牌布局或结构（称初始状态）和一个目标的布局（称目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。 1.2 问题的搜索形式描述（4要素） 初始状态：8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。后继函数：通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。目标测试：比较当前状态和目标状态的格局是否一致。路径消耗：每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。1.3 解决方案介绍（原理）对于八数码问题的解决，首先要考虑是否有答案。每一个状态可认为是一个19的矩阵，问题即通过矩阵的变换，是否可以变换为目标状态对应的矩阵？由数学知识可知，可计算这两个有序数列的逆序值，如果两者都是偶数或奇数，则可通过变换到达，否则，这两个状态不可达。这样，就可以在具体解决问题之前判断出问题是否可解，从而可以避免不必要的搜索。如果初始状态可以到达目标状态，那么采取什么样的方法呢？ 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。在这里就要用到启发式搜索启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。 二、 算法介绍2.1 搜索算法一般介绍不管哪种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解（可行解），搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解。搜索算法可分为两大类：无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索，其特点是只要问题状态可以形式化表示，原则上就可用使用无信息的搜索，无信息搜索有如下常见的几种搜索策略：广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DFS和BFS都是蛮力搜索，因为它们在搜索到一个结点时，在展开它的后续结点时，是对它们没有任何认识的，它认为它的孩子们都是一样的优秀，但事实并非如此，后续结点是有好有坏的。好，就是说它离目标结点近，如果优先处理它，就会更快的找到目标结点，从而整体上提高搜索性能。为了改善上面的算法，我们需要对展开后续结点时对子结点有所了解，这里需要一个估值函数，估值函数就是评价函数，它用来评价子结点的好坏，因为准确评价是不可能的，所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值，而不考虑深度，比较有名的就是有序搜索（Ordered-Search），它着重看好能否找出解，而不看解离起始结点的距离（深度）。如果估值函数考虑了深度，或者是带权距离（从起始结点到目标结点的距离加权和），那就是A*如果不考虑深度，就是说不要求最少步数，移动一步就相当于向后多展开一层结点，深度多算一层，如果要求最少步数，那就需要用A*。简单的来说A*就是将估值函数分成两个部分，一个部分是路径价值，另一个部分是一般性启发价值，合在一起算估整个结点的价值，考虑到八数码问题的特点，在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。2.2 算法伪代码算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）输入：初始状态，目标状态输出：从初始状态到目标状态的一系列过程算法描述：Begin：读入初始状态和目标状态，并计算初始状态评价函数值f；根据初始状态和目标状态，判断问题是否可解；If(问题可解)把初始状态假如open表中；While（未找到解&状态表非空）在open表中找到评价值最小的节点，作为当前结点；判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到；对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；把当前结点从open表中移除；End whileEnd if输出结果；End开始算法流程如下：读入棋局初始状态否o是否可解是o初始状态加入open表在open表中找到评价值最小的节点，作为当前结点是o是目标节点否o扩展新状态，把不重复的新状态加入open表中当前结点从open表移除输出结果结束三、 算法实现3.1 实验环境与问题规模实验环境：硬件环境：PC机。 软件环境：Windows XP ;VC+ 6.0。问题规模：对于任一给定可解初始状态，状态空间有9!/2=181440个状态；当采用不在位棋子数作为启发函数时，深度超过20时，算法求解速度缓慢；3.2 数据结构 static int target9=1,2,3,8,0,4,7,6,5; 全局静态变量，表示目标状态class eight_numprivate:int num9; 定义八数码的初始状态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_num9); 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_num9)设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)eight_num& eight_num:operator=(eight_num& another_8num)eight_num& eight_num:operator=(int other_num9)int eight_num:operator=(eight_num& another_8num)int eight_num:operator=(int other_num9)空格向上移int move_up(int num9)空格向下移int move_down(int num9)空格向左移int move_left(int num9)空格向右移int move_right(int num9)判断可否解出int icansolve(int num9,int target9)判断有无重复int existed(int num9,eight_num *where)寻找估价函数最小的叶子节点eight_num* find_OK_leaf(eight_num* start)3.3 实验结果h: 启发函数（不在位将牌数）初始状态目标状态是否有解启发函数用时步数3 2 18 0 47 6 5 1 2 3 8 0 4 7 6 5 否h-1 0 42 7 38 5 6 1 2 3 8 0 4 7 6 5是h2875ms211 0 38 2 47 6 5 1 2 3 8 0 4 7 6 5是h0ms13.4 系统中间及最终输出结果（要求有屏幕显示）目标状态默认为1 2 3 8 0 4 7 6 5 .a) 初始状态是3 2 1 8 0 4 7 6 5，用h作为启发函数结果都如下：b)初始状态是1 04 2 7 3 8 5 6，用h作为启发函数结果都如下：中间略b)初始状态是1 0 3 8 2 4 7 6 5，用h作为启发函数结果都如下：四、参考文献1 Artificial IntelligenceA Modern Approach. Stuart Russell, Peter Norvig. 人民邮电出版社,20042 Artificial Intelligence, Rob Callan. 电子工业出版社,2004附录源代码及其注释#include stdafx.h#include iostream.h#include #include #include #include static int target9=1,2,3,8,0,4,7,6,5;/class definitionclass eight_numprivate:int num9;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_num9);eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)num0=num1;num1=num2;num2=num3;num3=num4;num4=num5;num5=num6;num6=num7;num7=num8;num8=num9;eight_num(void)for (int i=0;i9;i+)numi=i; void cul_para(void); void get_numbers_to(int other_num9);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_num9); void show(void);eight_num& operator=(eight_num&);eight_num& operator=(int other_num9);int operator=(eight_num&);int operator=(int other_num9);/计算启发函数g(n)的值void eight_num:cul_para(void)int i;int temp_nipn=0;for (i=0;iparent=NULL)deapth=0;elsedeapth=this-parent-deapth+1;eva_function=not_in_position_num+deapth;/构造函数1eight_num:eight_num(int init_num9)for (int i=0;i9;i+)numi=init_numi;/显示当前节点的状态void eight_num:show()coutnum0;cout ;coutnum1;cout ;coutnum2;coutn;coutnum3;cout ;coutnum4;cout ;coutnum5;coutn;coutnum6;cout ;coutnum7;cout ;coutnum8;coutn;/复制当前节点状态到一个另数组中void eight_num:get_numbers_to(int other_num9)for (int i=0;i9;i+)other_numi=numi;/设置当前节点状态(欲设置的状态记录的other数组中)void eight_num:set_num(int other_num9)for (int i=0;i9;i+)numi=other_numi;eight_num& eight_num:operator=(eight_num& another_8num)for (int i=0;i9;i+)numi=another_8num.numi;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_num9)for (int i=0;i9;i+)numi=other_numi;return *this;int eight_num:operator=(eight_num& another_8num)int match=1;for (int i=0;i9;i+)if(numi!=another_8num.numi)match=0;break;if (match=0)return 0;else return 1;int eight_num:operator=(int other_num9)int match=1;for (int i=0;i9;i+)if(numi!=other_numi)match=0;break;if (match=0)return 0;else return 1;/class definition over/空格向上移int move_up(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i3)return 0;elsenumi=numi-3;numi-3=0;return 1;/空格向下移int move_down(int num9)for (int i=0;i5)return 0;elsenumi=numi+3;numi+3=0;return 1;/空格向左移int move_left(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i=0|i=3|i=6)return 0;elsenumi=numi-1;numi-1=0;return 1;/空格向右移int move_right(int num9)for (int i=0;i9;i+)if (numi=0)break;if (i=2|i=5|i=8)return 0;elsenumi=numi+1;numi+1=0;return 1;/判断可否解出int icansolve(int num9,int target9)int i,j;int count_num,count_target;for (i=0;i9;i+)for (j=0;ji;j+)if(numjnumi&numj!=0)count_num+;if(targetjparent)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(minp-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 num9;int flag=0;/是否输入错误标志，1表示输入错误int bingo=0;/是否查找成功标志，1表示成功int i,j;coutPlease input the number(0 for the blank):n;for (i=0;inumi;for(j=0;ji;j+)if(numi=numj)flag=1;if (numi8|flag=1)i-;coutIllegle number!tReinput!n;eight_num S(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used+;coutNow the initial numbers are:n;S.show();coutAnd the Target is:n;Target.show();if(!icansolve(num,target)couti;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;