人工智能課程報(bào)告--分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和A_算法求解“羅馬利亞度假問(wèn)題”

1、. 人工智能課程報(bào)告課 程: 人工智能實(shí)驗(yàn)報(bào)告 班 級(jí): 191121班 學(xué) 號(hào): 20121004362 學(xué)生姓名: 李 華 勇 指導(dǎo)教師: 趙 曼 2014年11月目錄一、羅馬利亞度假問(wèn)題31. 問(wèn)題描述32. 數(shù)據(jù)結(jié)構(gòu)42.1 廣度優(yōu)先算法42.2 深度優(yōu)先算法42.3 貪婪算法42.4 A*算法43. 算法思想53.1 廣度優(yōu)先搜索算法53.2 深度優(yōu)先搜索算法53.3 貪婪算法63.4 A*算法64. 運(yùn)行結(jié)果75. 比較討論86. 主要代碼8二、N皇后問(wèn)題131.問(wèn)題描述132.數(shù)據(jù)結(jié)構(gòu)132.1 回溯法（遞歸）132.2 GA算法132.3 CSP的最小沖突法133.算法思想14

2、3.1 回溯法（遞歸）143.2 CSP的最小沖突法143.3 GA算法154.運(yùn)行結(jié)果165.比較討論176.主要代碼18一、羅馬利亞度假問(wèn)題題目： 分別用寬度優(yōu)先、深度優(yōu)先、貪婪算法和A*算法求解“羅馬利亞度假問(wèn)題”。要求： 分別用文件存儲(chǔ)地圖和啟發(fā)函數(shù)表，用生成節(jié)點(diǎn)數(shù)比較幾種算法在問(wèn)題求解時(shí)的效率，并列表給出結(jié)果。1. 問(wèn)題描述 從文件中讀取圖和啟發(fā)函數(shù)，分別用廣度優(yōu)先、深度優(yōu)先、貪婪算法、A*算法得到從起始點(diǎn)Arad到目標(biāo)點(diǎn)Bucharest的一條路徑，即為羅馬尼亞問(wèn)題的一個(gè)解。在求解的過(guò)程中記錄生成擴(kuò)展節(jié)點(diǎn)的個(gè)數(shù)（用于比較幾種算法的優(yōu)劣），用堆棧記錄DepthFSearch和Broa

3、dFSearch的路徑。2. 數(shù)據(jù)結(jié)構(gòu) 分別使用了圖結(jié)構(gòu)，順序隊(duì)列，順序表以及堆棧。對(duì)于每一個(gè)圖中的結(jié)點(diǎn)，定義了一個(gè)結(jié)構(gòu)體HeuristicG，結(jié)構(gòu)體中包含結(jié)點(diǎn)的名稱(chēng)以及對(duì)應(yīng)的啟發(fā)函數(shù)值。 typedef struct char G20; int value; HeuristicG;typedef struct /圖結(jié)構(gòu)： typedef struct /鏈表 SeqList Vertices; string list20;int edge2020; int size;int numedge; SeqList;AdjMGraph;typedef struct /隊(duì)列 typedef struc

4、t /棧int queue20; int rear; int stack20;int front; int top;int count; SeqStack;SeqCQueue; 2.1 廣度優(yōu)先算法 使用了數(shù)據(jù)結(jié)構(gòu)中的圖、隊(duì)列和堆棧。 2.2 深度優(yōu)先算法 使用了數(shù)據(jù)結(jié)構(gòu)中的圖和堆棧。 2.3 貪婪算法 使用了數(shù)據(jù)結(jié)構(gòu)中的圖。 2.4 A*算法 使用了數(shù)據(jù)結(jié)構(gòu)中的圖。 3. 算法思想 3.1 廣度優(yōu)先搜索算法void BF_Search(AdjMGraph G, HeuristicG data, int v0,int vg, int *Expand, int * count, int visi

5、ted, int BFS_path) v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) count-返回路徑結(jié)點(diǎn)數(shù) BFS_path-存儲(chǔ)路徑信息 G、data-用來(lái)讀取圖的各種信息 visited-用來(lái)存儲(chǔ)節(jié)點(diǎn)是否已經(jīng)被訪(fǎng)問(wèn)的信息廣度優(yōu)先搜索是分層搜索的過(guò)程，廣度優(yōu)先搜索算法思想是用一個(gè)隊(duì)列來(lái)保存訪(fǎng)問(wèn)過(guò)的頂點(diǎn)的順序，以便按順序訪(fǎng)問(wèn)這些頂點(diǎn)的鄰接頂點(diǎn)，并把這些鄰接頂點(diǎn)依次入棧。在函數(shù)中我還創(chuàng)建了兩個(gè)棧，SeqStack SaveQ，LineSave，SaveQ將出隊(duì)列的節(jié)點(diǎn)全部進(jìn)棧，LineSave用于保存路徑。廣度優(yōu)先搜索算法如下：1） 訪(fǎng)問(wèn)頂點(diǎn)v0并標(biāo)記v0已被訪(fǎng)問(wèn)，把v0輸出

