基本介紹
- 中文名:X算法
- 縮寫:DLX
X算法的步驟,實現,
X算法的步驟
X算法用由0和1組成的矩陣A來表示精確覆蓋問題,目標是選出矩陣的若干行,使得其中的1在所有列中出現且僅出現一次。
X算法的步驟如下:
- 如果矩陣A為空(沒有任何列),則當前局部解即為問題的一個解,返回成功;否則繼續。
- 根據一定方法選擇第c列。如果某一列中沒有1,則返回失敗,並去除當前局部解中最新加入的行。
- 選擇第r行,使得Ar,c= 1(該步是不確定的)。
- 將第r行加入當前局部解中。
- 對於滿足Ar,j= 1的每一列j,從矩陣A中刪除所有滿足Ai,j= 1的行,最後再刪除第j列。
- 對所得比A小的新矩陣遞歸地執行此算法。
選擇r的不確定性意味著算法將派生出若干獨立的子算法,每個子算法都從其父算法中繼承了去除部分行列的A矩陣。如果其中有一列全為零,則當前情況無解,子算法返回失敗,但不一定意味整個問題無解。
第二步中,無論用什麼方法選擇列最終都可以得到解,但有的方法效率明顯較高。為減少疊代次數,高德納建議每次都選取1最少的列。