人工智能论文《八数码问题》.docx_第1页
人工智能论文《八数码问题》.docx_第2页
人工智能论文《八数码问题》.docx_第3页
人工智能论文《八数码问题》.docx_第4页
人工智能论文《八数码问题》.docx_第5页
已阅读5页,还剩19页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

人工智能论文精品问题说明:八数码问题是人工智能中一个很典型的智力问题。本文以状态空间搜索的观点讨论了八数码问题,给出了八数码问题的Jv算法与实现的思想,分析了算法的可采纳性等及系统的特点。关键词九宫重排,状态空间,启发式搜索,算法1引言九宫重排问题是人工智能当中有名的难题之一。问题是在33方格盘上,放有八个数码,剩下一个位置为空,每一空格其上下左右的数码可移至空格。问题给定初始位置和目标位置,要求通过一系列的数码移动,将初始状态转化为目标状态。状态转换的规则:空格四周的数移向空格,我们可以看作是空格移动,它最多可以有,个方向的移动,即上、下、左、右。九宫重排问题的求解方法,就是从给定的初始状态出发,不断地空格上下左右的数码移至空格,将一个状态转化成其它状态,直到产生目标状态。 一、 问题描述 1.1 待解决问题的解释 八数码游戏(八数码问题)描述为:在33组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。这种游戏求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),问如何移动将牌,实现从初始状态到目标状态的转变。 1.2 问题的搜索形式描述(4要素) 初始状态: 8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中,状态空间中的任一种状态都可以作为初始状态。 后继函数: 通过移动空格(上、下、左、右)和周围的任一棋子一次,到达新的合法状态。 目标测试: 比较当前状态和目标状态的格局是否一致。 路径消耗: 每一步的耗散值为1,因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。 1.3 解决原理 对于八数码问题的解决,首先要考虑是否有答案。每一个状态可认为是一个19的矩阵,问题即通过矩阵的变换,是否可以变换为目标状态对应的矩阵,由数学知识可知,可计算这两个有序数列的逆序值,如果两者都是偶数或奇数,则可通过变换到达,否则,这两个状态不可达。这样,就可以在具体解决问题之前判断出问题是否可解,从而可以避免不必要的搜索。 如果初始状态可以到达目标状态,那么采取什么样的方法呢,常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找,直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支,再查找另一个分支,以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法,可是当状态空间十分大,且不预测的情况下就不可取了。他的效率实在太低,甚至不可完成。由于八数码问题状态空间共有9!个状态,对于八数码问题如果选定了初始状态和目标状态,有9!/2个状态要搜索,考虑到时间和空间的限制,在这里采用*算法作为搜索策略。在这里就要用到启发式搜索 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。 启发中的估价是用估价函数表示的,如:(n) = g(n) + h(n) 其中(n) 是节点n的估价函数,g(n)是在状态空间中从初始节点到n节点的实际代价,h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中,显然g(n)就是从初始状态变换到当前状态所移动的步数,估计函数(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数,即错位数。 二、 算法介绍 2.1 搜索算法一般介绍 不管哪种搜索,都统一用这样的形式表示:搜索的对象是一个图,它面向一个问题,不一定有明确的存储形式,但它里面的一个结点都有可能是一个解(可行解),搜索的目的有两个方面,或者求可行解,或者从可行解集中求最优解。搜索算法可分为两大类:无信息的搜索算法和有信息的搜索算法。无信息的搜索又称盲目搜索,其特点是只要问题状态可以形式化表示,原则上就可用使用无信息的搜索,无信息搜索有如下常见的几种搜索策略:广度优先搜索、代价一致搜索、深度优先搜索、深度有限搜索、迭代深入优先搜索、双向搜索。我们说DS和BS都是蛮力搜索,因为它们在搜索到一个结点时,在展开它的后续结点时,是对它们没有任何认识的,它认为它的孩子们都是一样的优秀,但事实并非如此,后续结点是有好有坏的。好,就是说它离目标结点近,如果优先处理它,就会更快的找到目标结点,从而整体上提高搜索性能。 为了改善上面的算法,我们需要对展开后续结点时对子结点有所了解,这里需要一个估值函数,估值函数就是评价函数,它用来评价子结点的好坏,因为准确评价是不可能的,所以称为估值。这就是我们所谓的有信息搜索。如果估值函数只考虑结点的某种性能上的价值,而不考虑深度,比较有名的就是有序搜索(Ordered-Serch),它着重看好能否找出解,而不看解离起始结点的距离(深度)。如果估值函数考虑了深度,或者是带权距离(从起始结点到目标结点的距离加权和),那就是*如果不考虑深度,就是说不要求最少步数,移动一步就相当于向后多展开一层结点,深度多算一层,如果要求最少步数,那就需要用*。简单的来说*就是将估值函数分成两个部分,一个部分是路径价值,另一个部分是一般性启发价值,合在一起算估整个结点的价值, 考虑到八数码问题的特点,在本实验中使用*算法求解。*搜索是一种效的搜索算法,它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价:(n)=g(n)+h(n)。当h(n)是可采纳时,使用Tree-Serch的*算法将是最优的。 2.2 算法伪代码 算法的功能:产生8数码问题的解(由初始状态到达目标状态的过程)输入:初始状态,目标状态 输出:从初始状态到目标状态的一系列过程 算法描述: Begin: 读入初始状态和目标状态,并计算初始状态评价函数值; 根据初始状态和目标状态,判断问题是否可解; I(问题可解) 把初始状态假如open表中; While(未找到解&状态表非空) ?在open表中找到评价值最小的节点,作为当前结点;?判断当前结点状态和目标状态是否一致,若一致,跳出循环;否则跳转到?; ?对当前结点,分别按照上、下、左、右方向移动空格位置来扩展新的状态结点,并计算新扩展结点的评价值并记录其父节点;?对于新扩展的状态结点,判断其是否重复,若不重复,把其加入到open表中; ?把当前结点从open表中移除; End while End i 输出结果; End 算法流程如下: 开始 读入棋局初始状态 否 是否可解 o 是o 初始状态加入open表 在open表中找到评价值最小的节点,作为当前结点 是 是目标节点 o 否 o 扩展新状态,把不重复的新状态加入open表中 当前结点从open表移除 输出结果 结束 问题规模:对于任一给定可解初始状态,状态空间有9!/2=181440个状态;当采用不在位棋子数作为启发函数时,深度超过20时,算法求解速度缓慢;3.2 数据结构 sttic int trget9=1,2,3,8,0,4,7,6,5; 全局静态变量,表示目标状态clss eight_num privte: int num9; 定义八数码的初始状态 int not_in_position_num; 定义不在正确位置八数码的个数int depth; 定义了搜索的深度 int ev_unction; 评价函数的值,每次选取最小的进行扩展 public: eight_num* prent; 指向节点的父节点 eight_num* le_next; 指向open表的下一个节点 eight_num* le_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_pr(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:opertor=(eight_num& nother_8num) eight_num& eight_num:opertor=(int other_num9) int eight_num:opertor=(eight_num& nother_8num) int eight_num:opertor=(int other_num9) 空格向上移 int move_up(int num9) 空格向下移 int move_down(int num9) 空格向左移 int move_let(int num9) 空格向右移 int move_right(int num9) 判断可否解出 int icnsolve(int num9,int trget9) 判断有无重复 int existed(int num9,eight_num *where) 寻找估价函数最小的叶子节点 eight_num* ind_OK_le(eight_num* strt) 3.3 实验结果 h: 启发函数(不在位将牌数) 初始状目标状是否有启发函数 用时 步数 态 态 解 3 2 1 1 2 3 否 h - 8 0 4 8 0 4 7 6 5 7 6 5 1 0 4 1 2 3 是 h 2875ms 21 2 7 3 8 0 4 8 5 6 7 6 5 1 0 3 1 2 3 是 h 0ms 1 8 2 4 8 0 4 7 6 5 7 6 5 3.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作为启发函数结果都如下:源代码(用c+实现): #include stdx.h #include iostrem.h #include #include #include #include sttic int trget9=1,2,3,8,0,4,7,6,5; /clss deinition clss eight_num privte: int num9; int not_in_position_num; int depth; int ev_unction; public: eight_num* prent; eight_num* le_next; eight_num* le_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) or (int i=0;i9;i+) numi=i; void cul_pr(void); void get_numbers_to(int other_num9); int get_nipn(void) return not_in_position_num; int get_depth(void) return depth; int get_evun(void) return ev_unction; void set_num(int other_num9); void show(void); eight_num& opertor=(eight_num&); eight_num& opertor=(int other_num9); int opertor=(eight_num&); int opertor=(int other_num9); ; /计算启发函数g(n)的值 void eight_num:cul_pr(void) int i; int temp_nipn=0; or (i=0;iprent=NULL) depth=0; else depth=this-prent-depth+1; ev_unction=not_in_position_num+depth; /构造函数1 eight_num:eight_num(int init_num9) or (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) or (int i=0;i9;i+) other_numi=numi; /设置当前节点状态(欲设置的状态记录的other数组中) void eight_num:set_num(int other_num9) or (int i=0;i9;i+) numi=other_numi; eight_num& eight_num:opertor=(eight_num& nother_8num) or (int i=0;i9;i+) numi=nother_8num.numi; not_in_position_num=nother_8num.not_in_position_num; depth=nother_8num.depth+1; ev_unction=not_in_position_num+depth; return *this; eight_num& eight_num:opertor=(int other_num9) or (int i=0;i9;i+) numi=other_numi; return *this; int eight_num:opertor=(eight_num& nother_8num) int mtch=1; or (int i=0;i9;i+) i(numi!=nother_8num.numi) mtch=0; brek; i (mtch=0) return 0; else return 1; int eight_num:opertor=(int other_num9) int mtch=1; or (int i=0;i9;i+) i(numi!=other_numi) mtch=0; brek; i (mtch=0) return 0; else return 1; /clss deinition over /空格向上移 int move_up(int num9) or (int i=0;i9;i+) i (numi=0) brek; i (i3) return 0; else numi=numi-3; numi-3=0; return 1; /空格向下移 int move_down(int num9) or (int i=0;i5) return 0; else numi=numi+3; numi+3=0; return 1; /空格向左移 int move_let(int num9) or (int i=0;i9;i+) i (numi=0) brek; i (i=0|i=3|i=6) return 0; else numi=numi-1; numi-1=0; return 1; /空格向右移 int move_right(int num9) or (int i=0;i9;i+) i (numi=0) brek; i (i=2|i=5|i=8) return 0; else numi=numi+1; numi+1=0; return 1; /判断可否解出 int icnsolve(int num9,int trget9) int i,j; int count_num,count_trget; or (i=0;i9;i+) or (j=0;ji;j+) i(numjnumi&numj!=0) count_num+; i(trgetjprent) i(*p=num) return 1; return 0; /寻找估价函数最小的叶子节点 eight_num* ind_OK_le(eight_num* strt) eight_num *p,*OK; p=OK=strt; int min=strt-get_evun(); or(p=strt;p!=NULL;p=p-le_next) i(minp-get_evun() OK=p; min=p-get_evun(); return OK; /主函数开始 int min(void) double time; clock_t Strt,inish; int memery_used=0,step=0; int num9; int lg=0;/是否输入错误标志,1表示输入错误 int bingo=0;/是否查找成功标志,1表示成功 int i,j; coutPlese input the number(0 or the blnk):n; or (i=0;inumi; or(j=0;ji;j+) i(numi=numj) lg=1; i (numi8|lg=1) i-; coutIllegle number!tReinput!n; eight_num S(num),Trget(trget); S.prent=S.le_next=S.le_pre=NULL; S.cul_pr(); memery_used+; coutNow the initil numbers re:n; S.show(); coutnd the Trget is:n; Trget.show(); i(!icnsolve(num,trget) couti; return 1; Strt=clock( ); eight_num *OK_le=&S,*le_strt=&S,*new_8num,*p; while(OK_le!=NULL&bingo!=1) OK_le=ind_OK_le(le_strt); i(*OK_le=Trget) bingo=1; brek; p=OK_le-le_pre; OK_le-get_numbers_to(num); i(move_up(num)&!existed(num,OK_le) new_8num=new eight_num; new_8num-set_num(num); new_8num-prent=OK_le; new_8num-cul_pr(); new_8num-le_pre=p; i(p=NULL) le_strt=new_8num; else p-le_next=new_8num; p=new_8num; memery_used+; OK_le-get_numbers_to(num); i(move_down(num)&!existed(num,OK_le) new_8num=new eight_num; new_8num-set_num(num); new_8num-prent=OK_le; new_8num-cul_pr(); new_8num-le_pre=p; i(p=NULL) le_strt=new_8num; else p-le_next=new_8num; p=new_8num

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论