6、到屏幕。2） 頂點(diǎn)v0入隊(duì)列。3） 若隊(duì)列非空，則繼續(xù)執(zhí)行，否則算法結(jié)束。4） 出隊(duì)列取得隊(duì)頭頂點(diǎn)u，并把u入SaveQ棧。5） 查找頂點(diǎn)u的第一個(gè)鄰接頂點(diǎn)w。6） 如果w = vg，即找到目標(biāo)節(jié)點(diǎn)，算法結(jié)束。7） 若頂點(diǎn)u的鄰接頂點(diǎn)w不存在，則轉(zhuǎn)到步驟3），否則循環(huán)執(zhí)行： （a）若頂點(diǎn)w尚未被訪(fǎng)問(wèn)，則訪(fǎng)問(wèn)頂點(diǎn)w并標(biāo)記w為已訪(fǎng)問(wèn)； （b）頂點(diǎn)w入隊(duì)列，Expand+； （c）查找頂點(diǎn)u的w鄰接頂點(diǎn)后的下一個(gè)鄰接頂點(diǎn)w，轉(zhuǎn)到步驟7）。 廣度優(yōu)先搜索起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑的算法是：1） 把頂點(diǎn)vg以及vg的父節(jié)點(diǎn)u入棧。2） 把SaveQ棧頂元素出棧到u，當(dāng)SaveQ非空是執(zhí)行以下步驟： （a）

7、把SaveQ棧頂元素出棧到u 。 （b）取LineSave棧頂元素給y。 （c）如果u和y沒(méi)有相同的父親，沒(méi)被訪(fǎng)問(wèn)過(guò)，并且之間有邊則保存路 徑，把u壓入LineSave棧。 3.2 深度優(yōu)先搜索算法void DF_Search(AdjMGraph G, SeqStack * S, HeuristicG data, int * Expand ,int v0, int vg, int visited) v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) SeqStack * S-用堆棧存儲(chǔ)路徑信息 visited-存儲(chǔ)路徑是否被訪(fǎng)問(wèn)的信息 G、data-用來(lái)讀取圖的各種信息 深度優(yōu)先搜索

8、的算法思想是用棧來(lái)保存已經(jīng)訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)，遞歸找該節(jié)點(diǎn)的第一個(gè)鄰接頂點(diǎn)并把把頂點(diǎn)入棧，直到找不到頂點(diǎn)的鄰接頂點(diǎn)為止，然后回溯，找該頂點(diǎn)父頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)。 使用深度優(yōu)先搜索算法，每次都在訪(fǎng)問(wèn)完當(dāng)前頂點(diǎn)后首先訪(fǎng)問(wèn)當(dāng)前頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)。深度優(yōu)先搜索算法如下：1) 訪(fǎng)問(wèn)頂點(diǎn)v并標(biāo)記頂點(diǎn)v為以訪(fǎng)問(wèn)，把v0壓入棧S，并在屏幕上輸出v。2) 如果v0！= -1，查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w 3) 若頂點(diǎn)v的鄰接頂點(diǎn)w存在且為被訪(fǎng)問(wèn)，則繼續(xù)執(zhí)行，否則算法結(jié)束。4) 若果w = vg，即找到目標(biāo)節(jié)點(diǎn)，算法結(jié)束。5) 彈出S棧頂元素。6) 查找頂點(diǎn)v的w鄰接頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)w，轉(zhuǎn)到步驟3）。 3.3

