文档介绍：华容道游戏与算法收藏1引言华容道游戏是古老的中国传统益智游戏,以其变化多端百玩不厌的特点,与魔方独立钻石棋一起被国外智力专家并称为智力游戏界的三个不可思议。日本藤村幸三朗曾在《数理科学》杂志上发表华容道基本布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁·加德纳又进一步把它减少为81步。此后,至今还未曾见到打破这一记录的报道。而对解题效率的提升,则有数学家指出,此问题单靠数学方法很难求解。华容道游戏的棋盘是由20个小正方形组成的长方形宽4格长5格,共有10个棋子。其中五个棋子为张飞,赵云,马超,黄忠和关羽等。五虎将每个棋子占两格,可以是横的,也可以是竖的。四个棋子为刘备兵,各占一格。另一个棋子为曹操,占四格形状为正方形。棋盘的下部有两个空置的小格,作为华容道的出口。棋盘上仅有两个小方格,空着玩法就是通过棋子在这个长方形的棋盘内滑动,用最少的步数把曹操移出华容道。图1所示的布局即为华容道的一种初始布局,俗称横刀立马。应用计算机对每种布局都可以快速地找到最优走法或判断它无解。按一个棋子走一个空格,或连续走两个空格算一步的规则,横刀立马的布局的最优走法为81步。近年来虽然出现了几款华容道游戏的软件,但在电脑自动解题方面效率不够理想。有学者提到的应用双向广度优先搜索策略寻找最优走法,但也仍存在着一些不足之处。从计算机人工智能的角度看华容道游戏,可以表示成下述问题:给定一个三元组(SFG),S为初始状态(初始布局)构成的集合,F为算符(移动棋子的操作)构成的集合,G为目标状态(曹操在出口位置的布局)构成的集合。从初始状态出发,应用算符搜索一条到达目标状态的路径。本文中将该问题称为华容道问题文中从搜索策略数据结构算法优化程序设计等几方面详细讨论华容道问题最优解的求解方法。2经典的搜索策略以及方法目前在对华容道的研究上有几个有效的算法例程,一个是PASCAL的,一个是VB的,一个是C的,还有一个针对手机的java源代码,都指明使用广度优先算法及一些剪枝办法。但算法效率仍然不高。天津师范大李学武《华容道游戏的搜索策略》说到使用双向搜索可提高效率,但本文未采用这种方法。,在编程时表示节点的方法是多样的,可用一串数字来表示盘面状态节点,通过压缩处理,甚至可用一个int32整型数来表示一个节点。首先考查起始盘面(节点)的所有走法,然后逐一试走,设当前有n1种走法,则生成n1个儿子节点。接下来,考查这n1个儿子节点的所有走法,并分别试走,生成n2个孙子节点。接下来,考查这n2个孙子节点的所有走法,并分别试走,生成n3个曾孙节点。再接下,就不多说了,依上循环,一代一代的往下生成节点,直到找到目标节点。以上搜索思想朴素、简单,这也正是程序设计所需要的!可是摆在我们面前的问题有两个:a、代代生成子节点,将会有很多个节点,如何存取这些节点呢,也就是说如何有序的排放节点而不至于造成混乱。b、程序大概结构应是怎样的。第1个问题可这样解决:设第一代节点放在A[1]中,第二代节点放在A[2]中,第三代节点放在A[3]……注意A[1]中含有多个节点,A[2]也是这样的……。由于整个棋局的可行解可以描述成一个树型结构,并且为了得到最少移动步数需要采用广度优先的搜索算法,因此考虑将链表与树型结构整合起来,便于进行广度搜索。如图,当我们试图搜索第三步可行解时,只需要顺着第二步的链表依次搜索便可以实现了。而在人工智能中,对由三元组表示的状态空间,求解问题的方法是通过运用某种搜索策略生成状态空间的部分状态(节点)来寻找问题的解。其基本思想是首先把问题的初始状态(初始节点)作为当前状态(当前节点),选择适用的算符,对其进行操作生成一组子状态(子节点),然后检查目标状态(目标节点)是否在其中出现。若出现则搜索成功,找到问题的解,若不出现,则按某种搜索策略从已生成的节点中再选一个节点作为当前节点。重复上述过程,直到目标节点出现,或者不再有可供操作的节点及算符为止。在各种搜索策略中,广度优先搜索策略对于存在解的问题,总是可以搜索到它的解,而且得到的是路径最短的解。对华容道问题,棋子每走一步是对当前节点生成它的一个子节点在走法的步数最少为最优的意义下,寻找它的最优解,实际上也就是寻找路径最短的解。因此只要某种初始布局存在解,则应用广度优先搜索策略,总是可以搜索到它的最优解。对无解的初始布局,由于棋子和格子都是有限个,所生成的相异的节点个数也必然是有限个,则应用广度优先搜索策略也能在有限步内判断它无解。求解华容道问题广度优先搜索是一种合适的搜索策略。在搜索过程中,所有节点及其指向父节点的指针的反向指针构成一棵以初始节点为根的搜索树。如果把从初始节点算起,路径深度相同的节点称为同层节点,那么广度优先搜索就是逐层地