华容道搜索算法研究

《华容道搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、华容道搜索算法研究许剑伟2006五一节于福建莆出十中一、算法的由來：也不知写了多少行程序，累了，写点轻松的吧，可千万不要和操作系统打交了！还有那该死的Socket,真讨厌，什么“缓冲区不足”，我不是有2G内存，怎么就不足了？志雄正潜心研究24点算法，向我要全排列的算法，我给他一个利用堆栈解决方法，寥寥几行，志雄叫好。看他挺专心的，于是我也加入他的24点项目。花了一个晚上考虑算法，第二天早上，完全实现了我的算法，用时0.75秒，解出1900道24点题目的完全解，比较满意。第二天再和李雄讨论算法并最后定稿。后来李志雄和我谈起华容道的问题。想来颇为感慨,大概6年前，林清霞

2、老师给我“华容道”时，我花费了整整一个下午时间，也没能走出来，一恼火，打开电脑编程来解。用TC2.0编写一个程序，花了一天，终于写好，并得到结果。可如今再提“华容道”吋，我竟然对当吋的算法很模糊，我知道写那种程序有一定难度，可多年后，在我更加熟悉程序设计之后，怎么突然没头绪了，只记得当时写象棋程序花费了不少时间，华容道应是小问题，当时的我到底有用了什么招术？我想，我应再闯“华容道”。可是要用什么算法呢？在网络上找了很久，看了儿篇，没找到我满意的，仔细分析，这些算法效率不行，我不想釆用。于是我又坐下来考虑算法，3个小时过去了，终于有眉目了。本文算法可在40毫秒内解岀“

3、横刀立马”(P2.4G),其它棋局耗吋略有不同。本文程序利用哈希技术优化后速度提高3倍，约12ms/题。二、棋局：张飞曹操赵云马超关羽黄忠兵兵兵兵图屮棋子共10个，滑动棋子，把曹操移正下方出口。有数学家指出，此问题单靠数学方法很难求解。“华容道”开局布阵有数百种，以上仅是一种。三、前人研究：引网文：“华容道”是世界著名的智力游戏。在国外和魔方、独粒钻石并列，被誉为”智力游戏界三大不可思议”并被编入学校的教科书。日本藤村幸三朗曾在《数理科学》杂志上发表华容道基木布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁•加徳纳又进一步把它减少为81

4、步。此后，至今还未曾见到打破这一记录的报道。网络上可找到儿个有效的算法例程，一个是PASCAL的，一个是VB的，一个是C的,还有一个针对手机的java源代码，都指明使用广度优先算法及一些剪枝办法。但算法效率仍然不高。天津师范大李学武《华容道游戏的搜索策略》说到使用双向搜索可提高效率，但本文未采用这种方法，我觉得目标结点不好选择。有篇文章说对称的节点可以不搜索，想了想确实有道理，本文采用了。后來又在网络上找到几个华容道游戏程序，其中李智广的程序效率较高(V2.0),本想细仔研究它，可是很遗憾，未能找到它的算法说明，只好自已动手设计算法，经过2天努力，本文的搜索效率已远

5、远超过它，足以证实算法的有效性。四、算法：（一）、广度优先搜索：这里简单介绍，不明白的话自己查查图、树相关资料吧。一个盘而状态理解为一个节点，在编程时表示节点的方法是多样的，可用一串数字来表示盘面状态节点，通过压缩处理，甚至可用一个int32整型数来表示一个节点。首先考查起始盘面（节点）的所有走法，然后逐一试走，设当前有nl种走法，则生成nl个儿子节点。接下来，考查这nl个儿子节点的所有走法，并分别试走，生成n2个孙子节点。接下来，考查这n2个孙子节点的所有走法，并分别试走，生成n3个曾孙节点。再接下，就不多说了，依上循环，一代一代的往下生成节点，直到找到目标节点。

6、以上搜索思想朴素、简单，这也正是程序设计所需要的！可是摆在我们面前的问题有两个：a、代代生成子节点，将会有很多个节点，如何存取这些节点呢，也就是说如何有序的排放节点而不至于造成混乱。b、程序大概结构应是怎样的。第1个问题可这样解决：设第一代节点放在A[l]中，第二代节点放在A[2]中，第三代节点放在A⑶……注意A[l]中含有多个节点，A⑵也是这样的……。第2个问题可用以下伪代码解决：//展开首节点得所有儿子节点A[l]for（i=l;i<=n层;I++）｛//查找n代（层）Pl=A[i],P2=A[i+l]for（j=l;j<=Pl内节点个数;j++）｛B=Pl[j

7、]〃读取P中的第j个节点检查B是否为目标节点，如果是，结束搜索展开B并将所有节点追加到P2中//P2为P1下一代的节点集//以上代码基本上给出了搜索算法，这种搜索本质上是广度优先算法。接下个我们来优化这个程序。把第一代儿子节点放在A⑴中，那么A[l]要有多大空间來放节点所，显然第一代只需能放10个节点就够了，因为最多可能的走步不会超过10步，那第二代呢，肯定就多了，第三代还会更多……，每代所需空间都不一样，那我们要如何分配空间，如果使用javascript.PHP等脚本语言来编程，内存空间分配问题基本不用管，但用C语言呢。假如每代最多10000个节点，然后，您想