9、貪婪算法void Greedy_Search(AdjMGraph G, HeuristicG data, int v0, int vg, int *Expand, int visited) v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) G、data-用來(lái)讀取圖的各種信息貪心算法思想是找到當(dāng)前頂點(diǎn)的所有鄰接頂點(diǎn)中h（x）值最小的鄰接頂點(diǎn)，并把該頂點(diǎn)設(shè)置為下一個(gè)起始節(jié)點(diǎn)，遞歸直到找到目標(biāo)節(jié)點(diǎn)。算法如下：1） 訪(fǎng)問(wèn)v0，并將v0設(shè)為以訪(fǎng)問(wèn)，把v0輸出到屏幕。2） 如果v0 = vg，即找到目標(biāo)節(jié)點(diǎn)，算法結(jié)束。3） 找到v0的所有鄰接頂點(diǎn)，并比較鄰接頂點(diǎn)的h（x）值，把h（x）最小 的

10、鄰接頂點(diǎn)w，把w設(shè)置為起始頂點(diǎn)v0，轉(zhuǎn)到步驟1）。 3.4 A*算法void A_Search(AdjMGraph G, HeuristicG data, int v0, int vg, int distance, int *Expand, int visited) v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) distance-用來(lái)保存已經(jīng)過(guò)路徑值 Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) G、data-用來(lái)讀取圖的各種信息 A*算法思想是找到起始節(jié)點(diǎn)v0的所有鄰接頂點(diǎn)，比較所有鄰接頂點(diǎn)的fx值（fx = 到v0已經(jīng)經(jīng)過(guò)路徑值+v0到鄰接頂點(diǎn)w的邊的路徑值distance+鄰接頂點(diǎn)w的hx值），找到fx最小的鄰接頂點(diǎn)

11、w作為下一個(gè)起始頂點(diǎn)v0，同時(shí)更新距離diatance = diatance + v0到w邊的路徑值，直到找到目標(biāo)節(jié)點(diǎn)。算法如下：1）訪(fǎng)問(wèn)v0，并將v0設(shè)為以訪(fǎng)問(wèn)，把v0輸出到屏幕。2）如果v0 = vg，即找到目標(biāo)節(jié)點(diǎn)，算法結(jié)束。3）找到v0的所有鄰接頂點(diǎn)w，并比較所有鄰接頂點(diǎn)的fx值， fx=ditance+v0到w的距離+w的啟發(fā)函數(shù)值，找到fx最小的鄰接頂點(diǎn)w 令v0 = w，更新distance = distance + edgev0w，轉(zhuǎn)到步驟1）。 4. 運(yùn)行結(jié)果深度優(yōu)先搜索寬度優(yōu)先搜索 A*算法 貪婪算法 擴(kuò)展節(jié)點(diǎn)數(shù)121154 路徑節(jié)點(diǎn)數(shù)54545. 比較討論從運(yùn)行結(jié)果中可以

12、看出，在搜索的過(guò)程中：DFS算法擴(kuò)展結(jié)點(diǎn)數(shù)為12BFS算法擴(kuò)展結(jié)點(diǎn)數(shù)為11A*算法擴(kuò)展結(jié)點(diǎn)數(shù)為5貪婪算法擴(kuò)展結(jié)點(diǎn)數(shù)為4所以在求解該問(wèn)題時(shí)，貪婪算法的效率最高，其次是A*算法，然后是BFS算法，最后是DFS算法。但是貪婪算法和A*算法生成的節(jié)點(diǎn)數(shù)依賴(lài)于啟發(fā)函數(shù)的值，因此雖然對(duì)于本題來(lái)說(shuō)貪婪算法和A*算法的效率很高，但是不能說(shuō)在所有搜索問(wèn)題中貪婪算法和A*算法的效率都是最高的。 6. 主要代碼1）深度優(yōu)先搜索 / v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) / Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) / SeqStack * S-用堆棧存儲(chǔ)路徑信息 / visited-存儲(chǔ)路徑訪(fǎng)問(wèn)信息 / G、data-用來(lái)讀取圖的各

