華容道算法基礎(chǔ)版

今天來聊聊華容道算法具體實(shí)現(xiàn)方法，華容道算法我會(huì)通過鏈表和紅黑樹兩種方法實(shí)現(xiàn)查找算法，程序體現(xiàn)出來的效率差別很大。

本篇文章拿華容道橫刀立馬做分析，華容道游戲下圖所示。游戲原理是每個(gè)方塊每次只可以移動(dòng)一個(gè)方格，如何將正方形移除到方塊外部。拿到這個(gè)需求我們首先需要構(gòu)建數(shù)學(xué)模型，該游戲設(shè)計(jì)到的方塊數(shù)量較少，走法也比較少，那么可以采取窮舉思想計(jì)算出最佳走法。

圖 1

?

當(dāng)方塊每移動(dòng)一步時(shí)，程序應(yīng)該獲取到當(dāng)前游戲盤面下一步可以執(zhí)行的路徑，如果不考慮去除重復(fù)狀態(tài)，那么程序每個(gè)盤面節(jié)點(diǎn)數(shù)量會(huì)成指數(shù)增加，這樣導(dǎo)致計(jì)算量太大。華容道效率出現(xiàn)在比較上，不同的查找策略會(huì)導(dǎo)致效率差別在幾十倍，幾百倍上。

???????? 游戲數(shù)學(xué)模型如下圖所示，程序應(yīng)該通過一個(gè)數(shù)據(jù)結(jié)構(gòu)保留查找過程中出現(xiàn)的所有狀態(tài)，本次采用鏈表。程序每走一步應(yīng)該獲取下一步可走的路徑，并且把可走路徑呈現(xiàn)的盤面結(jié)點(diǎn)保存到鏈表中，同時(shí)應(yīng)該剔除相同盤面結(jié)點(diǎn)。同時(shí)每個(gè)結(jié)點(diǎn)還會(huì)有結(jié)點(diǎn)指針指向下一個(gè)盤面和指向父盤面，保留這個(gè)指針的意義在于，當(dāng)程序找到了方塊最終應(yīng)該有的狀態(tài)，程序可以通過父指針回溯到最佳捷徑路徑，然后通過棧先進(jìn)后出策略完成最終路徑尋找。

圖 2

?

程序思路已經(jīng)很清楚，如何構(gòu)造每個(gè)盤面結(jié)點(diǎn)呢？早期由于計(jì)算機(jī)內(nèi)存比較小，華容道算法都采取犧牲性能來換取內(nèi)存空間，一個(gè)盤面采用一個(gè)int就可以表示完全。盤面和走法圖片來源于網(wǎng)絡(luò)。

圖 3 盤面表示方法

?

圖 4 程序走法思想

?

上圖是用性能換內(nèi)存思想，現(xiàn)在電腦的內(nèi)存都比較大，盤面編碼方式也隨之改變，本次編碼采用最簡(jiǎn)單的數(shù)字編碼，整個(gè)游戲盤面是5*4=20方格，編碼方式如下如圖所示。

圖 5

其實(shí)這種編碼方式效率比較低，如果2和5對(duì)調(diào)其實(shí)是一種狀態(tài)，本次實(shí)驗(yàn)為了簡(jiǎn)單，由淺入深分析算法效率。下面開始代碼編寫環(huán)節(jié)。盤面結(jié)點(diǎn)與初始值狀態(tài)值如下所示，state二維數(shù)組用來存儲(chǔ)每個(gè)結(jié)點(diǎn)的實(shí)際值,并且賦值為橫刀立馬的初始值。

圖 6

?

判斷下一步可以的走法，采取遍歷二維數(shù)組方式。

圖 7

每次判斷得到新的狀態(tài)，鏈接到c這個(gè)鏈表后面，上圖的整個(gè)循環(huán)是獲取當(dāng)前盤面的可走的所有方法，在得到可走的路徑時(shí)需要判斷是否與以前盤面結(jié)點(diǎn)重復(fù)。如何判斷下一步可走，下面只列舉正方形的走法。其他的棋子走法請(qǐng)看源代碼。正方形走法如下所示。

?

?

圖 8

?

如何判斷重復(fù)比較重要的環(huán)節(jié)，本次同樣采用效率最低的遍歷去判斷重復(fù)，重鏈表頭比對(duì)到鏈表尾巴，每個(gè)結(jié)點(diǎn)狀態(tài)通過一一比較數(shù)組的值來判斷當(dāng)前盤面是否重復(fù)，這個(gè)編碼方式與判斷重復(fù)是最簡(jiǎn)單的，但效率是最低的，下篇文章提高效率。

圖 9

棋子連續(xù)走幾步解決方案，當(dāng)前從棋子布局初始狀態(tài)變化到如下狀態(tài)，如果按照一步一步走法算，這個(gè)路徑是兩步，如果棋子可以拐彎或者走幾步，那么達(dá)到現(xiàn)在這個(gè)狀態(tài)最多算一步。本次實(shí)驗(yàn)沒有優(yōu)化這個(gè)代碼，下篇文章會(huì)提供優(yōu)化好的華容道算法。

?

本次實(shí)驗(yàn)結(jié)果是，該程序運(yùn)行花費(fèi)時(shí)間為2~3小時(shí)，下篇文章優(yōu)化效率后時(shí)間不到10ms。

?

源碼下載：https://download.csdn.net/download/qq_21792169/11044867