电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

八数码难题详解广度搜索

八数码难题详解广度搜索_第1页
1/6
八数码难题详解广度搜索_第2页
2/6
八数码难题详解广度搜索_第3页
3/6
【例题】八数码难题(Eight-puzzle)。在 3X3的棋盘上,摆有 8个棋子,在每个棋子上标有 1~8中的某一数字。棋盘中留有一个空格。空格周围的棋子可以移到空格中。要求解的问题是,给出一种初始布局(初始状态)和目标布局(目标状态),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。初始状态和目标状态如下: 初始状态 目标状态 2 8 3 1 2 3 1 6 4 8 4 7 5 7 6 5 求解本题我们可以分 3步进行。 问题分析: 由于题目要找的解是达到目标的最少步骤,因此可以这样来设计解题的方法: 初始状态为搜索的出发点,把移动一步后的布局全部找到,检查是否有达到目标的布局,如果没有,再从这些移动一步的布局出发,找出移动两步后的所有布局,再判断是否有达到目标的。依此类推,一直到某布局为目标状态为止,输出结果。由于是按移动步数从少到多产生新布局的,所以找到的第一个目标一定是移动步数最少的一个,也就是最优解。 建立产生式系统: (1)综合数据库。用3X3的二维数组来表示棋盘的布局比较直观。我们用Ch[i,j]表示第 i行第 j列格子上放的棋子数字,空格则用0来表示。为了编程方便,还需存储下面3个数据:该布局的空格位置(Si,Sj);初始布局到该布局的步数,即深度dep;以及该布局的上一布局,即父结点的位置(pnt)。这样数据库每一个元素应该是由上述几个数据组成的记录。 在程序中,定义组成数据库元素的记录型为: Type node=record ch:array[1..3,1..3] of byte;{存放某种棋盘布局} si,sj:byte; {记录此布局中空格位置} dep,pnt:byte; end; 因为新产生的结点深度(从初始布局到该结点的步数)一般要比数据库中原有的结点深度大(或相等)。按广度优先搜索的算法,深度大(步数多)的结点后扩展,所以新产生的结点应放在数据库的后面。而当前扩展的结点从数据库前面选取,即处理时是按结点产生的先后次序进行扩展。这样广度优先搜索的数据库结构采用队列的结构形式较合适。我们用记录数组data来表示数据库,并设置两个指针:Head为队列的首指针,tail为队列的尾指针。 (2)产生规则。原规则规定空格周围的棋子可以向空格移动。但如果换一种角度观察,也可看作空格向上、下、左、右4个位置移动,这样处理更便于编程。设空格位置在(Si,sj),则有 4条规则: ①空格向上移动: if si-1>=1 then ch[si,sj]:=ch[si-1,sj];ch[si-1,sj]:=0 ②空格向下移动: if si+1<=3 then [si,sj]...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

八数码难题详解广度搜索

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部