13、種信 /void DF_Search(AdjMGraph G, SeqStack * S, HeuristicG data, int * Expand ,int v0, int vg, int visited) int t, w; /用于尋找目標(biāo)節(jié)點(diǎn) static int flag = 0;static int DFS_flag = 0; /標(biāo)志位-找到目標(biāo)節(jié)點(diǎn)后退出遞歸StackPush(S,v0); /首先將起始節(jié)點(diǎn)入棧 flag+;printf("%s-> ",datav0.G);visitedv0=1; if(v0 != -1) w=GetFirstVex(G

14、,v0,visited); /獲取第一個(gè)臨接點(diǎn) while(!DFS_flag && w != -1) if(w = vg)DFS_flag = 1;*Expand = flag;break;if(! visitedw && w != vg && DFS_flag = 0)DF_Search(G, S, data, Expand, w, vg, visited);if(DFS_flag) break; StackPop(S, &t); w = GetNextVex(G, v0, w, visited); 2）寬度優(yōu)先搜索 / v0-起始節(jié)

15、點(diǎn) vg-目標(biāo)節(jié)點(diǎn) / Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) / count-返回路徑結(jié)點(diǎn)數(shù) / BFS_path-存儲(chǔ)路徑信息 / G、data-用來(lái)讀取圖的各種信息 /void BF_Search(AdjMGraph G, HeuristicG data, int v0,int vg, int *Expand, int * count, int visited, int BFS_path)int u,w,y,SumExpand=1, i=0;SeqCQueue Q;SeqStack SaveQ,LineSave; /SaveQ將出隊(duì)列的節(jié)點(diǎn)全部進(jìn)棧,LineSave用于保存路徑StackIniti

16、ate(&SaveQ);StackInitiate(&LineSave);printf("%s-> ",datav0.G);visitedv0=1;QueueInitiate(&Q);QueueAppend(&Q,v0); /首先將起始節(jié)點(diǎn)入隊(duì)列 while(QueenNotEmpty(Q)QueueDelete(&Q,&u); StackPush(&SaveQ,u); /將每一個(gè)出隊(duì)列的結(jié)點(diǎn)進(jìn)行保存w = GetFirstVex(G, u, visited);if(w = vg)SumExpand+;*Expa

17、nd = SumExpand;break;while(w != -1)if( !visitedw) printf("%s-> ",dataw.G);visitedw = 1;QueueAppend(&Q,w);SumExpand+;w = GetNextVex(G, u, w, visited);StackPush(&LineSave,w);/此時(shí)w為目標(biāo)節(jié)點(diǎn)StackPush(&LineSave,u); /此時(shí)u為w的父節(jié)點(diǎn)StackPop(&SaveQ,&u);while(StackNotEmpty(SaveQ)StackP

18、op(&SaveQ,&u);StackTop(LineSave,&y);if ( Edge(G,u,y)=1 && visitedu=1)/如果沒(méi)有相同的父親,被訪(fǎng)問(wèn)過(guò)，并且之間有邊則保存路徑StackPush(&LineSave,u);while(StackNotEmpty(LineSave)StackPop(&LineSave,&u);BFS_pathi+=u; * count = i;3）A* 搜索 / v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) / distance-用來(lái)保存已經(jīng)過(guò)路徑值 / Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) / G、da

19、ta-用來(lái)讀取圖的各種信息 /void A_Search(AdjMGraph G, HeuristicG data, int v0, int vg, int distance, int *Expand, int visited)int i, u, temp=10000;static int path_num = 0;static int A_Search_flag = 0; /標(biāo)志位-找到目標(biāo)節(jié)點(diǎn)后退出遞歸static int fx = 0;if(v0 = 2) printf("%s",datav0.G); else printf("%s->",d

20、atav0.G);visitedv0 = 1;path_num+;if(v0 = vg) A_Search_flag = 1;*Expand = path_num;return;for(i=0;i<20;i+)if(Edge(G, v0, i) && visitedi = 0 && A_Search_flag = 0)fx = distance+datai.value+G.edgev0i;if(fx < temp)temp = fx;u = i;A_Search( G, data, u, vg, distance+G.edgev0u, Expand,

21、 visited); 4）貪心搜索 / v0-起始節(jié)點(diǎn) vg-目標(biāo)節(jié)點(diǎn) / Expand-返回?cái)U(kuò)展結(jié)點(diǎn)數(shù) / G、data-用來(lái)讀取圖的各種信息 /void Greedy_Search(AdjMGraph G, HeuristicG data, int v0, int vg, int *Expand, int visited)int i, u, temp = 1000;static int path_num = 0;static int G_Search_flag = 0; /標(biāo)志位-找到目標(biāo)節(jié)點(diǎn)后退出遞歸if(v0 = 2)printf("%s",datav0.G); e

