|
华容道游戏是古老的中国传统益智游戏，以其变化多端百玩不厌的特点，与魔方独立钻石棋 一起被国外智力专家并称为智力游戏界的三个不可思议。日本藤村幸三朗曾在《数理科学》 杂志上发表华容道基本布局的最少步法为85步。后来清水达雄找出更少的步法为83步。美国著名数学家马丁?加德纳又进一步把它减少为81步。此后，至今还未曾见到打破这一记录 的报道。而对解题效率的提升，则有数学家指出，此问题单靠数学方法很难求解。 华容道游戏的棋盘是由20个小正方形组成的长方形宽4 格长5 格，共有10 个棋子。其中五个棋子为张飞，赵云，马超，黄忠和关羽等。五虎将每个棋子占两格，可以是横的，也 可以是竖的。四个棋子为刘备兵，各占一格。另一个棋子为曹操，占四格形状为正方形。棋 盘的下部有两个空置的小格，作为华容道的出口。棋盘上仅有两个小方格，空着玩法就是通 过棋子在这个长方形的棋盘内滑动，用最少的步数把曹操移出华容道。 图1 所示的布局即为华容道的一种初始布局，俗称横刀立马。应用计算机对每种布局都可 以快速地找到最优走法或判断它无解。按一个棋子走一个空格，或连续走两个空格算一步的 规则，横刀立马的布局的最优走法为81 步。近年来虽然出现了几款华容道游戏的软件，但 在电脑自动解题方面效率不够理想。有学者提到的应用双向广度优先搜索策略寻找最优走法， 但也仍存在着一些不足之处。从计算机人工智能的角度看华容道游戏，可以表示成下述问题： 给定一个三元组(S F G)， S 为初始状态(初始布局)构成的集合，F为算符(移动棋子的操作)构成的集合，G 为目标状态(曹操在出口位置的布局)构成的集合。从初始状态出发，应用算 符搜索一条到达目标状态的路径。本文中将该问题称为华容道问题文中从搜索策略数据结构 算法优化程序设计等几方面详细讨论华容道问题最优解的求解方法。 2 经典的搜索策略以及方法 目前在对华容道的研究上有几个有效的算法例程，一个是PASCAL的，一个是VB的，一个是C的，还有一个针对手机的java源代码，都指明使用广度优先算法及一些剪枝办法。但算 法效率仍然不高。天津师范大李学武《华容道游戏的搜索策略》说到使用双向搜索可提高效 率，但本文未采用这种方法。 2.1广度优先的树型结构 一个盘面状态理解为一个节点，在编程时表示节点的方法是多样的，可用一串数字来表示 盘面状态节点，通过压缩处理，甚至可用一个int32整型数来表示一个节点。首先考查起始 盘面（节点）的所有走法，然后逐一试走，设当前有n1种走法，则生成n1个儿子节点。接下来，考查这n1个儿子节点的所有走法，并分别试走，生成n2个孙子节点。接下来，考查 这n2个孙子节点的所有走法，并分别试走，生成n3个曾孙节点。再接下，就不多说了，依 上循环，一代一代的往下生成节点，直到找到目标节点。以上搜索思想朴素、简单，这也正 是程序设计所需要的！可是摆在我们面前的问题有两个： a、代代生成子节点，将会有很多 个节点，如何存取这些节点呢，也就是说如何有序的排放节点而不至于造成混乱。b、程序大概结构应是怎样的。第1个问题可这样解决：设第一代节点放在A[1]中，第二代节点放在A[2]中，第三代节点放在A[3]„„注意A[1]中含有多个节点，A[2]也是这样的„„。由于整个棋 局的可行解可以描述成一个树型结构，并且为了得到最少移动步数需要采用广度优先的搜索 1/11页 算法，因此考虑将链表与树型结构整合起来，便于进行广度搜索。如图，当我们试图搜索第 三步可行解时，只需要顺着第二步的链表依次搜索便可以实现了。 而在人工智能中，对由三元组表示的状态空间，求解问题的方法是通过运用某种搜索策略 生成状态空间的部分状态(节点)来寻找问题的解。其基本思想是首先把问题的初始状态(初始 节点)作为当前状态(当前节点)，选择适用的算符，对其进行操作生成一组子状态(子节点)， 然后检查目标状态(目标节点)是否在其中出现。若出现则搜索成功，找到问题的解,若不出现， 则按某种搜索策略从已生成的节点中再选一个节点作为当前节点。重复上述过程，直到目标 节点出现，或者不再有可供操作的节点及算符为止。在各种搜索策略中，广度优先搜索策略 对于存在解的问题，总是可以搜索到它的解，而且得到的是路径最短的解。对华容道问题， 棋子每走一步是对当前节点生成它的一个子节点在走法的步数最少为最优的意义下，寻找它 的最优解，实际上也就是寻找路径最短的解。因此只要某种初始布局存在解，则应用广度优 先搜索策略，总是可以搜索到它的最优解。对无解的初始布局，由于棋子和格子都是有限个， 所生成的相异的节点个数也必然是有限个，则应用广度优先搜索策略也能在有限步内判断它 无解。求解华容道问题广度优先搜索是一种合适的搜索策略。在搜索过程中，所有节点及其 指向父节点的指针的反向指针构成一棵以初始节点为根的搜索树。如果把从初始节点算起， 路径深度相同的节点称为同层节点，那么广度优先搜索就是逐层地对节点进行扩展并考察它 是否为目标节点。 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下一代的节点集 } } 2.3 对于本方法的一些思考 以上代码基本上给出了搜索算法，这种搜索本质上是广度优先算法。接下个我们来优化这 个程序。把第一代儿子节点放在A[1]中，那么A[1]要有多大空间来放节点所，显然第一代只 需能放10个节点就够了，因为最多可能的走步不会超过10步，那第二代呢，肯定就多了， 2/11页 第三代还会更多„„，每代所需空间都不一样，那我们要如何分配空间，如果使用javascript、PHP等脚本语言来编程，内存空间分配问题基本不用管，但用C语言呢。假如每代最多10000个节点，然后，您想搜索200代，为了简化程序，您可以简单的分配一个200*10000即可解决问题。现在电脑内存很多，用这些空间虽不算奢侈，并且会取得很高的搜索速度，但本着 求精、节约的精神，有必要优化A[][]数组问题。基本思想方法就是将这个二维数组压入一 个一维数组中去。这个特殊的一维数据，称为队。队和数组还有些区别，构成一个队一般还 需要队头指针和队尾指针，当我们读写节点数据时，高度有序的移动这两个指针进行存取节 点而不至于混乱。伪程序中看到，第一代n1个儿子节点放在A[1]中，第二代放在A[2]中，这时A[1]中的很多空间就浪费了，不妨这样吧，读第一代节点时，把生成的第二代节点数据 接在A[1]中最后一个节点之后，当第一代读完时，下一个就是第二代了；读第二代时，生成 第三代节点，同样第三代也接往A[1]里的最后一节点之后，读的过程称出队，写过程过程称 为入队。我们统一从队头开始读（出队），队尾处开始写（入队）。由于搜索时是一代代有序 往下搜索，则队里的节点也是一代一代的往下接。为了有序进行，读取儿子节点时，我们将 队头指针指向儿子节点开始处，然后读取节点，读完后队头指针往后移动一步，当移动n1次后，就读完n1个儿子节点。在读儿子节点的过程中，我们同时试走儿子节点，生成孙子节 点并入队。如此过程，在队头指针读完儿子节点后，队头指针就会指向第一个孙子节点上。 伪代码如下一步展开首节点A得所有儿子节点D数组(队)中P=1，P2=最后一个; //P指向D的第一个(队头指针)，P2指向D的最后一个(队尾指针) for(i=1;i<=n层;I++){ //查找n代（层） k=P2-P //当前层节点个数 for(j=1;j<=k;j++){ B=D[P] //读取D中的第P个节点 检查B是否为目标节点，如果是，结束搜索 展开B并将所有节点追加到D[P2]中 P++，P2+=B展开的个数 } } 2.4 数据结构 在求解华容道问题时，将棋盘的方格按列从左至右编为0,1,2,3 列，按行从上至下编为 0,1,2,3,4 行。即每个方格都给定一个由行号和列号组成的二维坐标，可将棋子编号固定为 0,1,2,3表示四个刘备兵，4,5,6,7,8 表示五虎将，9 表示曹操，有必要时将两个空格也看 作两个棋子编号为10,11。这样棋盘的布局可用一个5 行4 列的二维数组来表示。图1 所示的布局可表示为二维数组判断，是否为目标布局，仅需判断该数组中的第四五行中的第二三 3/11页 列元素的取值是否都等于9。由于棋子的形状不全相同，因此需要一个一维数组来表示按棋 子编号顺序排列的棋子的形状编号。可用1 表示占一个方格，2 表示占竖排的两个方格，3 表示占横排的两个方格，4 表示占四个方格，5 表示空格。给定初始布局相当于初始化两个数 组，对图1所示的初始布局可进行如下初始化： int initstatus[5][4]={4,9,9,5,4,9,9,5,6,8,8,7,6,0,1,7,2,10,11,3}; int mantype[12]={1,1,1,1,2,2,2,2,3,4,5,5}; 为了提高程序的运行效率.根据华容道问题的特点以下介绍三种表示方法。 (1) typedef struct { unsigned int num; 其中num 表示节点编号father 表示父unsigned int father; 节点编号二维数组status 的元素表示unsigned char status[5][4]; 棋盘上相应位置的棋子编号} NODETYPE1; 这种表示方法比较直接，在扩展节点及进行节点的比较时，不必进行数据转换。但每个节 点占用24 个字节的存储空间较浪费空间。 (2) typedef struct { unsigned int num; 其中num 和father 的含义同上字节数组unsigned int father; status 的元素表示相应编号的棋子所占的方unsigned char status[12]; 格中左上角这一格的坐标高四位表示行 } NODETYPE2; 坐标低四位表示列坐标。 这种表示方法，通过存储每个棋子在棋盘上位置的坐标，来描述节点状态，在扩展节点及 进行节点的比较时，需将它转换成一个二维数组。但每个节点占用16 个字节较节省空间。 (3) typedef struct { unsigned int num; 其中num 和father 的含义同上对棋盘上的 unsigned int father; 方格按从左到右从上到下的顺序扫描将unsigned char status[6]; 棋子的编号按出现顺序存储在数组status 中 } NODETYPE3; 每个棋子的编号仅存储一次，占四位。这种表示方法同样在扩展节点及进行节点的比较时， 需进行数据转换。每个节点仅占10个字节，大大地节省了空间，但需做较多的运算。 图1 所示的节点状态在上述三种方法下可分别表示成以下三组数据 NODETYPE1: {4,9,9,5,4,9,9,5,6,8,8,7,6,0,1,7,2,10,11,3} ,每个数据占一个字节,共20 个字节。 NODETYPE2: 4/11页 {0x31,0x32, 0x40,0x43,0x00,0x03,0x20,0x23,0x21,0x01,0x41,0x42}共12 个字节 NODETYPE3: {0x49,0x56,0x87,0x01,0x2a,0xb3 } 共6 个字节。 3使用HashTable以及索引的方法来解决问题 要解决索引问题，可能有很多种方法，首先想到的是使用哈希表的办法，哈希表是棋类游 戏常用的方法，算法原理不难，不过实现起来也挺麻烦的，使用哈希表时一般使用随机数来 建立索引，因此一定要选择有足够散列度随机数(或准随机算法)，以免造成大量哈希冲突而 降底效率。以下介绍的方法是通过编码及查表方法来完成节点索引，建立一种不会发生重复 的索引。总之，就是要建立一个索引，哈希表是个有重复的索引(碰到冲突的一般要做二次哈 希)，编码方法是建立一个无重复索引。本文讲述的的编码方法得到的速度不会很快，如果你 追求速度，最好使用哈希表建立索引，并且在计算哈希值时采用增量技术，这样计算索引号 的速度可提高10至20倍，程序在10ms内可搜索出最优解。 盘面的状态（节点）数量是十分有限的，状态总数不会超过50万种。(横刀立马为例)曹操的走法只有12种，任你如何排放，只有12种，不是20种。横将（关羽）的排法最多只有 11种。接下来对4个竖将排列（组合），排列第一个竖将的排法最多10种，第二个8种，第三个6种，第四个4种。组合数是10*8*6*4/4!=80，后来为来编程方便，做了更多冗于，组 合数用C10取4，即C（10，4）=10*9*8*7/4！=210，这样，4个竖将的某一排列组合必对应 0—209中的一个数，这个数就是我们所要的竖将组合编码值。同理小兵的组合为C（6，4）=15，编码范围在0—14因此对这4种(10个)棋子全排列，种数最多为12*11*210*15=415800，即4百多K。最后易得盘面编码：各种棋子的编码值乘以码权，然后取和。码权只需遵照排 列规律，随你定，是比较简单的。可设兵的码权为1，竖将则是15，横将则为15*210，曹操为15*210*11。要如何对各种棋子高速有效的编码呢？如“横刀立马”开局，如何编码？这 又变成一个组合问题。我们一个一个的排放“横刀立马”棋子并演示编码过程。曹操有12个可排放位置，这12个位置编号为0-11，曹操位置在1，注意，首个是0。关羽有11个可排放位置，这11个位置编号为0-10，关羽位置在1个。竖将有10个可排放的位置，编号为 0-9，一将是0，二将是1，三将是4，四将是5。小兵有6个可排放的位置，编号为0-5，一兵是0，二兵是1，三兵是2，四兵是5。竖将编号序列为0,1,4,5，这一组合对应的组合序 号（编码）是多少呢，如何定义？真还有点不好处理，有人说这与群论有关。0,1,4,5表示的是各个将的位置，竖将在位用1表示，不在位用0表示，则0,1,4,5可示意为11001100000，这不就成了二进制数，不妨把0145转为二进数，用查表法转换是很快的，只需4个加法语名即可完成，再用这个二进数当作数组的下标来查组合的编号表，从表中得到它的编号，设表 为Sb，则编号值为Sb[11001100000]或Sb[816]，这样就完成了高速编码。这个编号表如何 建立呢？这也好办，事前把0000000000—1111111111共1024个数中含4个1的数按顺序编号，其中只有C（10，4）=210个数被编号，其余不用。由此建立一个1024长的有序表Sb[]，表中位置下标含4个1的被编号，共210个。竖将编码过程表示为： 0145=>1100110000=>Sb[100110000]即Sb[816]，小兵同样方式编码 0125=>111001=>Bb[111001]即Bb[57]。上述，编码后盘面总数最多为415800，当我们记录每一个节点是否已经遍历时，最多只需415800个字节，如果是广度搜索，还可按比特方法压缩 8倍，只需415800/8=51975个字节，现在的计算机，内存很存都很强，随便一个new，就可 5/11页 点击展开全文 从APP打开该文档，阅读高清版 开通Plus会员，全场文档6折起 >> |
|
|
