一、可優化的地方
上一節實現的代碼從運行效率上看，有兩個重大缺陷：
1、每次遞歸調用前，需要將當前的狀態矩陣拷貝一份，然後刪除和當前行相交的所有行和列，得到新的矩陣，當矩陣非常大時，拷貝操作所需的時間和空間都很大。
2、在實際情況中，矩陣M一般是稀疏矩陣，0的個數遠遠多於1的個數，如果我們能只處理含1的單元格的話，將大大提高運行的時空效率。
二、優化所用到的數據結構
以下優化算法是Knuth提出來的，其主要思想是用十字鏈表存儲矩陣中的所有1.具體敘述如下
1、首先定義一個通用的十字鏈表節點類
[cpp] struct CNode
{
CNode* Left; //左節點指針
CNode* Right; //右節點指針
CNode* Up; //上節點指針,對列節點，則為本列最後一個元素的指針
CNode* Down; //下節點指針,對列節點，則為本列第一個元素的指針
int name; //對普通節點，為所在子集的編號,即行號;
//對列節點，為列編號
};
struct CNode
{
CNode* Left; //左節點指針
CNode* Right; //右節點指針
CNode* Up; //上節點指針,對列節點，則為本列最後一個元素的指針
CNode* Down; //下節點指針,對列節點，則為本列第一個元素的指針
int name; //對普通節點，為所在子集的編號,即行號;
//對列節點，為列編號
};
2、然後從上面的節點類派生出一個列標題類，這個列標題多了一個size數據域，用於存儲本列元素的個數，即
struct CColumnHead:public CNode
{
int size; //本列元素的個數
};
3、數據節點類，存儲原矩陣裡的每個1，
[cpp] struct CGrid:public CNode
{
CColumnHead* columnHead; //列頭節點的指針
};
struct CGrid:public CNode
{
CColumnHead* columnHead; //列頭節點的指針
};4、建立一個頭節點，指向列標題雙向鏈表，以及存放可行解的變量。
[cpp] set<int> solution; //存放可行解
CColumnHead* master; //列頭鏈表的頭節點
set<int> solution; //存放可行解
CColumnHead* master; //列頭鏈表的頭節點
三、核心函數
算法的核心是兩個函數。
1、cover函數
cover函數，輸入是一個列號c，函數流程的偽代碼為
(1)將列c整個的從列頭鏈表中摘除
(2)從列c的第一個數據節點開始向下遍歷列c的所有數據節點r，都每個r都執行如下操作：
a、從r 的右側開始向右遍歷r 所在行的其他節點cell,對每個cell執行如下操作
b、設cell的所在列號為n，將cell從其所在列n中摘除，列標題n的size域的值減1
總體來說cover函數的目的是將和這個列相關的所有節點從矩陣中刪除。
2、cover的執行實例
下面看一個實例，假設
矩陣的當前狀態為，括號中的數字表示該列的含1個數,h為列頭鏈表的頭節點，開始指向第一列
[cpp] > 1(2) 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
h-> 1(2) 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1 矩陣1 ——原始矩陣
現在要將列1及其相關節點從矩陣中摘除，則具體過程是
(1)將列1從矩陣中整體摘除，此時h指向列2，矩陣的狀態為
[cpp] -> 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 0 0 1 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
h-> 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 0 0 1 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 矩陣2——摘除列1之後的矩陣
注：列1雖然從矩陣中整體摘除，但它的自身信息並未發生變化，列1的原始信息仍然為
[cpp] 1(2)
A 1
B 1
C 0
D 0
E 0
F 0
1(2)
A 1
B 1
C 0
D 0
E 0
F 0 可見，和列1相關的行有A和B
下一步的任務就是將行A和B的其他節點從矩陣2中刪除，
(2) 首先在矩陣2中遍歷行A的所有數據節點（從第一列的右側向右開始遍歷），顯然，A和列4、列7中有交點，於是刪除這兩個節點，第4列和第7列的計數器值減1，
這樣整個行A就被從矩陣2中移走，現在得到的矩陣為
[cpp] h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(3)
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(3)
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 類似的，將行B的所有數據節點（只有第4列）從矩陣中摘除，各數據節點所在列的計數器值減1。此時矩陣M的新狀態為
[cpp] h->2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
h->2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 矩陣4 - 移走行B之後的狀態
從上面的過程可知，cover並未切斷被刪除元素與其他元素的橫向和縱向聯系，這樣就被恢復矩陣的狀態打下了基礎。
3、uncpver函數
uncover 函數的輸入也是一個列號c，它的功能與cover相反，是將列c插入到矩陣中，也就是將矩陣恢復到執行
cover(c)以前的狀態。
uncover的處理流程也正好和cover相反。
函數流程的偽代碼為
(1)從列c的最後一個數據節點開始，向上遍歷列c的所有數據節點r，都每個r都執行如下操作：
a、從r的左側開始向左遍歷其 所在行的其他節點cell,對每個cell執行如下操作
b、設cell的所在列號為n，將cell加入到列n中，列標題n的size域的值加1。
(2)將列c整個加入到從列頭鏈表中
4、uncover的執行實例
設現在的矩陣狀態為
[cpp] 2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
2(2) 3(2) 4(1) 5(2) 6(2) 7(3)
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1要插入的列號為1，且列1的信息為
[cpp] view plaincopyprint? 1(2)
A 1
B 1
C 0
D 0
E 0
F 0
1(2)
A 1
B 1
C 0
D 0
E 0
F 0 行A和B的信息為
2 3 4 5 6 7
A 0 0 1 0 0 1
B 0 0 1 0 0 0
那麼uncover的具體執行過程是
(1)首先將列4的最後一行B恢復到矩陣中，即將B的節點4恢復到矩陣中，且列4的計數器加1，矩陣狀態為
[cpp] h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(3)
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(3)
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 (2)然後將行A恢復到矩陣中，A的最後一個節點是7，所以先恢復列7的狀態，矩陣為
[cpp] -> 2(2) 3(2) 4(2) 5(2) 6(2) 7(4)
A 0 0 0 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
h-> 2(2) 3(2) 4(2) 5(2) 6(2) 7(4)
A 0 0 0 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 然後將節點4恢復到矩陣中，矩陣的狀態為
[cpp] h-> 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 0 0 1 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1
h-> 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 0 0 1 0 0 1
B 0 0 1 0 0 0
C 0 0 1 1 0 1
D 0 1 0 1 1 0
E 1 1 0 0 1 1
F 1 0 0 0 0 1 (3)最後將列1插入到矩陣中，矩陣為
[cpp]
1(2) 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1
1(2) 2(2) 3(2) 4(3) 5(2) 6(2) 7(4)
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1 至此，矩陣已完全恢復到cover(1)之前的狀態。
四、優化算法的基本步驟
算法的函數為search
1、如果矩陣為空，即 master->Right==master,則函數返回true
2、選擇含1數目最少的列，設其列標題為c
3、執行cover(c)
4、 遍歷列c的每一個數據節點r ，對每個r都執行(a)到(d)中的操作
(a) 從r的右側開始向右遍歷r所在行的所有其他節點cell，設cell所在裡的列頭節點為n，執行操作cover(n)
(b) 遞歸調用函數search，結果存到變量flag中
(c) 如果上一步的結果為真，將行r加入到解集中，然後返回true
(d) 如果步驟(b)的結果為false，則向從r的左側開始向左遍歷r所在行的所有其他節點cell，設cell所在裡的列頭節點為n
，執行操作uncover(n)
5、執行uncover(c)
6、函數返回false
分享到：