22、lse printf("%s->",datav0.G);visitedv0 = 1;path_num+; if(v0 = vg) G_Search_flag = 1;*Expand = path_num;return;for(i=0;i<20;i+)if(Edge(G, v0, i) && visitedi = 0 && G_Search_flag = 0 && datai.value < temp)u = i; temp = datai.value;Greedy_Search( G, data, u, vg

23、, Expand, visited); 二、N皇后問(wèn)題題目： 分別用回溯法（遞歸）、GA算法和CSP的最小沖突法求解n皇后問(wèn)題。要求：. 輸入n，并用運(yùn)行時(shí)間比較幾種算法在相同規(guī)模的問(wèn)題時(shí)的求解效率，并列表給出結(jié)果。. 比較同一算法在n不相同時(shí)的運(yùn)行時(shí)間，分析算法的時(shí)間復(fù)雜性，并列表給出結(jié)果。1.問(wèn)題描述 在n*n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后(按照國(guó)際象棋的規(guī)則),即任意兩個(gè)皇后不能處在同一行或同一列或同一斜線(xiàn)上。分別用回溯法（遞歸）、GA算法、CSP的最小沖突法求解n皇后問(wèn)題。并比較不同n的情況下各個(gè)算法的算法耗時(shí)，以及相同n情況下三個(gè)算法的耗時(shí)的大小。2.數(shù)據(jù)結(jié)構(gòu) 2.1 回溯法（

24、遞歸） 使用了一維數(shù)組queenN = M，表示第 M 行 N 列有一個(gè)皇后。 2.2 GA算法 定義了一個(gè)種群結(jié)構(gòu)體： typedef struct int queenMAX_QUEENS ; int unitFitness; int eachFitnessMAX_QUEENS ; Population ; queen序列保存?zhèn)€體的 DNA 值，即每個(gè)皇后在棋盤(pán)上的位置。unitFitness 當(dāng)前個(gè)體的 適應(yīng)度eachFitness 個(gè)體中每個(gè) DNA 的適應(yīng)度Population m_population10 + MAX_QUEENS / 10 ; 定義種群 2.3 CSP的最小沖突法

25、typedef struct int queenMAX_QUEENS ; int unitConflicts ; int eachConflictMAX_QUEENS ; Mf_Queens ; queen序列保存每列皇后的位置unitConflict 當(dāng)前棋盤(pán)皇后的總沖突數(shù)eachConflict 每列棋盤(pán)皇后的總沖突數(shù)3.算法思想 3.1 回溯法（遞歸）回溯法的算法思想是從棋盤(pán)的第column = 0列開(kāi)始，對(duì)于棋盤(pán)每一列再?gòu)牡趓ow = 0行放置皇后，如果棋盤(pán)該位置與棋盤(pán)上已經(jīng)放置的其他皇后不沖突，則把皇后放置在該位置，進(jìn)行下一列皇后的放置；如果該列所有行的位置都不安全，則返回上一列。就

26、這樣直到將棋盤(pán)最后一列皇后成功放置為止。算法步驟如下：1） 從函數(shù)中傳入第column列，如果column = 皇后數(shù)，則算法結(jié)束。2） 從column列第row = 0行開(kāi)始循環(huán)，把row值賦給queencolumn。如果該點(diǎn)安全，則column +，轉(zhuǎn)到1），否則row+，繼續(xù)執(zhí)行循環(huán)。 3.2 CSP的最小沖突法 CSP的最小沖突法的算法思想是從棋盤(pán)的第column = 0列開(kāi)始，找到棋盤(pán)該列在所有行位置上放置皇后與棋盤(pán)其他皇后的沖突數(shù)，選擇沖突數(shù)最小的那一行放置皇后，如果有幾行沖突數(shù)一樣，則隨機(jī)選取一行；直到找到棋盤(pán)所有列上皇后的位置，如果此時(shí)整個(gè)棋盤(pán)的沖突度為零，即每個(gè)皇后之間都不沖

