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

周揚(yáng) 陳伊琳 韋妮君 周一諾

關(guān)鍵詞：華容道；時(shí)間復(fù)雜度；hash表

1引言

目前對(duì)華容道算法的優(yōu)化主要集中在改進(jìn)搜索策略和減少搜索狀態(tài)[1-2]，即基于深度優(yōu)先或廣度優(yōu)先的改進(jìn)。這兩種算法的時(shí)間復(fù)雜度都為O（V+E）[3]，其中V為頂點(diǎn)數(shù)，E為邊數(shù)。對(duì)于華容道游戲，可以將棋盤上的每個(gè)狀態(tài)看作一個(gè)頂點(diǎn)，最小正方形棋子的大小視為1*1，則棋盤的大小為4*5，共20個(gè)位置。為了估算不考慮棋子重合情況，所有狀態(tài)數(shù)就是在20個(gè)位置上放10個(gè)棋子的排列，共A=670442572800種狀態(tài)，即便除去棋子重合的非法情況，也有65 880種狀態(tài)。保守估算1個(gè)狀態(tài)對(duì)應(yīng)2條邊，則對(duì)于華容道游戲頂點(diǎn)和邊總數(shù)約為65880*3=197640。深度優(yōu)先和廣度優(yōu)先算法本質(zhì)是在以萬(wàn)為數(shù)量級(jí)的狀態(tài)中找到最優(yōu)解。實(shí)際情況是，幾個(gè)經(jīng)典開局都要搜索約2萬(wàn)個(gè)狀態(tài)，效率較低。

鑒于此，可以考慮：（1）能否求出華容道一共幾種狀態(tài)？（2）是否能將所有狀態(tài)枚舉出來？（3）存儲(chǔ)所有狀態(tài)和對(duì)應(yīng)最優(yōu)解所需的內(nèi)存空間能否接受？如果這3個(gè)問題都是肯定回答，那么就可以提前將狀態(tài)和對(duì)應(yīng)的最優(yōu)解存人hash表。下文將分析這3個(gè)問題。

2基本定義

定義1狀態(tài)：10個(gè)棋子在棋盤的排列方式。

定義2棋盤坐標(biāo)系：棋盤左上角為坐標(biāo)原點(diǎn)D（0，0）；從坐標(biāo)原點(diǎn)出發(fā)，水平向右為x軸正方向，長(zhǎng)度為4；垂直向下為y軸正方向，長(zhǎng)度為5，x與y為整數(shù)。

定義6狀態(tài)坐標(biāo)：是一個(gè)長(zhǎng)度為10的數(shù)組。第0～3個(gè)元素分別為趙云，馬超，張飛，黃忠；第4～7個(gè)元素分別為兵1，兵2，兵3，兵4；第8個(gè)元素為關(guān)羽；第9個(gè)元素是曹操。

定義7

基本狀態(tài)坐標(biāo)：是一個(gè)長(zhǎng)度為10的數(shù)組。第O—3個(gè)元素分別為4個(gè)1*2型棋子的坐標(biāo)，順序記為AIA2A3A4；第4～7個(gè)元素分別為4個(gè)1*1型棋子的坐標(biāo)，按順序記為BIB28384。其中，1*2型和1*1型棋子坐標(biāo)按y從小到大的順序排列，若y相等，則再按x從小到大的順序排列。第8個(gè)元素為2*1型棋子的坐標(biāo)，記為C：第9個(gè)元素是2*2型棋子的坐標(biāo)，記為D。

圖1和圖2是兩個(gè)不同狀態(tài)，有不同的狀態(tài)坐標(biāo)，但有相同的基本狀態(tài)坐標(biāo)。

定義8

基本狀態(tài)：基本狀態(tài)坐標(biāo)對(duì)應(yīng)的狀態(tài)定義為基本狀態(tài)。

3枚舉所有合法狀態(tài)

3.1位置排列轉(zhuǎn)化為一維狀態(tài)坐標(biāo)

