這兩天在寫AI的課程實(shí)驗(yàn)，趁剛剛完結(jié)實(shí)驗(yàn)代碼，腦海中還有些思路，在此簡(jiǎn)單總結(jié)一下。
目錄
問題描述
2N皇后問題：給定一個(gè)n*n的棋盤?，F(xiàn)要向棋盤中放入n個(gè)黑皇后和n個(gè)白皇后，使任意的兩個(gè)黑皇后都不在同一行、同一列或同一條對(duì)角線上，任意的兩個(gè)白皇后都不在同一行、同一列或同一條對(duì)角線上。請(qǐng)盡量快地給出一組可行解。
關(guān)于N皇后問題
N皇后問題是一個(gè)很經(jīng)典的問題，在大家最初學(xué)習(xí)算法的時(shí)候都有討論過?；厮莘ㄊ墙?jīng)典的解法，但是隨著N的增大，其復(fù)雜度的增加呈指數(shù)增長(zhǎng)。哪怕N只是為100，使用回溯解法的話，運(yùn)行也要相當(dāng)久的時(shí)間。
簡(jiǎn)單分析
對(duì)于2N皇后問題，很多同學(xué)的第一想法可能是兩次求解N皇后問題，且第二次求解時(shí)為擺放位置設(shè)限。然而，這種做法不免顯得過于繁瑣。
我們?cè)谶@里，不妨先簡(jiǎn)單地分析了一下幾種情況：
1. 當(dāng)N為偶數(shù)時(shí)：其實(shí)只要求得一組可行解即可，另外一組可行解可以由當(dāng)前解沿N*N矩陣的中軸線作對(duì)稱變換得到。因?yàn)镹為偶數(shù)，所以不會(huì)存在黑白皇后位置沖突的情況。
例如：N=4時(shí)，求得一組可行解為：3 1 4 2，按著這個(gè)思路，變換得到另一組可行解為：2 4 1 3。可以判斷，這樣的兩組解合并起來是符合題目要求的。
2. 當(dāng)N為奇數(shù)時(shí)：沿中軸線對(duì)稱的方式不再可行，因?yàn)榭隙ㄓ幸粋€(gè)皇后會(huì)落在中軸線上。此時(shí)，可以考慮通過中心點(diǎn)作點(diǎn)對(duì)稱的情況。
這里要注意，如果求得的可行解存在關(guān)于中心點(diǎn)對(duì)稱的皇后擺放(或有皇后位于中心點(diǎn))，那么此解不合要求，需要重新再求；直到?jīng)]有兩個(gè)皇后的位置是關(guān)于中心點(diǎn)對(duì)稱的，另一組解可以通過對(duì)當(dāng)前解關(guān)于中心點(diǎn)作點(diǎn)對(duì)稱變換得到。
例如，N=5時(shí)，求得一組可行解為：2 4 1 3 5，按著這個(gè)思路，變換得到另一組可行解為：1 3 5 2 4?？梢耘袛啵@樣的兩組解合并起來是符合題目要求的。
從上可以看出，其實(shí)2N皇后問題并不需要二次求解N皇后，在大多數(shù)情況下只需求得一組可行解即可。
爬山算法
在介紹爬山算法之前，我覺得很有必要先弄清楚什么是局部搜索。
局部搜索
從數(shù)學(xué)層面來理解，局部搜索是一種解決最優(yōu)化問題的啟發(fā)式算法。
對(duì)于某些計(jì)算起來非常復(fù)雜的最優(yōu)化問題，比如各種 NP 完全問題，要找到最優(yōu)解所需要的時(shí)間會(huì)隨問題規(guī)模的增大呈指數(shù)增長(zhǎng)，因此誕生了各種啟發(fā)式算法來退而求次地尋找局部最優(yōu)解，而局部搜索算法就是其中的一種算法。
局部搜索算法從某一狀態(tài)(而不是多條路徑)出發(fā)，通常只移動(dòng)到與當(dāng)前狀態(tài)相鄰的狀態(tài)。而在典型情況下，搜索的路徑是不保留的。盡管局部搜索算法不是系統(tǒng)化的求解方法，但是它有幾個(gè)關(guān)鍵的優(yōu)點(diǎn)：
1. 占用很少的內(nèi)存，通常情況下容量是常數(shù)級(jí)別的。
2. 經(jīng)常能在不適合系統(tǒng)化算法的很大或者無限的（連續(xù)的）狀態(tài)空間中快速找出合理的解。
爬山算法簡(jiǎn)介
爬山算法屬于局部搜索算法的一份子，因此是一種解決最優(yōu)化問題的啟發(fā)式算法。
在實(shí)際運(yùn)用中，爬山算法不會(huì)前瞻與當(dāng)前狀態(tài)不直接相鄰的狀態(tài)，只會(huì)選擇比當(dāng)前狀態(tài)價(jià)值更好的相鄰狀態(tài)，所以簡(jiǎn)單來說，爬山算法是向價(jià)值增長(zhǎng)方向持續(xù)移動(dòng)的循環(huán)過程。
由于它的貪婪特性，使得在解決問題中容易陷入局部極大值(Local maxima，指一個(gè)比所有鄰居狀態(tài)價(jià)值要高但是比全局最大值要低的狀態(tài))，我們能采取隨機(jī)重啟(Random restart)以及模擬退火(Simulated annealing)的方法來改進(jìn)。本文的主要涉及的就是這兩種算法。
先在這里簡(jiǎn)單地說一下它們之間的區(qū)別，主要在于如何選擇下一狀態(tài)以及如何有效地得到全局最優(yōu)解：
1. 隨機(jī)重啟爬山算法：
求解過程中，當(dāng)?shù)玫搅司植繕O大值時(shí)，如果不是全局最優(yōu)解，則隨機(jī)生成初始狀態(tài)，重新求解，直到得到全局最優(yōu)解。
2. 模擬退火爬山算法：
基于隨機(jī)爬山算法，允許在隨機(jī)選擇相鄰狀態(tài)的時(shí)候有概率地選擇價(jià)值更小的狀態(tài)。在初期，向低價(jià)值狀態(tài)移動(dòng)的概率高，隨著時(shí)間流逝該概率會(huì)越來越低。(溫度逐漸降低，即"退火"。)
算法實(shí)現(xiàn)與關(guān)鍵優(yōu)化
初始化
不同于一般的隨機(jī)初始化。我實(shí)現(xiàn)時(shí)采用的初始化方式為：先依次為每一行的對(duì)應(yīng)列擺上皇后，如第i 行，那么皇后就擺在第i 列，之后再隨機(jī)選擇交換皇后所在列。
這樣做的優(yōu)點(diǎn)是可以保證在任一時(shí)刻，每一行每一列都只有一個(gè)皇后，大大縮小了搜索范圍，節(jié)省了程序運(yùn)行時(shí)間。(從我的程序運(yùn)行耗時(shí)可以明顯看出這一策略的優(yōu)越性。)
具體的實(shí)驗(yàn)代碼如下：
/*初始化函數(shù)：在每行每列放置一個(gè)皇后*/
void generate_status(int* status) {
for (int i = 0; i < N; i++) {
status[i] = i;
}
/*隨機(jī)交換*/
srand((unsigned)time(NULL));
for (int i = 0; i < N; i++) {
int r = rand();
r = r % N;
swap(status[r], status[N - r - 1]);
}
}
評(píng)價(jià)函數(shù)
對(duì)于每一個(gè)狀態(tài)，需要有一個(gè)評(píng)價(jià)函數(shù)對(duì)其進(jìn)行估值評(píng)價(jià)。在此，我選用沖突數(shù)作為評(píng)價(jià)指標(biāo)，存在沖突數(shù)越多的狀態(tài)，其評(píng)價(jià)就越差。顯然，最優(yōu)解的評(píng)價(jià)結(jié)果為0，即不存在沖突。
為了進(jìn)一步優(yōu)化實(shí)驗(yàn)運(yùn)行效果，此函數(shù)我設(shè)置為內(nèi)聯(lián)函數(shù)。
具體的實(shí)驗(yàn)代碼如下：
/*評(píng)價(jià)函數(shù)：返回?cái)[放狀態(tài)的沖突數(shù)*/
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;
}
嘗試交換函數(shù)
對(duì)傳入的狀態(tài)進(jìn)行交換嘗試，如果交換后的狀態(tài)評(píng)價(jià)結(jié)果小于當(dāng)前傳入狀態(tài)，就進(jìn)行交換，將新狀態(tài)返回；否則，不交換，直接返回原先的狀態(tài)。
對(duì)于模擬退火算法，這里就需要加上一個(gè)temperature變量，當(dāng)鄰居狀態(tài)不是更優(yōu)，但是溫度夠高,達(dá)到了振蕩指標(biāo)時(shí)，也可以進(jìn)行狀態(tài)轉(zhuǎn)換。同時(shí)，temperature值是在不斷減小的。
尋找下一個(gè)更優(yōu)狀態(tài)的函數(shù)
對(duì)于傳入的狀態(tài)，不斷調(diào)用嘗試交換函數(shù)，直到獲得了沖突數(shù)更小的新狀態(tài)，即為一個(gè)更優(yōu)狀態(tài)，將此狀態(tài)的沖突數(shù)作為返回值返回。
N皇后解法的主函數(shù)
這個(gè)函數(shù)的主要實(shí)現(xiàn)的就是調(diào)用初始化函數(shù)進(jìn)行初始化，然后持續(xù)迭代調(diào)用尋找下一個(gè)更優(yōu)狀態(tài)函數(shù)，直到返回的沖突數(shù)指標(biāo)為0時(shí)，可以將此狀態(tài)作為求得的一組可行解再交還給main函數(shù)。
算法效率比較
下面就是見證奇跡的時(shí)刻啦~~~
筆者特意寫了一份回溯法求解N皇后問題的程序，作為對(duì)比參照。
N=10時(shí)：
額，好像N設(shè)的有點(diǎn)小了。。。。來個(gè)大點(diǎn)的。。。。
N=20吧：
什么？回溯法？這。尷尬了。。等了好久都沒跑出來結(jié)果。。。
退而求其次，我跑了個(gè)N=16的回溯法給大家瞧瞧，不過也是讓我足足等了5分多鐘：
可見當(dāng)N>10以后，爬山算法的優(yōu)越性盡顯無疑，我于是又給它上了幾個(gè)更大的數(shù)，具體的運(yùn)行效果如下：
爬山算法 N=1000的耗時(shí)也不過是回溯法 N=16情況運(yùn)行耗時(shí)的一半！
AI的強(qiáng)大之處可以略窺一二了吧~
