人工智能-N皇后問(wèn)題回溯法爬山算法的實(shí)現(xiàn)及性能分析

1、N皇后問(wèn)題爬山法和回溯法的實(shí)現(xiàn)及性能分析 云南大學(xué)信息學(xué)院 專業(yè)：計(jì)算機(jī)軟件與理論目錄 TOC o 1-3 h z u HYPERLINK l _Toc358850097 HYPERLINK l _Toc358850098 一、N皇后問(wèn)題 PAGEREF _Toc358850098 h 4 HYPERLINK l _Toc358850099 1.問(wèn)題描述 PAGEREF _Toc358850099 h 4 HYPERLINK l _Toc358850100 2. 數(shù)據(jù)結(jié)構(gòu) PAGEREF _Toc358850100 h 4 HYPERLINK l _Toc358850101 二、爬山算法 PA

2、GEREF _Toc358850101 h 4 HYPERLINK l _Toc358850102 1. 爬山算法一般介紹 PAGEREF _Toc358850102 h 4 HYPERLINK l _Toc358850103 2. 爬山算法的偽代碼 PAGEREF _Toc358850103 h 5 HYPERLINK l _Toc358850104 3. 算法評(píng)價(jià) PAGEREF _Toc358850104 h 5 HYPERLINK l _Toc358850105 三、回溯法 PAGEREF _Toc358850105 h 5 HYPERLINK l _Toc358850106 1. 回

3、溯法一般介紹 PAGEREF _Toc358850106 h 5 HYPERLINK l _Toc358850107 2. 回溯法的偽代碼 PAGEREF _Toc358850107 h 5 HYPERLINK l _Toc358850108 3. 算法評(píng)價(jià) PAGEREF _Toc358850108 h 6 HYPERLINK l _Toc358850109 四、算法實(shí)現(xiàn)及性能比擬 PAGEREF _Toc358850109 h 6 HYPERLINK l _Toc358850110 五、兩種算法性能分析 PAGEREF _Toc358850110 h 7 HYPERLINK l _Toc3

4、58850111 六、結(jié)論 PAGEREF _Toc358850111 h 8 HYPERLINK l _Toc358850112 七、參考文獻(xiàn) PAGEREF _Toc358850112 h 8 HYPERLINK l _Toc358850113 附錄 PAGEREF _Toc358850113 h 9一、N皇后問(wèn)題1n皇后問(wèn)題：在n*n格的國(guó)際象棋上擺放n個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上， 2分別用回溯法遞歸、爬山法和GA算法求解n皇后問(wèn)題。要求：輸入n，并用運(yùn)行時(shí)間比擬幾種算法在相同規(guī)模的問(wèn)題時(shí)的求解效率。列表給出結(jié)果。2. 數(shù)據(jù)結(jié)構(gòu)1、邏輯結(jié)

5、構(gòu)：用到線性結(jié)構(gòu)包括數(shù)組等。2、存儲(chǔ)結(jié)構(gòu)物理結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)。二、爬山算法1. 爬山算法一般介紹爬山法是指從當(dāng)前的節(jié)點(diǎn)開始，和周圍的鄰居節(jié)點(diǎn)的值進(jìn)行比擬。 如果當(dāng)前節(jié)點(diǎn)是最大的，那么返回當(dāng)前節(jié)點(diǎn)，作為最大值(既山峰最高點(diǎn))；反之就用最高的鄰居節(jié)點(diǎn)來(lái)，替換當(dāng)前節(jié)點(diǎn)，從而實(shí)現(xiàn)向山峰的高處攀爬的目的。如此循環(huán)直到到達(dá)最高點(diǎn)。每次都選擇是與目標(biāo)結(jié)點(diǎn)啟發(fā)函數(shù)值最小的那個(gè)結(jié)點(diǎn)，經(jīng)過(guò)迂回前進(jìn),最終到達(dá)解決問(wèn)題的總目標(biāo)。如果我們把目標(biāo)函數(shù)的幾何圖形看成一個(gè)山峰,那么點(diǎn)的直接移動(dòng)就像人在爬山,選擇方向,逐步向山頂移動(dòng)。爬山法需要建立一個(gè)描述數(shù)據(jù)庫(kù)變化的單極值函數(shù)，且使極值對(duì)應(yīng)目標(biāo)狀態(tài)；選取使函數(shù)值增長(zhǎng)最大的那