根據(jù)一維棋子坐標(biāo)的定義，d=0，20）。根據(jù)文獻(xiàn)[4]排列的定義及計(jì)算方法，從整數(shù)[0，20）取10個(gè)整數(shù)的排列共有P（20，10）種。每一種排列都是一個(gè)長(zhǎng)度為10的數(shù)組，若將該種數(shù)組當(dāng)作一個(gè)基本狀態(tài)坐標(biāo)（數(shù)組中的每個(gè)數(shù)值對(duì)應(yīng)一個(gè)一維棋子坐標(biāo)），不考慮棋子重合的非法狀態(tài)，理論上共有P（20，10）=670442572800種狀態(tài)。

3.2合法狀態(tài)篩選

算法1

驗(yàn)證狀態(tài)坐標(biāo)是否合法

產(chǎn)生不合法狀態(tài)的原因是排列組合算法沒有考慮棋盤的形狀和棋子的形狀。比如，某個(gè)1*2型的棋子的坐標(biāo)是（0，4），棋子就會(huì)超出棋盤范圍；若某個(gè)1*2型的棋子的坐標(biāo)是（0，0），另外一個(gè)1*1型棋子的坐標(biāo)是（1，0），這就會(huì)造成棋子重合。篩選合法狀態(tài)本質(zhì)上是從所有狀態(tài)中去除超出棋盤范圍和棋子重合的情況，具體步驟如算法1所示。

4壓縮存儲(chǔ)

根據(jù)定義6和定義7．對(duì)于任意一個(gè)狀態(tài)坐標(biāo)，都能求得其對(duì)應(yīng)的基本狀態(tài)坐標(biāo)。比如，記下“張飛”對(duì)應(yīng)A1，那么可由基本狀態(tài)坐標(biāo)還原成狀態(tài)坐標(biāo)?；谶@個(gè)事實(shí)，可以只存儲(chǔ)基本狀態(tài)坐標(biāo)和其對(duì)應(yīng)的最優(yōu)解。對(duì)于基本狀態(tài)坐標(biāo)，有A1～A4，B1～B4，C，D共10種棋子（圖3）。根據(jù)定義2，x軸的值為[0，4）的整數(shù)，y軸的值為[0，5）的整數(shù)，所以保存x軸的坐標(biāo)需要2bit，保存v軸坐標(biāo)需要3bit，保存一個(gè)棋子的坐標(biāo)共需要5bit，10個(gè)棋子共需要50bit（圖4），即7個(gè)字節(jié)即可保存一個(gè)基本狀態(tài)坐標(biāo)。但是，考慮到實(shí)際程序?qū)崿F(xiàn)方便，用64位的整數(shù)（8字節(jié)）存儲(chǔ)基本狀態(tài)坐標(biāo)。根據(jù)算法1，求得65880種合法狀態(tài)，對(duì)應(yīng)65880個(gè)基本狀態(tài)坐標(biāo)。

用改進(jìn)的深度優(yōu)先算法[5]，可得到53954種基本狀態(tài)有解。一個(gè)狀態(tài)占用8字節(jié)，存儲(chǔ)53954種約占421KB。由實(shí)驗(yàn)結(jié)果可知．53954種有解的基本狀態(tài)中，最優(yōu)解最多為126步，1字節(jié)就能表示。共有10個(gè)不同棋子，需要4bit表示，移動(dòng)方向有上下左右4種，要2bit表示。因此，表示移動(dòng)一步要用6bit。實(shí)驗(yàn)部分為了實(shí)現(xiàn)方便，用1字節(jié)表示移動(dòng)一步。如圖5所示，0—7個(gè)字節(jié)為基本狀態(tài)坐標(biāo)。第8個(gè)字節(jié)為該基本狀態(tài)坐標(biāo)的最優(yōu)解有幾步。假定第8個(gè)字節(jié)為116，那么之后的116個(gè)字節(jié)表示116步具體內(nèi)容。116個(gè)字節(jié)之后的8個(gè)字節(jié)又是下個(gè)基本狀態(tài)坐標(biāo)，以此類推。如圖6所示。

5實(shí)驗(yàn)

上文已經(jīng)討論過華容道游戲共有P（20，10）種狀態(tài)，執(zhí)行算法1后，得到65880種合法狀態(tài)。再執(zhí)行文獻(xiàn)[5]的算法求得53954種基本狀態(tài)有解。用Python實(shí)現(xiàn)該過程，把基本狀態(tài)坐標(biāo)及對(duì)應(yīng)的最優(yōu)解保存成第4節(jié)討論的二進(jìn)制文件。結(jié)果表明，該文件僅2.8 MB。將該文件存人Python的字典（相當(dāng)于hash表），用于求解最優(yōu)解步數(shù)最多的8個(gè)狀態(tài)（圖6）。得到的結(jié)果如表1。表1第1列為基本狀態(tài)坐標(biāo)，每個(gè)棋子的坐標(biāo)用一維棋子坐標(biāo)表示。第2列和第3列為運(yùn)行時(shí)間對(duì)比。時(shí)間保留4位小數(shù)，單位是ms。文獻(xiàn)[5]是用C#實(shí)現(xiàn)的算法，C#是編譯型靜態(tài)語(yǔ)言。Python是動(dòng)態(tài)語(yǔ)言，對(duì)于執(zhí)行CPU密集型的算法，C#程序的效率要明顯高于Python。但是，同樣用Python實(shí)現(xiàn)文獻(xiàn)[5]和本文算法，在同樣的硬件上運(yùn)行，在語(yǔ)言和硬件層面，兩個(gè)算法是公平的。由表1可知，基于hash表的算法尋找最優(yōu)解的時(shí)間較短，個(gè)別小于0.001ms。從理論上分析，時(shí)間復(fù)雜度0（1）要低于0（V+E），所以表1的時(shí)間從理論上分析也是合理的。

6結(jié)束語(yǔ)

針對(duì)目前華容道算法的效率問題，利用排列算法求得華容道游戲所有可能的狀態(tài)，刪除不合法的狀態(tài)后，對(duì)每一種狀態(tài)求解，將每種狀態(tài)及最優(yōu)解保存在hash表中。本質(zhì)是將圖的遍歷算法轉(zhuǎn)化成查詢hash表，將時(shí)間復(fù)雜度由0（V+E）降為接近0（1）。理論分析和實(shí)驗(yàn)結(jié)果表明，利用hash表解決華容道問題可以減少找到最優(yōu)解的時(shí)間。