[科普中國]-X算法

在計算機科學中，X算法可用來求解精確覆蓋問題。此名稱最早在高德納的論文《舞蹈鏈》中出現(xiàn)，他認為此算法是“試錯法中最顯而易見”的。就技術(shù)而言，X算法是一個深度優(yōu)先的不確定性回溯算法。由于X算法是一個解決精確覆蓋問題的簡潔方法，高德納希望通過該算法體現(xiàn)舞蹈鏈數(shù)據(jù)結(jié)構(gòu)的高效性，他把使用后者的X算法稱為DLX。

X算法的步驟X算法用由0和1組成的矩陣A來表示精確覆蓋問題，目標是選出矩陣的若干行，使得其中的1在所有列中出現(xiàn)且僅出現(xiàn)一次。

X算法的步驟如下：

如果矩陣A為空（沒有任何列），則當前局部解即為問題的一個解，返回成功；否則繼續(xù)。

根據(jù)一定方法選擇第c列。如果某一列中沒有1，則返回失敗，并去除當前局部解中最新加入的行。

選擇第r行，使得Ar,c= 1（該步是不確定的）。

將第r行加入當前局部解中。

對于滿足Ar,j= 1的每一列j，從矩陣A中刪除所有滿足Ai,j= 1的行，最后再刪除第j列。

對所得比A小的新矩陣遞歸地執(zhí)行此算法。

選擇r的不確定性意味著算法將派生出若干獨立的子算法，每個子算法都從其父算法中繼承了去除部分行列的A矩陣。如果其中有一列全為零，則當前情況無解，子算法返回失敗，但不一定意味整個問題無解。

實際上，所有子算法形成了一棵搜索樹，其中原問題為根節(jié)點，樹的第k層由子算法在第k次所選擇的行組成。整個算法即用回溯法對搜索樹深度優(yōu)先遍歷。

第二步中，無論用什么方法選擇列最終都可以得到解，但有的方法效率明顯較高。為減少迭代次數(shù)，高德納建議每次都選取1最少的列1。

實現(xiàn)高德納主要想通過X算法體現(xiàn)舞蹈鏈的實用性。他發(fā)現(xiàn)了使用舞蹈鏈的X算法效率極高，并把這一過程稱為DLX。DLX用矩陣來表示精確覆蓋問題，在內(nèi)部的存儲結(jié)構(gòu)為舞蹈鏈。舞蹈鏈是一個雙向環(huán)形鏈表，每個矩陣中的1都有一個指針指向其左、右、上、下的1。因為精確覆蓋問題中的矩陣一般都是稀疏的，所以舞蹈鏈中的元素很少，既很省時間，又很省空間?？梢娛褂梦璧告湹腄LX算法無論在選擇行時還是回溯錯誤的選擇時效率都很高。

本詞條內(nèi)容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學院工程熱物理研究所