【算法】從少女前線重裝部隊，到NP問題、精確覆蓋和DLX算法

2019-10-25 20:31 作者:命運の樂章 0人讀過 | 我要投稿

* 注：本文主要內(nèi)容為?算法，屬?計算機/軟件/數(shù)學(xué)?領(lǐng)域，游戲內(nèi)容僅為背景，請讀者悉知

重裝部隊芯片拼接

《少女前線》游戲中，你擁有數(shù)支重裝部隊，每一個部隊都有特殊的裝備槽（重裝回路），給她們配備裝備（芯片）可以增加戰(zhàn)斗屬性。

不過給重裝部隊“穿裝備”是件很麻煩的事情。重裝部隊的“裝備”是形狀各異的?俄羅斯方塊?芯片，她們的“裝備槽”是不同形狀的插槽，插入插槽不允許重疊。芯片由1x1正方形小格組成，可以旋轉(zhuǎn)90°、180°、270°，芯片每一格都帶有屬性加成，插槽塞的越滿“套裝效果”（同色諧振）越好，所以首先要做的就是把芯片插槽盡可能拼滿！

于是乎玩家饒有興致的拼起來了……一番折騰后發(fā)現(xiàn)終于拼滿了，可是屬性不好??！換芯片又得重新拼別的形狀……辣么多芯片，還得考慮多種屬性組合最優(yōu)……何時是個頭啊！

量大的情況人力無法解決，我們就用計算機，就寫代碼！

問題抽象

為了讓計算機幫我們解決運算問題，我們首先要把芯片和回路進行數(shù)學(xué)抽象。二維的回路我們可以從左往右、從上往下拉伸成一維數(shù)組。被芯片占據(jù)的地方記1，空的地方記0。我們以簡單的九宮格示例：

什么都沒放的回路必然是全為0數(shù)組，那么怎么將芯片放進去呢？不難發(fā)現(xiàn)，全滿的回路其實就是將不同芯片單獨放置在對應(yīng)位置，再將數(shù)組按位置求和：

一個芯片，一種旋轉(zhuǎn)角度，放在空回路的一個可行位置，我們將這個放置的回路數(shù)組稱為放置行。所有芯片和回路的形狀都是固定的，那么對于給定的一組芯片，我們先將所有芯片所有放置單元先求出來，以上圖為例，只需要選出7個屬于不同芯片的放置行，使其能夠求和為全1矩陣就行了！

上述問題數(shù)學(xué)中稱為“精確覆蓋”

精確覆蓋

在一個全集X中若干子集的集合為S，精確覆蓋是指，S的子集S*，滿足X中的每一個元素在S*中恰好出現(xiàn)一次。

——百度百科《精確覆蓋問題》

我們需要解決的問題是精確覆蓋的特殊問題：零一精確覆蓋，即全集X為全1矩陣，子集元素僅為0或1。通俗來講，就是選出幾個01行，對應(yīng)位置相加剛好加出全為1的行。

零一精確覆蓋問題是NP問題。

NP問題

即非確定性多項式（Nondeterministic Polynomially）問題，指一個復(fù)雜問題不能確定是否在多項式時間內(nèi)找到答案，但是可以在多項式時間內(nèi)驗證答案是否正確。

也就是說，芯片拼接問題處理時間會隨著芯片數(shù)量增加而非多項式時間增加，這種增加趨勢近乎于階乘。

解決芯片拼接問題最簡單的辦法就是窮舉法：把所有芯片所有放置方法都試一遍就行了！然而實際上，以6x6回路為例，對于形狀限定在九宮格內(nèi)的芯片，一共有36種放置方法（4x旋轉(zhuǎn)3x橫移3x豎移）。那么假設(shè)玩家有100個芯片，每7個芯片有可能組成回路，粗略估算有8,000,000,000,000,000,000種需要驗證的組合！（電腦：我也遭不住?。。?/span>

一般解決NP問題都會根據(jù)問題的特性，基于窮舉進行優(yōu)化，很多組合大類可以在很早就被否定掉，這種思路叫剪枝。以芯片拼接為例，假設(shè)前兩個芯片已經(jīng)出現(xiàn)重疊，那么后面的就不用試了。解決零一精確覆蓋的高效算法之一，就是“舞蹈鏈算法”（Dancing Link X），簡稱DLX。

DLX

該算法剪枝思路是提前消除沖突行的試探回溯法，具體步驟：

