下载此文档

华容道搜索算法研究.doc


文档分类:IT计算机 | 页数:约43页 举报非法文档有奖
1/43
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/43 下载此文档
文档列表 文档介绍
华容道搜索算法研究
许剑伟 2006五一节于福建莆田十中
一、算法的由来:
也不知写了多少行程序,累了,写点轻松的吧,可千万不要和操作系统打交了!还有那该死的Socket,真讨厌,什么“缓冲区不足”,我不是有2G内存,怎么就不足了?
志雄正潜心研究24点算法,向我要全排列的算法,我给他一个利用堆栈解决方法,寥寥几行,志雄叫好。看他挺专心的,于是我也加入他的24点项目。花了一个晚上考虑算法,第二天早上,完全实现了我的算法,,解出1900道24点题目的完全解,比较满意。第二天再和李雄讨论算法并最后定稿。后来李志雄和我谈起华容道的问题。想来颇为感慨,大概6年前,林清霞老师给我“华容道”时,我花费了整整一个下午时间,也没能走出来,一恼火,打开电脑编程来解。,花了一天,终于写好,并得到结果。可如今再提“华容道”时,我竟然对当时的算法很模糊,我知道写那种程序有一定难度,可多年后,在我更加熟悉程序设计之后,怎么突然没头绪了,只记得当时写象棋程序花费了不少时间,华容道应是小问题,当时的我到底有用了什么招术?我想,我应再闯“华容道”。
可是要用什么算法呢?在网络上找了很久,看了几篇,没找到我满意的,仔细分析,这些算法效率不行,我不想采用。于是我又坐下来考虑算法,3个小时过去了,终于有眉目了。
本文算法可在40毫秒内解出“横刀立马”(),其它棋局耗时略有不同。本文程序利用哈希技术优化后速度提高3倍,约12ms/题。
二、棋局:









关羽







图中棋子共10个,滑动棋子,把曹操移正下方出口。
有数学家指出,此问题单靠数学方法很难求解。
“华容道”开局布阵有数百种,以上仅是一种。
三、前人研究:
引网文:“华容道”是世界著名的智力游戏。在国外和魔方、独粒钻石并列,被誉为"智力游戏界三大不可思议"并被编入学校的教科书。日本藤村幸三朗曾在《数理科学》杂志上发表华容道基本布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁·加德纳又进一步把它减少为81步。此后,至今还未曾见到打破这一记录的报道。

网络上可找到几个有效的算法例程,一个是PASCAL的,一个是VB的,一个是C的,还有一个针对手机的java源代码,都指明使用广度优先算法及一些剪枝办法。但算法效率仍然不高。天津师范大李学武《华容道游戏的搜索策略》说到使用双向搜索可提高效率,但本文未采用这种方法,我觉得目标结点不好选择。有篇文章说对称的节点可以不搜索,想了想确实有道理,本文采用了。后来又在网络上找到几个华容道游戏程序,其中李智广的程序效率较高(),本想细仔研究它,可是很遗憾,未能找到它的算法说明,只好自已动手设计算法,经过2天努力,本文的搜索效率已远远超过它,足以证实算法的有效性。
四、算法:
(一)、广度优先搜索:这里简单介绍,不明白的话自己查查图、树相关资料吧。
一个盘面状态理解为一个节点,在编程时表示节点的方法是多样的,可用一串数字来表示盘面状态节点,通过压缩处理,甚至可用一个int32整型数来表示一个节点。
首先考查起始盘面(节点)的所有走法,然后逐一试走,设当前有n1种走法,则生成n1个儿子节点。
接下来,考查这n1个儿子节点的所有走法,并分别试走,生成n2个孙子节点。
接下来,考查这n2个孙子节点的所有走法,并分别试走,生成n3个曾孙节点。
再接下,就不多说了,依上循环,一代一代的往下生成节点,直到找到目标节点。
以上搜索思想朴素、简单,这也正是程序设计所需要的!可是摆在我们面前的问题有两个: a、代代生成子节点,将会有很多个节点,如何存取这些节点呢,也就是说如何有序的排放节点而不至于造成混乱。b、程序大概结构应是怎样的。

第1个问题可这样解决:设第一代节点放在A[1]中,第二代节点放在A[2]中,第三代节点放在A[3]……注意A[1]中含有多个节点,A[2]也是这样的……。
第2个问题可用以下伪代码解决:
//---------------------
展开首节点得所有儿子节点A[1]
for( i=1;i<=n层;I++){ //查找n代(层)
P1=A[i],P2=A[i+1]
for(j=1;j<=P1内节点个数;j++){
B=P1[j] //读取P中的第j个节点
检查B是否为目标节点,如果是,结束搜索
展开B并将所有节点追加到P2中//P2为P1下一代的节点集
}
}
//---------------------
以上代码基本上给出了搜索算法,这种搜索本质上是广度优先算法。接下个我们来优化这个程序。
把第一代儿

华容道搜索算法研究 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数43
  • 收藏数0 收藏
  • 顶次数0
  • 上传人977562398
  • 文件大小535 KB
  • 时间2018-07-14