论文首页
代写论文
代发论文
论文搜索:
www
热门:代写论文 |代写职称论文|期刊导航|代写留学生论文
 
当前位置:论文首页 >> 论文写作指导 >> 数码迷题求解算法的比较及A*算法的简单介绍

数码迷题求解算法的比较及A*算法的简单介绍 (1)

2011-05-08 10:08:42  作者:  来源:互联网  文字大小:【】【】【
简介: 一、引言   8数码迷题又称重排九宫,问题描述如下:用数字1~8标注的棋子摆放在一个3×3共9个格子的棋盘上,空出一个格子使棋子能在盘内水平滑动,8个符号在棋盘上的排列称为8数码的状态,游戏要求给定一个初 ...
定制论文   发表论文

 一、引言 
  8数码迷题又称重排九宫,问题描述如下:用数字1~8标注的棋子摆放在一个3×3共9个格子的棋盘上,空出一个格子使棋子能在盘内水平滑动,8个符号在棋盘上的排列称为8数码的状态,游戏要求给定一个初始的状态和一个终止状态,且每次只能移动一个棋子,求从任一初始棋局变化到另一目标棋局是否有解,以及有解时的解法。 
  二、定理化判定可解性 
  按从左往右,从上到下的顺序将棋局状态表示为一个数列P=a1a2a3a4a5a6a7a8,ai为1,2…8八个数码中的一个,P是1,2…8的一个排列,称P是该棋局的状态数列。在序列P中对iaj,则称aj出现了一个逆序,元素aj的逆序数记为R(aj)。于是序列P的逆序数记为R(P),定义为除元素0外所有元素的逆序个数之和。序列P的元素存放在数组S[1∽n×n]中。 
  三、搜索算法的分析比较 
  (一)三种搜索算法的数据结构分析。首先简单介绍下Open表和Closed的动态数据结构,前者记录当前未考察的结点,后者记录考察过的结点。扩展所得子结点按其估值的大小插入Open表中合适的位置,每次从中选出估值最小的加以扩展。每个结点都保留父结点的信息,这保证了搜索完毕后,能通过Closed表返回完整的搜索路径。 
  一般图的搜索算法中,提高效率的关键在于Open表中结点的排列方式,若每次排在表首的结点都最终搜索到解的路径上,则算法不需扩展任何多余的结点就可快速结束搜索。所以排列方式成为研究搜索算法的焦点,并由此形成了多种搜索策略。 
  (二)三种搜索算法的比较及适用范围。对于,实际问题,深度优先搜索一般不能保证找到最优解,虽然通过与回溯结合可以找到最优解,但是在最坏的情况下,搜索空间等同于穷举。而且对于许多问题,其状态空间的搜索树的深度可能无限深,或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径,往往给出一个结点扩展的最大深度,称深度界限。任何结点如果达到了深度界限,那么都将把它们作为后继结点处理。即便应用了深度界限的规定,由于一个有解的问题树可能含有无穷分支,深度优先搜索如果误入无穷分支,或解出现在深度界限之外,则不可能找到目标结点。所以,深度优先搜索策略是不完备的。另外,应用此策略得到的解不一定是最佳解,如果深度限制过小的话,甚至得不到解。因此这里就有了一个如何定义深度的问题,太小得不到结果,太大就很容易引起“结点爆炸”。 
  三种搜索算法运用于八数码问题的求解时,对于深度优先搜索有时候会得不到解答,而且具有不确定的时间效率;对于宽度优先搜索,虽然得到的都是最优解,但是由于生成了大量的结点,因此每次生成的结点要判断是否为全新结点都要对已经生成的结点进行遍历和比较,不但损失了空间效率,甚至还会影响时间效率;对于A*算法,理论上是能够扩展最少的结点,最快的找到解答,但是如果评估函数选的不好,也会影响效率。因此对启发式搜索的启发函数的研究就显得特别有意义了。 
  四、启发式搜索策略A*算法的简单介绍 
  (一)算法估价函数简介。数码重排最简单的启发函数h(n)就是计算当
[1] [2]

责任编辑:lw66

定制论文   发表论文


 

最新论文

更多

· 速算扣除数
· 利用网上资源和EXCEL函数...
· 节煤管理模式研究
· 浅议新世纪建筑给排水的...
· 从议程设置理论来看网络...
· 山区农村自建住宅防雷措施
· 数码迷题求解算法的比较...
· 中医是否科学
· 商业银行加强劳务派遣制...
· 商业银行信贷风险管控效...

推荐论文

更多

· 速算扣除数
· 利用网上资源和EXCEL函数...
· 节煤管理模式研究
· 浅议新世纪建筑给排水的...
· 从议程设置理论来看网络...
· 山区农村自建住宅防雷措施
· 数码迷题求解算法的比较...
· 中医是否科学
· 商业银行加强劳务派遣制...
· 商业银行信贷风险管控效...

热门论文

更多

· 对中国农村医疗救助的研究
· 商业银行加强劳务派遣制...
· 中国农地流转研究综述
· 商业银行信贷风险管控效...
· 新时代下新农村中党的基...
· 浅析土地流转对粮食安全...
· 论村民大会议事程序之完善
· 汉庄镇水改旱种植杂交玉...
· 中医是否科学
· 数码迷题求解算法的比较...