前幾天聽了 CMU 一大神的算法公開課，算是近距離見識了算法大神的冰山一角洋访，管中窺豹镣陕，可見一斑。
先稍微介紹一下大神姻政，方便感興趣的童鞋進一步了解他呆抑。
- 姓名：王赟 Maigo
想了解更多的就自己谷歌吧。知乎專欄就夠看好久的了汁展。
我寫這篇文字的目的很簡單鹊碍，
- 分享給需要的和感興趣的同學(xué)
- 看了好幾遍視頻，還是想自己從頭到尾復(fù)述一遍以加深印象食绿，熟悉 bit 的操作侈咕。
算法的所有代碼，java 版本和 swift 版本器紧，我都放在了我的 Github 上耀销。當(dāng)然還有歡迎訂閱我的博客。
為了找工作過 OA 關(guān)铲汪，也是沒辦法用 swift熊尉，更不想用 C++，還不如臨時學(xué) java 來的效率點桥状。所以這里就用 java 代碼來講解一下帽揪。我這里用的是 “15 queens”，共5個方法辅斟，第四個開始速度有了質(zhì)的提升转晰，但需要第三個方法的基礎(chǔ)，反正后一個的提升都基于前一個士飒。
Queen 1
我自己的電腦上跑的時間是// Time elapsed: 28423ms查邢。用的是最基礎(chǔ)的回溯法（back tracking）。最后就不把所有的解都打印出來了酵幕，打印的時間其實和算法本身關(guān)系并不大扰藕，而且因為是15 皇后，容易死機芳撒。
public class Main {
private static final int n = 15;
private static int count = 0;
private static int[] sol;
public static void main(String[] args) {
sol = new int[n];
long tic = System.currentTimeMillis();
DFS(0);
long toc = System.currentTimeMillis();
System.out.println("Total solutions: " + count);
System.out.println("Time elapsed: " + (toc - tic) + "ms");
}
private static void DFS(int row) {
for (int col = 0; col < n; col++) {
boolean ok = true;
// 注意下面這個循環(huán)邓深，后面會做改進
for (int i = 0; i < row; i++) {
if (col == sol[i] || i - row == sol[i] - col || i - row == col - sol[i]) {
ok = false;
break;
}
}
if (!ok) continue;
sol[row] = col;
if (row == n - 1) {
count++;
} else {
DFS(row + 1);
}
}
}
}
Queen 2
Queen1 的時間是：// Time elapsed: 28423ms
這個方法的時間是：// Time elapsed: 16024ms
這里就需要開始介紹一個小竅門未桥，因為上面的方法，每次都要和之前的所有行相比較（看上面代碼的注釋部分）芥备，如果我們可以用一個 boolean 數(shù)組冬耿，記錄下每一列，每一個對角線的情況萌壳，就可以不用所有都比較了亦镶。那么如何求行和列呢
如上圖，一共有 2n － 1 個對角線袱瓮，大神是語言研究所的博士生缤骨，他用的是中文的“豎”，“撇”和“捺”來表示兩種對角線尺借，可以很容易知道它們的 index 就是 0 -> 2n - 2绊起。所以上面的代碼注釋部分就可以改成：
int j = col + row, k = n - 1 + col - row;
if (shu[col] || pie[j] || na[k]) continue;
就是如果當(dāng)前列和對角線都被占用的話淌哟，就直接 continue侍瑟。當(dāng)然我們還需要設(shè)置和清除。把已經(jīng)被占用的設(shè)為 true，一趟完事了就重新設(shè)為 false瘫里。
shu[col] = true; pie[j] = true; na[k] = true;
DFS(row + 1);
shu[col] = false; pie[j] = false; na[k] = false;
Queen 3
Queen1 ：// Time elapsed: 28423ms
Queen2 ：// Time elapsed: 16024ms
這個方法：// Time elapsed: 10302ms
從這個方法開始引入 bit array，關(guān)鍵點是:
用 32 位的 bit array（也就是一個整數(shù)（int）的長度）荡碾，代替 32 位長度的 boolean 谨读。
位運算的基本操作是：與，或坛吁，異或劳殖，取反，左移拨脉，右移哆姻。很容易理解，這里瞬間就節(jié)省了超多的空間玫膀。也很容易就想到這里并不會節(jié)省時間很多時間矛缨，因為整個的流程是沒什么太大的區(qū)別的。所以上面的 boolean[] shu, pie, na; 就成了 int shu, pie, na;帖旨，默認為 0箕昭。上面的判斷條件也成了
if ((((shu >> col) | (pie >> (col + row)) | (na >> (n - 1 + col - row))) & 1) != 0) continue;
這個乍一看有點復(fù)雜，先看一下這個 bit 是如何模擬數(shù)組操作的解阅，其實就是讀和寫：
－ 寫
把第 i 位置1：a |= (1 << i)
把第 i 位置0: a &= ~(1 << i)
把第 i 位取反：a ^= (1 << i)
－ 讀
讀取第 i 位的值：(a >> i)&1
所以上面那個條件其實就是取第col位的值 (shu >> col) & 1落竹，每個都是這樣，所以就先把三個都|或起來货抄，再和 1 &與述召。操作是等價的朱转，存儲空間不同而已。后面的設(shè)置與清除也成了：
shu ^= (1 << col); pie ^= (1 << (row + col)); na ^= (1 << (n - 1 + col - row));
就是把shu的第col位置1积暖，本來是0肋拔，取反就成了1。用異或的好處就是清除和設(shè)置的代碼相同呀酸，更方便凉蜂。
Queen 4
Queen1 ：// Time elapsed: 28423ms
Queen2 ：// Time elapsed: 16024ms
Queen3 ：// Time elapsed: 10302ms
這個方法：// Time elapsed: 1962ms
可以從上面這個時間比較看出來瞬間少了個數(shù)位。因為這一方法用到了系統(tǒng)級別的運算性誉，利用了 bit array 可以一步操作多位的優(yōu)勢窿吩，不像一般的 array，必須要一個一個操作错览，而 bit array 可以在一個整形的長度內(nèi)纫雁，O(1) 時間任意存取任意位置的數(shù)。為了更好的理解這個方法倾哺，這里我們需要介紹另一個 bit 的操作轧邪，取最后一個 1:
a & -a
懂負數(shù)的原理就很容易理解了，負數(shù)就是取反＋1羞海。例子：
a = 0001100
-a = 1110011 + 1 = 1110100
a & -a = 0000100
枚舉 bit array 中的1忌愚，就是：
while(a != 0) {
int p = a & -a; // p 就是取出來的 1
a ^= p;
Do something with p;
}
之前是枚舉每個位置，然后檢查是否沖突却邓，而現(xiàn)在我們可以利用這點硕糊，直接枚舉不沖突的位置。那么在第 row 行腊徙，相應(yīng)的shu简十，pie，na中沖突的位置在哪里呢撬腾？
shu 沖突的位置：shu
pie 沖突的位置：pie >> row
na 沖突的位置：na >> (n - 1 - row)
就是之前式子 pie[row ＋ col], na[n - 1 + col - row] 的一個變形螟蝙，用 bit array 來代替普通的 boolean array。所以現(xiàn)在這個 DFS 方法就成了：
private static void DFS(int row) {
int ok = ((1 << n) - 1) & ~(shu | (pie >> row) | (na >> (n - 1 - row)));
while (ok != 0) {
int p = ok & -ok;
ok ^= p;
if (row == n - 1) {
count++;
} else {
shu ^= p; pie ^= (p << row); na ^= (p << (n - 1 - row));
DFS(row + 1);
shu ^= p; pie ^= (p << row); na ^= (p << (n - 1 - row));
}
}
}
Queen 5
Queen1 ：// Time elapsed: 28423ms
Queen2 ：// Time elapsed: 16024ms
Queen3 ：// Time elapsed: 10302ms
Queen4 ：// Time elapsed: 1962ms
這個方法：// Time elapsed: 1350ms
為了更好的理解這個方法民傻，這里有個 google developer 的文檔胰默，講的是 Propagation and backtracking。所謂的 Propagation饰潜，就是：
Propagation consists of taking some constraint—which might be a constraint of the original problem, or a constraint learned or hypothesized along the way—and applying it to variables.
利用之前學(xué)到的初坠，來限制接下來的。
這個方法中彭雾，我們把 shu碟刺，pie，na 都當(dāng)成形參薯酝，把當(dāng)前行學(xué)到的“不能放”的限制信息半沽，保留到下一行爽柒，從而限制下一行的決策。這也就是 Propagation 的意思者填。所以我們的代碼也就成了
public class Main {
private static final int n = 15;
private static int count = 0;
public static void main(String[] args) {
long tic = System.currentTimeMillis();
DFS(0, 0, 0, 0);
long toc = System.currentTimeMillis();
System.out.println("Total solutions: " + count);
System.out.println("Time elapsed: " + (toc - tic) + "ms");
}
private static void DFS(int row, int shu, int pie, int na) {
// shu, pie, na 當(dāng)前行的位置不能放
int ok = ((1 << n) - 1) & ~(shu | pie | na);
while (ok != 0) {
int p = ok & -ok;
ok ^= p;
if (row == n - 1) {
count++;
} else {
// 把當(dāng)前行的 shu浩村，pie，na 設(shè)為 0占哟，從而之后的所有行都不能放
DFS(row + 1, shu ^ p, (pie ^ p) >> 1, (na ^ p) << 1);
}
}
}
}
