這兩天在寫AI的課程實驗也物，趁剛剛完結實驗代碼宫屠，腦海中還有些思路，在此簡單總結一下滑蚯。
目錄
問題描述
2N皇后問題：給定一個n*n的棋盤±缩澹現要向棋盤中放入n個黑皇后和n個白皇后，使任意的兩個黑皇后都不在同一行告材、同一列或同一條對角線上坤次，任意的兩個白皇后都不在同一行、同一列或同一條對角線上斥赋。請盡量快地給出一組可行解缰猴。
關于N皇后問題
N皇后問題是一個很經典的問題，在大家最初學習算法的時候都有討論過疤剑』蓿回溯法是經典的解法，但是隨著N的增大隘膘，其復雜度的增加呈指數增長疑故。哪怕N只是為100，使用回溯解法的話弯菊，運行也要相當久的時間纵势。
簡單分析
對于2N皇后問題，很多同學的第一想法可能是兩次求解N皇后問題管钳，且第二次求解時為擺放位置設限钦铁。然而，這種做法不免顯得過于繁瑣才漆。
我們在這里牛曹，不妨先簡單地分析了一下幾種情況：
1. 當N為偶數時：其實只要求得一組可行解即可，另外一組可行解可以由當前解沿N*N矩陣的中軸線作對稱變換得到栽烂。因為N為偶數躏仇，所以不會存在黑白皇后位置沖突的情況。
例如：N=4時腺办，求得一組可行解為：3 1 4 2焰手，按著這個思路，變換得到另一組可行解為：2 4 1 3怀喉∈槠蓿可以判斷，這樣的兩組解合并起來是符合題目要求的。
2. 當N為奇數時：沿中軸線對稱的方式不再可行躲履，因為肯定有一個皇后會落在中軸線上见间。此時，可以考慮通過中心點作點對稱的情況工猜。
這里要注意米诉，如果求得的可行解存在關于中心點對稱的皇后擺放(或有皇后位于中心點)，那么此解不合要求篷帅，需要重新再求史侣；直到沒有兩個皇后的位置是關于中心點對稱的，另一組解可以通過對當前解關于中心點作點對稱變換得到魏身。
例如惊橱，N=5時，求得一組可行解為：2 4 1 3 5箭昵，按著這個思路税朴，變換得到另一組可行解為：1 3 5 2 4〖抑疲可以判斷正林，這樣的兩組解合并起來是符合題目要求的。
從上可以看出慰丛，其實2N皇后問題并不需要二次求解N皇后卓囚，在大多數情況下只需求得一組可行解即可瘾杭。
爬山算法
在介紹爬山算法之前诅病，我覺得很有必要先弄清楚什么是局部搜索。
局部搜索
從數學層面來理解粥烁，局部搜索是一種解決最優(yōu)化問題的啟發(fā)式算法贤笆。
對于某些計算起來非常復雜的最優(yōu)化問題，比如各種 NP 完全問題讨阻，要找到最優(yōu)解所需要的時間會隨問題規(guī)模的增大呈指數增長芥永，因此誕生了各種啟發(fā)式算法來退而求次地尋找局部最優(yōu)解，而局部搜索算法就是其中的一種算法钝吮。
局部搜索算法從某一狀態(tài)(而不是多條路徑)出發(fā)埋涧，通常只移動到與當前狀態(tài)相鄰的狀態(tài)。而在典型情況下奇瘦，搜索的路徑是不保留的棘催。盡管局部搜索算法不是系統(tǒng)化的求解方法，但是它有幾個關鍵的優(yōu)點：
1. 占用很少的內存耳标，通常情況下容量是常數級別的醇坝。
2. 經常能在不適合系統(tǒng)化算法的很大或者無限的（連續(xù)的）狀態(tài)空間中快速找出合理的解。
爬山算法簡介
爬山算法屬于局部搜索算法的一份子次坡，因此是一種解決最優(yōu)化問題的啟發(fā)式算法呼猪。
在實際運用中画畅，爬山算法不會前瞻與當前狀態(tài)不直接相鄰的狀態(tài)，只會選擇比當前狀態(tài)價值更好的相鄰狀態(tài)宋距，所以簡單來說轴踱，爬山算法是向價值增長方向持續(xù)移動的循環(huán)過程。
由于它的貪婪特性谚赎，使得在解決問題中容易陷入局部極大值(Local maxima寇僧，指一個比所有鄰居狀態(tài)價值要高但是比全局最大值要低的狀態(tài))，我們能采取隨機重啟(Random restart)以及模擬退火(Simulated annealing)的方法來改進沸版。本文的主要涉及的就是這兩種算法嘁傀。
先在這里簡單地說一下它們之間的區(qū)別，主要在于如何選擇下一狀態(tài)以及如何有效地得到全局最優(yōu)解：
1. 隨機重啟爬山算法：
求解過程中视粮，當得到了局部極大值時细办，如果不是全局最優(yōu)解，則隨機生成初始狀態(tài)蕾殴，重新求解笑撞，直到得到全局最優(yōu)解。
2. 模擬退火爬山算法：
基于隨機爬山算法钓觉，允許在隨機選擇相鄰狀態(tài)的時候有概率地選擇價值更小的狀態(tài)茴肥。在初期，向低價值狀態(tài)移動的概率高荡灾，隨著時間流逝該概率會越來越低瓤狐。(溫度逐漸降低，即"退火"批幌。)
算法實現與關鍵優(yōu)化
初始化
不同于一般的隨機初始化础锐。我實現時采用的初始化方式為：先依次為每一行的對應列擺上皇后，如第i 行荧缘，那么皇后就擺在第i 列皆警，之后再隨機選擇交換皇后所在列。
這樣做的優(yōu)點是可以保證在任一時刻截粗，每一行每一列都只有一個皇后信姓，大大縮小了搜索范圍，節(jié)省了程序運行時間绸罗。(從我的程序運行耗時可以明顯看出這一策略的優(yōu)越性意推。)
具體的實驗代碼如下：
/*初始化函數：在每行每列放置一個皇后*/
void generate_status(int* status) {
for (int i = 0; i < N; i++) {
status[i] = i;
}
/*隨機交換*/
srand((unsigned)time(NULL));
for (int i = 0; i < N; i++) {
int r = rand();
r = r % N;
swap(status[r], status[N - r - 1]);
}
}
評價函數
對于每一個狀態(tài)，需要有一個評價函數對其進行估值評價从诲。在此左痢，我選用沖突數作為評價指標，存在沖突數越多的狀態(tài)，其評價就越差俊性。顯然略步，最優(yōu)解的評價結果為0，即不存在沖突定页。
為了進一步優(yōu)化實驗運行效果趟薄，此函數我設置為內聯函數。
具體的實驗代碼如下：
/*評價函數：返回擺放狀態(tài)的沖突數*/
inline int evaluate(int* status, CollisionList& collision_list) {
collision_list.clear();
int num = 0;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
int offset = j - i;
if (abs(status[i] - status[j]) == offset) {
collision_list.push_back(j);
num += 1;
}
}
}
return num;
}
嘗試交換函數
對傳入的狀態(tài)進行交換嘗試典徊，如果交換后的狀態(tài)評價結果小于當前傳入狀態(tài)杭煎，就進行交換凌埂，將新狀態(tài)返回盖呼；否則，不交換寝姿，直接返回原先的狀態(tài)儡毕。
對于模擬退火算法也切，這里就需要加上一個temperature變量，當鄰居狀態(tài)不是更優(yōu)腰湾，但是溫度夠高,達到了振蕩指標時雷恃，也可以進行狀態(tài)轉換。同時费坊，temperature值是在不斷減小的倒槐。
尋找下一個更優(yōu)狀態(tài)的函數
對于傳入的狀態(tài)，不斷調用嘗試交換函數附井，直到獲得了沖突數更小的新狀態(tài)讨越，即為一個更優(yōu)狀態(tài)，將此狀態(tài)的沖突數作為返回值返回羡忘。
N皇后解法的主函數
這個函數的主要實現的就是調用初始化函數進行初始化谎痢，然后持續(xù)迭代調用尋找下一個更優(yōu)狀態(tài)函數磕昼，直到返回的沖突數指標為0時卷雕，可以將此狀態(tài)作為求得的一組可行解再交還給main函數。
算法效率比較
下面就是見證奇跡的時刻啦~~~
筆者特意寫了一份回溯法求解N皇后問題的程序票从，作為對比參照漫雕。
N=10時：
額，好像N設的有點小了峰鄙。浸间。。吟榴。來個大點的魁蒜。。。兜看。
N=20吧：
什么锥咸？回溯法？這细移。尷尬了搏予。。等了好久都沒跑出來結果弧轧。雪侥。。
退而求其次精绎，我跑了個N=16的回溯法給大家瞧瞧速缨，不過也是讓我足足等了5分多鐘：
可見當N>10以后，爬山算法的優(yōu)越性盡顯無疑代乃，我于是又給它上了幾個更大的數鸟廓，具體的運行效果如下：
爬山算法 N=1000的耗時也不過是回溯法 N=16情況運行耗時的一半！
AI的強大之處可以略窺一二了吧~