6、條規(guī)那么作用于數(shù)據(jù)庫(kù)；重復(fù)上步，直到?jīng)]有規(guī)那么使函數(shù)值繼續(xù)增長(zhǎng)。爬山法是一種局部搜索算法，也屬一種啟發(fā)式方法。但它一般只能得到局部最優(yōu)，并且這種解還依賴于起始點(diǎn)的選取。它是一種解多變量無(wú)約束最優(yōu)化問(wèn)題的一類方法，通過(guò)點(diǎn)的直接移動(dòng)產(chǎn)生的目標(biāo)值有所改善的點(diǎn),經(jīng)過(guò)這樣的移動(dòng),逐步到達(dá)使目標(biāo)函數(shù)最優(yōu)的點(diǎn)。在爬山法中，h表示相互攻擊的皇后的對(duì)數(shù)，用它來(lái)生成啟發(fā)函數(shù)。2. 爬山算法的偽代碼爬山函數(shù)問(wèn)題是局部極大值的一種狀態(tài)返回輸入問(wèn)題，一個(gè)問(wèn)題局部變量：當(dāng)前，一個(gè)節(jié)點(diǎn)。鄰居，一個(gè)節(jié)點(diǎn)。當(dāng)前生成節(jié)點(diǎn)初始狀態(tài)問(wèn)題循環(huán)做鄰居一個(gè)價(jià)值最高當(dāng)前的繼任者如果值鄰居價(jià)值當(dāng)前，然后返回狀態(tài)當(dāng)前當(dāng)前鄰居3. 算法評(píng)價(jià)爬山法

7、的缺點(diǎn)：會(huì)出現(xiàn)山脊、高原，86%的時(shí)間會(huì)卡?。坏桥郎剿惴ㄝ^簡(jiǎn)單，在皇后的個(gè)數(shù)較多時(shí)表達(dá)出來(lái)效率最高，處理多約束大規(guī)模問(wèn)題時(shí)往往不能得到較好的解。三、回溯法1. 回溯法一般介紹回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以到達(dá)目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法。2. 回溯法的偽代碼回溯法根本思想是：從一條路往前走，能進(jìn)那么進(jìn)，不能進(jìn)那么退回來(lái)，換一條路再試。對(duì)于n皇后問(wèn)題，第一步按照順序放一個(gè)皇后，然后第二步符合要求放第2個(gè)皇后，如果沒(méi)有符合位置符合要求，那么就要改變第一個(gè)皇后的位置，重新放第2個(gè)皇后的位置，直到找到

8、符合條件的位置就可以了，在目標(biāo)狀態(tài)終止。3. 算法評(píng)價(jià)回溯法在皇后數(shù)目較小的，很占優(yōu)勢(shì)，它的速度非常的快，但隨著皇后數(shù)目的增加，回溯法顯得很不實(shí)用，在n=28時(shí)，用回溯法已不能較好的解決n皇后問(wèn)題。四、算法實(shí)現(xiàn)及性能比擬這里通過(guò)c+語(yǔ)言來(lái)實(shí)現(xiàn)各種排序算法源碼見附錄，程序運(yùn)行環(huán)境為windows 7，所用編譯器為vs2021。實(shí)驗(yàn)分別以不同的皇后規(guī)模用例進(jìn)行測(cè)試?；屎笠?guī)模設(shè)置為10,50,100,150,200,250實(shí)驗(yàn)局部結(jié)果如圖4-1：圖4-1.局部測(cè)試結(jié)果五、兩種算法性能分析在測(cè)試中我們根據(jù)不同的皇后規(guī)模用例進(jìn)行測(cè)試，并給出了各個(gè)規(guī)模的不同算法所用的運(yùn)行時(shí)間單位ms。表1為不同的皇后規(guī)模

9、測(cè)試后得到的運(yùn)行時(shí)間數(shù)據(jù)。 規(guī)模時(shí)間1050100150200250爬山法(ms)回溯法(ms)表1 不同的皇后規(guī)模運(yùn)行時(shí)間單位ms為了直觀起見，根據(jù)實(shí)驗(yàn)數(shù)據(jù)畫出不同的皇后規(guī)模以及不同算法的時(shí)間變化趨勢(shì)圖如圖5-1所示： 圖5-1兩種算法用時(shí)變化趨勢(shì)圖六、結(jié)論爬山法是一種始終都比擬快的算法，它的運(yùn)行時(shí)間與皇后是個(gè)數(shù)沒(méi)有必然的聯(lián)系，而且在n很大時(shí)，它顯現(xiàn)出來(lái)運(yùn)行時(shí)間短，效率高的優(yōu)勢(shì)，但它的缺點(diǎn)是會(huì)出現(xiàn)山脊、高原，86%的時(shí)間會(huì)卡住?？偟膩?lái)說(shuō)，爬山算法較簡(jiǎn)單，也比擬快，在皇后的個(gè)數(shù)較多時(shí)表達(dá)出來(lái)效率最高，處理多約束大規(guī)模問(wèn)題時(shí)往往不能得到較好的解?；厮莘ㄔ诨屎髷?shù)目較小的，很占優(yōu)勢(shì)，它的速度非常的快