將所有01行合并為矩陣，創(chuàng)建一個棧S（棧Stack：數(shù)據(jù)結(jié)構(gòu)，類似堆放椅子，從棧中取元素稱為出棧，只能取最后放入的元素，即先入后出）
選擇一行為當(dāng)前行，默認從當(dāng)前矩陣第1行開始選
檢查當(dāng)前行所有元素為1的對應(yīng)列，我們稱這些列為沖突列。除當(dāng)前行外，其他行在該列元素如果為1，則必將與當(dāng)前行沖突，稱為沖突行。標記所有沖突行，并將當(dāng)前行的行號入棧S
刪除當(dāng)前行、沖突列和沖突行。如果：（a）當(dāng)前矩陣0、1元素都包含，則返回第2步繼續(xù)（b）當(dāng)前矩陣為全1矩陣，算法結(jié)束，將所有剩余行的行號入棧（c）當(dāng)前矩陣為全0矩陣，或者為空矩陣，則先前選擇無法滿足條件?；貪L至約簡前的矩陣，S出棧，并選擇S出棧行號的下一行。如果已經(jīng)是最后一行，那么繼續(xù)回滾，直到能選擇下一個當(dāng)前行，或者退回初始矩陣
如果：（a）退回到初始矩陣，且不能選擇下一行，那么所給集合沒有零一精確覆蓋解（b）矩陣為全1，則S中的行號為滿足零一精確覆蓋的對應(yīng)行號

我們看如下例子：我們從3個備選行 [1,0,1,1]、[0,1,0,1]、[1,0,1,0] 中求精確覆蓋解。首先選取#1為當(dāng)前行，1、3、4列被標記為沖突列，檢查所有沖突列隨后將2、3行標記為沖突行。將當(dāng)前行行號#1入棧S，并刪除當(dāng)前行、沖突列和沖突行，發(fā)現(xiàn)矩陣為空，該次試探失敗。于是回滾至上一次矩陣，將S出棧。出棧得到上次選取行號=1，則本次選取#2為當(dāng)前行，2、4列被標記為沖突列，檢查所有沖突列隨后將1行標記為沖突行。將當(dāng)前行行號#2入棧S，并刪除當(dāng)前行、沖突列和沖突行，發(fā)現(xiàn)矩陣為全1矩陣，剩余行號#3入棧，算法成功結(jié)束。故得到零一精確覆蓋解為2、3行。

利用DLX求得全部圖解

實際操作需要增加額外判斷，行需要存儲所屬芯片序號，因為同一個芯片有很多放置行，但是一個芯片只能用一次。并且因為芯片和回路形狀各異，部分重裝可以空出一些格數(shù)依舊可以達到最高屬性（M2迫擊炮）。所以具體求圖解的步驟為：

將所有芯片形狀的所有旋轉(zhuǎn)角度，先以二維坐標表示，稱為基本形狀矩陣
回路設(shè)為8x8的零行，針對不同形狀，邊界外部分初始化為1即可
根據(jù)回路形狀，輸出所有形狀芯片所有旋轉(zhuǎn)的所有可能放置位置，用01行表示，這些01行的集合稱為位置矩陣
窮舉可能的芯片格數(shù)組合（例如：36格回路，可能由6個六格，或者1個六格+6個五格拼成），并進行DLX，且每一步迭代不選取已經(jīng)入棧的芯片編號。DLX結(jié)束條件更改為：必須執(zhí)行固定次數(shù)迭代，且最后一步不為空矩陣即可（保證M2這種特殊情況能被正確計算）
記錄每一個DLX的解，這種解包含兩條數(shù)據(jù)（a）放置行矩陣，即該圖解中，每一塊芯片的種類、旋轉(zhuǎn)、放置位置（b）芯片數(shù)索引，表示每類芯片用了多少個。因為圖解是固定的，所有圖解保存為本地文件，運行芯片計算時直接通過查表得到圖解，不需要再跑一遍DLX。放置行矩陣和芯片數(shù)索引詳見下圖：

DLX后續(xù)優(yōu)化

DLX對沖突行的判斷，可以將64位01串分成兩個32位01串 *，并將32位01串直接按二進制存儲為32位整形。判斷“有沒有同位為1”，本質(zhì)等價于“兩個32位整形按位求與≥0”（按位與：運算符&，兩個二進制數(shù)按位求與，同為1的位數(shù)保留1，否則保留0）按位運算速度比邏輯判斷快數(shù)百倍，在DLX成千億級的比較中可極大幅度優(yōu)化速度。 * 注：只所以8x8方陣的64位01穿要拆分成兩半，因javascript默認支持32位整形
計算最佳方案時，將芯片可能的組合列舉出來，根據(jù)總屬性（或增加篩選條件）進行排序，利用堆排序能加快速度