27、突，即找到了一個(gè)解，算法結(jié)束；否則繼續(xù)從第一列開(kāi)始循環(huán)。算法步驟如下： 1）從i = 0列開(kāi)始循環(huán) 2）從j = 0行開(kāi)始循環(huán)，把j賦給queeni，如果此時(shí)第i列的沖突度最小，則更新棋盤(pán)。 3）j+，如果j小于皇后數(shù)，則轉(zhuǎn)到步驟2）；否則i+，如果i小于皇后數(shù),則轉(zhuǎn)到步驟1）；否則計(jì)算該棋盤(pán)的沖突數(shù)是否為零，如果為零則算法結(jié)束，否則令i = 0，轉(zhuǎn)到步驟1）。 沖突度算法是計(jì)算每列皇后與其他列皇后是否在同一行或在對(duì)角線(xiàn)上，如果是則沖突數(shù)加1，整個(gè)棋盤(pán)的沖突數(shù)是每一列皇后沖突數(shù)之和除以2。 3.3 GA算法GA算法思想是初始化一個(gè)種群，種群中有size = 30 + 皇后數(shù)n/ 10個(gè)個(gè)體，每

28、個(gè)個(gè)體對(duì)應(yīng)一種皇后在棋盤(pán)上的分布狀態(tài)，每個(gè)個(gè)體都有自己的適應(yīng)度，適應(yīng)度越高越接近N皇后的解。利用qsort排序函數(shù)按適應(yīng)度大小給種群排序。利用輪盤(pán)賭局規(guī)則從種群中選擇雙親進(jìn)行雜交（即被選到的概率與適應(yīng)度成正比），雜交得到size-2個(gè)子代，再加上父代中適應(yīng)度最高的兩個(gè)個(gè)體組成新的種群。對(duì)新種群利用qsort排序函數(shù)按適應(yīng)度大小給種群排序，并對(duì)適應(yīng)度最高的兩個(gè)個(gè)體進(jìn)行局部變異，如果這兩個(gè)個(gè)體中有達(dá)到適應(yīng)度n×（n-1）的，即找到了一個(gè)解，則算法結(jié)束，否則繼續(xù)進(jìn)行種群的繁衍。個(gè)體適應(yīng)的的計(jì)算：判斷每列皇后與其他列皇后是否在同一行或在對(duì)角線(xiàn)上，如果不是則適應(yīng)度加1，所有列皇后適應(yīng)度之和即為

29、個(gè)體的適應(yīng)度。如果該個(gè)體是一個(gè)解，則每一列皇后與其他列皇后都不沖突，即每一個(gè)皇后的適應(yīng)度都為n-1，所以該個(gè)體的適應(yīng)度為n×（n-1）。GA算法步驟如下：1） 初始換種群。2） 當(dāng)種群中適應(yīng)度最高的兩個(gè)個(gè)體中沒(méi)有符合目標(biāo)適應(yīng)度的，執(zhí)行以下循環(huán)： （a）雜交 （b）把種群中的個(gè)體按適應(yīng)度大小排序 （c）把適應(yīng)度最高的兩個(gè)個(gè)體做局部變異并且更新他們的適應(yīng)度 4. 運(yùn)行結(jié)果當(dāng)皇后數(shù)為8時(shí)： 當(dāng)皇后數(shù)為20時(shí)（因?yàn)榻绱笮≡驔](méi)有選擇打印解）： 當(dāng)皇后數(shù)為30時(shí)（因?yàn)榻绱笮≡驔](méi)有選擇打印解）：此時(shí)回溯法的運(yùn)行時(shí)間超過(guò)20s，沒(méi)有繼續(xù)向下運(yùn)行?；屎髷?shù)回溯法(s)CSP最小沖突法(s)GA算法(

30、s)40.0000.0000.00080.0000.0020.034200.2400.0321.22030-0.0452.52340-0.0722.87950-0.1023.14360-0.2055.07970-0.16113.77480-0.40832.20590-0.47162.892100-0.821-200-7.699-5.比較討論從運(yùn)行結(jié)果中可以看出，當(dāng)皇后數(shù)N小于30的時(shí)候回溯法和CSP的最小沖突法以及GA算法運(yùn)行都很快。但是當(dāng)N>30時(shí)，回溯法已經(jīng)很難找到解，運(yùn)行時(shí)超過(guò)了20s。當(dāng)N>50時(shí)，GA算法運(yùn)行時(shí)間開(kāi)始逐漸變長(zhǎng)，當(dāng)N>90時(shí)運(yùn)行時(shí)間已經(jīng)超過(guò)了60s。當(dāng)