10、，但隨著皇后數(shù)目的增加，回溯法顯得很不實(shí)用，在n=50時(shí)，用回溯法已不能較好的解決n皇后問(wèn)題。總的來(lái)說(shuō)，回溯在n值很小時(shí)，效率最高，在n值很大時(shí)，回溯法不能再解決，此時(shí)，爬山法的效率最高，且與n值沒(méi)有必然的聯(lián)系。七、參考文獻(xiàn)1?Artificial intelligence :;a modern approach 人工智能 : 一種現(xiàn)代方法? Russell, Stuart J. 出版社：清華大學(xué)出版社附錄/*/* 爬山法解決N皇后問(wèn)題 */*/#include #include #include #include #include #include #includeusing namespa

11、ce std;typedef vector CollisionList_t;void print_row_mark(int N)if (N15)return;for (int i=0; iN; +i) cout +;cout + 5)return;/cout |;for (int i=0; iN; +i) /*if(i=fill)cout X ;elsecout 0 ;*/cout | (i=fill) ? X : ) ;cout | endl;print_row_mark(N); /皇后位置的表示方法: /使用數(shù)組chessmanN來(lái)表示N個(gè)皇后的位置 /第i個(gè)皇后chessmani的下標(biāo)i

12、表示其行所在的位置， /chessmanj表示其列的位置。 /一個(gè)四皇后問(wèn)題的表示方法如下所示： /(0, 1) (1, 3) (2, 0) (3, 2) /+ /| | X | | | /+ /| | | | X | /+ /| X | | | | /+ /| | | X | | /+ /void print_chessboard(int* chessman, int N)for (int i=0; iN; +i) if(i%5=0)coutn;cout ( i , chessmani ) ;cout endl;print_row_mark(N);for (int j=0; jN; +j)

13、print_row(N, chessmanj);/ 隨機(jī)生成一個(gè)初始化狀態(tài)，在每行每列上放置一個(gè)皇后void generate_init_state(int* chessman, int N)for (int i=0; iN; +i) chessmani = i;for (int j=0; jN; +j) int r = rand();r = r % N;swap(chessmanr, chessmanN-r-1);/ 返回沖突的皇后個(gè)數(shù)int h(int* chessman, int N, CollisionList_t& collision_list)collision_list.clea

14、r();int collision = 0;for (int i=0; iN; +i) for (int row=i+1; row cl.size() / 取消之前的交換swap(chessmanrow1, chessmanrow2);else cl = new_cl;return new_cl.size();int choose_next_state(int* chessman, int N, CollisionList_t& cl)int old_collision = cl.size();int new_collision;int row1 = -1;int row2 = -1;/ 優(yōu)化

15、最后只有一個(gè)沖突的解if (cl.size() = 1) for (int i=0; i old_collision);return new_collision;/ 使用隨機(jī)爬山法尋找一個(gè)N皇后問(wèn)題的解int queen_solution(int N)int* chessman = new intN;int max_tries = N*N;int max_steps = N*N;int tries = 0;while (tries max_tries) +tries;int steps = 0;int collision=0;CollisionList_t collision_list;sra

16、nd(time(NULL) + tries * collision);generate_init_state(chessman, N);collision = h(chessman, N, collision_list);while (collision != 0) & (stepsmax_steps) collision = choose_next_state(chessman, N, collision_list);+steps;if (collision = 0) cout 測(cè)試后找到一個(gè)方案: endl;print_chessboard(chessman, N);return 1;return 0;/ 接受一個(gè)整數(shù)N，表示要尋找的解是N皇后問(wèn)題。int main()coutendl;int N=8;/ 缺省為尋找8皇后問(wèn)題的一個(gè)解for(;)if(N=0)break;coutendl;cout輸入N的值：N;if (N = 0) cout 輸入錯(cuò)誤，請(qǐng)輸入正整數(shù)！ endl;return 1;srand(time(NULL);LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/獲取時(shí)