X算法

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

基本介紹

• 中文名：X算法
• 縮寫：DLX

X算法的步驟

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

X算法的步驟如下：

1. 如果矩陣A為空（沒有任何列），則當前局部解即為問題的一個解，返回成功；否則繼續。
2. 根據一定方法選擇第c列。如果某一列中沒有1，則返回失敗，並去除當前局部解中最新加入的行。
3. 選擇第r行，使得A_r,c= 1（該步是不確定的）。
4. 將第r行加入當前局部解中。
5. 對於滿足A_r,j= 1的每一列j，從矩陣A中刪除所有滿足A_i,j= 1的行，最後再刪除第j列。
6. 對所得比A小的新矩陣遞歸地執行此算法。

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

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

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

實現

高德納主要想通過X算法體現舞蹈鏈的實用性。他發現了使用舞蹈鏈的X算法效率極高，並把這一過程稱為DLX。DLX用矩陣來表示精確覆蓋問題，在內部的存儲結構為舞蹈鏈。舞蹈鏈是一個雙向環形鍊表，每個矩陣中的1都有一個指針指向其左、右、上、下的1。因為精確覆蓋問題中的矩陣一般都是稀疏的，所以舞蹈鏈中的元素很少，既很省時間，又很省空間。可見使用舞蹈鏈的DLX算法無論在選擇行時還是回溯錯誤的選擇時效率都很高。