基于hash表的华容道算法研究

周扬 陈伊琳 韦妮君 周一诺

关键词：华容道；时间复杂度；hash表

1引言

目前对华容道算法的优化主要集中在改进搜索策略和减少搜索状态[1-2]，即基于深度优先或广度优先的改进。这两种算法的时间复杂度都为O（V+E）[3]，其中V为顶点数，E为边数。对于华容道游戏，可以将棋盘上的每个状态看作一个顶点，最小正方形棋子的大小视为1*1，则棋盘的大小为4*5，共20个位置。为了估算不考虑棋子重合情况，所有状态数就是在20个位置上放10个棋子的排列，共A=670442572800种状态，即便除去棋子重合的非法情况，也有65 880种状态。保守估算1个状态对应2条边，则对于华容道游戏顶点和边总数约为65880*3=197640。深度优先和广度优先算法本质是在以万为数量级的状态中找到最优解。实际情况是，几个经典开局都要搜索约2万个状态，效率较低。

鉴于此，可以考虑：（1）能否求出华容道一共几种状态？（2）是否能将所有状态枚举出来？（3）存储所有状态和对应最优解所需的内存空间能否接受？如果这3个问题都是肯定回答，那么就可以提前将状态和对应的最优解存人hash表。下文将分析这3个问题。

2基本定义

定义1状态：10个棋子在棋盘的排列方式。

定义2棋盘坐标系：棋盘左上角为坐标原点D（0，0）；从坐标原点出发，水平向右为x轴正方向，长度为4；垂直向下为y轴正方向，长度为5，x与y为整数。

定义6状态坐标：是一个长度为10的数组。第0～3个元素分别为赵云，马超，张飞，黄忠；第4～7个元素分别为兵1，兵2，兵3，兵4；第8个元素为关羽；第9个元素是曹操。

定义7

基本状态坐标：是一个长度为10的数组。第O—3个元素分别为4个1*2型棋子的坐标，顺序记为AIA2A3A4；第4～7个元素分别为4个1*1型棋子的坐标，按顺序记为BIB28384。其中，1*2型和1*1型棋子坐标按y从小到大的顺序排列，若y相等，则再按x从小到大的顺序排列。第8个元素为2*1型棋子的坐标，记为C：第9个元素是2*2型棋子的坐标，记为D。

图1和图2是两个不同状态，有不同的状态坐标，但有相同的基本状态坐标。

定义8

基本状态：基本状态坐标对应的状态定义为基本状态。

3枚举所有合法状态

3.1位置排列转化为一维状态坐标

根据一维棋子坐标的定义，d=0，20）。根据文献[4]排列的定义及计算方法，从整数[0，20）取10个整数的排列共有P（20，10）种。每一种排列都是一个长度为10的数组，若将该种数组当作一个基本状态坐标（数组中的每个数值对应一个一维棋子坐标），不考虑棋子重合的非法状态，理论上共有P（20，10）=670442572800种状态。

3.2合法状态筛选

算法1

验证状态坐标是否合法

产生不合法状态的原因是排列组合算法没有考虑棋盘的形状和棋子的形状。比如，某个1*2型的棋子的坐标是（0，4），棋子就会超出棋盘范围；若某个1*2型的棋子的坐标是（0，0），另外一个1*1型棋子的坐标是（1，0），这就会造成棋子重合。筛选合法状态本质上是从所有状态中去除超出棋盘范围和棋子重合的情况，具体步骤如算法1所示。

4压缩存储

根据定义6和定义7．对于任意一个状态坐标，都能求得其对应的基本状态坐标。比如，记下“张飞”对应A1，那么可由基本状态坐标还原成状态坐标。基于这个事实，可以只存储基本状态坐标和其对应的最优解。对于基本状态坐标，有A1～A4，B1～B4，C，D共10种棋子（图3）。根据定義2，x轴的值为[0，4）的整数，y轴的值为[0，5）的整数，所以保存x轴的坐标需要2bit，保存v轴坐标需要3bit，保存一个棋子的坐标共需要5bit，10个棋子共需要50bit（图4），即7个字节即可保存一个基本状态坐标。但是，考虑到实际程序实现方便，用64位的整数（8字节）存储基本状态坐标。根据算法1，求得65880种合法状态，对应65880个基本状态坐标。

用改进的深度优先算法[5]，可得到53954种基本状态有解。一个状态占用8字节，存储53954种约占421KB。由实验结果可知．53954种有解的基本状态中，最优解最多为126步，1字节就能表示。共有10个不同棋子，需要4bit表示，移动方向有上下左右4种，要2bit表示。因此，表示移动一步要用6bit。实验部分为了实现方便，用1字节表示移动一步。如图5所示，0—7个字节为基本状态坐标。第8个字节为该基本状态坐标的最优解有几步。假定第8个字节为116，那么之后的116个字节表示116步具体内容。116个字节之后的8个字节又是下个基本状态坐标，以此类推。如图6所示。

5实验

上文已经讨论过华容道游戏共有P（20，10）种状态，执行算法1后，得到65880种合法状态。再执行文献[5]的算法求得53954种基本状态有解。用Python实现该过程，把基本状态坐标及对应的最优解保存成第4节讨论的二进制文件。结果表明，该文件仅2.8 MB。将该文件存人Python的字典（相当于hash表），用于求解最优解步数最多的8个状态（图6）。得到的结果如表1。表1第1列为基本状态坐标，每个棋子的坐标用一维棋子坐标表示。第2列和第3列为运行时间对比。时间保留4位小数，单位是ms。文献[5]是用C#实现的算法，C#是编译型静态语言。Python是动态语言，对于执行CPU密集型的算法，C#程序的效率要明显高于Python。但是，同样用Python实现文献[5]和本文算法，在同样的硬件上运行，在语言和硬件层面，两个算法是公平的。由表1可知，基于hash表的算法寻找最优解的时间较短，个别小于0.001ms。从理论上分析，时间复杂度0（1）要低于0（V+E），所以表1的时间从理论上分析也是合理的。

6结束语

针对目前华容道算法的效率问题，利用排列算法求得华容道游戏所有可能的状态，删除不合法的状态后，对每一种状态求解，将每种状态及最优解保存在hash表中。本质是将图的遍历算法转化成查询hash表，将时间复杂度由0（V+E）降为接近0（1）。理论分析和实验结果表明，利用hash表解决华容道问题可以减少找到最优解的时间。