31、N=200時(shí)，CSP的最小沖突法時(shí)間才僅為7.699s。對(duì)比可知當(dāng)N較大時(shí)，CSP的最小沖突法的效率最高，GA算法次之，回溯法在求解大的皇后數(shù)是效率最低。對(duì)于回溯法的時(shí)間復(fù)雜度，最好情況是O(n2)，最壞情況是O(n!)。對(duì)于CSP的最小沖突法的時(shí)間復(fù)雜度，最好的情況是O(n3)，最壞的情況是O（m*n3）。對(duì)于GA算法的時(shí)間復(fù)雜度，最好情況是O(n3)，最壞的情況是O（p*n3）。 6.主要代碼1、回溯法：void backtrack(int column) /以列作為判斷點(diǎn) int row,i,j;double secs, ms;BK_stop =clock();ms = (double)

32、(BK_stop - BK_start);if(ms>20000) /回溯法運(yùn)行超過(guò)20s就退出printf("BackT_Queen Calculations took more than 20 seconds !n");exit(0); if ( column=BK_Q_num) BK_end = clock () ;secs = (double)(BK_end - BK_start) / CLOCKS_PER_SEC ; printf("Back_Queen Calculations took %.3lf second%s.n", secs,

33、 (secs < 1 ? "" : "s");exit(0); else/放置第column列上的皇后，從第一行開(kāi)始試探放置 for (row=0;row<BK_Q_num;row+)Queencolumn = row;if ( isSafe(Queen,column)backtrack(column+1); /該點(diǎn)安全，向第column列遞歸2、 CSP的最小沖突法：void Min_Conflict_Queens () int i, j,Min;Mf_Queens temp; /從第一列開(kāi)始尋找該列沖突數(shù)最小的皇后所在行，循環(huán)執(zhí)行每一列f

34、or(i=0;i<CSP_Q_num;i+) temp = Min_conflictsQ; UpdateConflictNum(&temp) ; /更新該行皇后在每一列形成的新的棋面的總沖突數(shù) Min = RAND_MAX; for(j=0;j<CSP_Q_num;j+) temp.queeni = j; UpdateColumn (&temp, i) ; /更新棋盤(pán)第i列皇后放在j行的沖突度 if(temp.eachConflicti < Min) /把沖突數(shù)小的棋盤(pán)賦給 Min_conflictsQ Min = temp.eachConflicti; Mi

35、n_conflictsQ = temp; if(temp.eachConflicti = Min) /如果沖突數(shù)相等，則隨機(jī)更新棋盤(pán) Min_conflictsQ = rand() % 2 ? Min_conflictsQ : temp; 3、 GA算法：/ 雙親遺傳中的變異算子/ 對(duì)種群中的最優(yōu)兩個(gè)個(gè)體保留，并局部變異看是否可以達(dá)到結(jié)果 void MultiMutate (Population* p)int i, j, swap ;int worst ;Population baby ;worst = 0 ;for (i = 0 ; i < GA_Q_num ; i+)if (p-&g

36、t;eachFitnessi < p->eachFitnessworst)worst = i ;if(p->eachFitnessworst = GA_Q_num-1) return;baby = *p ;for (i = 0 ; i < GA_Q_num / 4 ; i+)j = rand() % GA_Q_num ;swap = baby.queenworst ;baby.queenworst = baby.queenj ;baby.queenj = swap ;UpdateFitnessScore(&baby) ;if (baby.unitFitness

37、> p->unitFitness | (double)rand() / RAND_MAX < M_Critical)*p = baby ;break ;/ 采取輪盤(pán)賭局規(guī)則進(jìn)行雙親的選擇/ 即被選到的概率與適應(yīng)度呈正比 （越是優(yōu)越的個(gè)體基因越容易被保留下來(lái)）int RouletteWheelSelection()int selection = 0;int i ;double slice = (double)rand() / RAND_MAX;double addFitness = 0;for(i = 0; i < m_size ; i+)addFitness += (double)m_populationi.unitFitness / m_to