【正文】 m_population[count+2] = p[count] 。 // 雜交 ,后代保存 } // 將結果覆蓋回原種群，加上原種群中適應度最高的兩個個體組成新的進化后的種群 for (count = 0 。 count++) { father = RouletteWheelSelection () 。 i m_size 。 Population p[30 + MAX_QUEENS / 10] 。 } else babyqueen[i] = [i] 。 i GA_Q_num 。 for (j = pos1。 pos2 = tmp。 pos2 = rand() % GA_Q_num 。 } // 雜交 father , mother， 產生的子代保存在 baby 中 void CrossOverFM (Population father, Population mother, Population *baby) { 人工智能課程報告 21 int flag[MAX_QUEENS] 。 i++) { addFitness += (double)m_population[i].unitFitness / m_totFitness 。 double slice = (double)rand() / RAND_MAX。 if ( punitFitness || (double)rand() / RAND_MAX M_Critical) { *p = baby 。 [worst] = [j] 。 for (i = 0 。 i GA_Q_num 。 int worst 。 //更新棋盤第 i 列皇后放在 j 行的沖突度 if([i] Min) //把沖突數(shù)小的棋盤賦給 Min_conflictsQ { Min = [i]。jCSP_Q_num。 UpdateConflictNum(amp。 Mf_Queens temp。rowBK_Q_num。 secs = (double)(BK_end BK_start) / CLOCKS_PER_SEC 。 ms = (double)(BK_stop BK_start)。 對于 GA 算法的時間復雜度，最好情況是 O(n^3)，最壞的情況是 O（ p*n^3）。 當 N=200 時， CSP 的最小沖突法時間才僅為 。 2） 當種群中適應度最高的兩個個體中沒有符合目標適應度的，執(zhí)行以下循環(huán)： （ a）雜交 （ b）把種群中的個體按適應度大小排序 （ c）把適應度最高的兩個個體做局部變異并且更新他們的適應度 人工智能課程報告 16 當皇后數(shù)為 8時： 當皇后數(shù)為 20時（因為界大小原因沒有選擇打印解）： 人工智能課程報告 17 當皇后數(shù)為 30時（因為界大小原因沒有選擇打印解）： 此時回溯法的運行時間超過 20s，沒有繼續(xù)向下運行。對新種群利用 qsort 排序函數(shù)按適應度大小給種群排序，并對適應度最高的兩個個體進行局部變異，如果這兩個個體中有達到適應度 n（ n1）的，即找到了一個解，則算法結束，否則繼續(xù)進行種群的繁衍。 沖突度算法是計算每列皇后與其他列皇后是否在同一行或在對角線上，如果是則沖突數(shù)加 1，整個棋盤的沖突數(shù)是每一列皇后沖突數(shù)之和除以 2。如果該點安全，則 column ++，轉到 1），否則 row++，繼續(xù)執(zhí)行循環(huán)。 queen 序列保存每列皇后的位置 unitConflict 當前棋盤皇后的總沖突數(shù) eachConflict 每列棋盤皇后的總沖突數(shù) 回溯法（遞歸） 回溯法的算法思想 是從棋盤的第 column = 0列開始，對于棋盤每一列再從第row = 0行放置皇后，如果棋盤該位置與棋盤上已經放置的其他皇后不沖突，則把皇后放置在該位置，進行下一列皇后的放置；如果該列所有行的位置都不安全，則返回上一列。 定義種群 CSP 的最小沖突法 typedef struct { int queen[MAX_QUEENS] 。 int eachFitness[MAX_QUEENS] 。并比較不同 n的情況下各個算法的算法耗時，以及相同 n情況下三個算法的耗時的大小。 要求 ： ⅰ . 輸入 n，并用運行時間比較幾種算法在相同規(guī)模的問題時的求解效率，并列表給出結果。 data[i].value temp) { u = i。 visited[i] == 0 amp。 } for(i=0。 path_num++。 static int G_Search_flag = 0。 u = i。 visited[i] == 0 amp。 } for(i=0。 path_num++。 //標志位 找到目標節(jié)點后退出遞歸 static int fx = 0。 * count = i。 } while(StackNotEmpty(LineSave)) { StackPop(amp。 if ( Edge(G,u,y)==1 amp。SaveQ,amp。 //此時 u 為 w 的父節(jié)點 StackPop(amp。 } } StackPush(amp。 QueueAppend(amp。 *Expand = SumExpand。 StackPush(amp。Q,v0)。 visited[v0]=1。SaveQ)。 } } 2）寬度優(yōu)先搜索 // v0起始節(jié)點 vg目標節(jié)點 // // Expand返回擴展結點數(shù) // // count返回路徑結點數(shù) // // BFS_path[]存儲路徑信息 // // G、 data[]用來讀取圖的各種信息 // 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。 if(DFS_flag) break。amp。 w != 1) 人工智能課程報告 9 { if(w == vg) { DFS_flag = 1。 visited[v0]=1。 static int DFS_flag = 0。 深度優(yōu)先搜索 寬度優(yōu)先搜索 A*算法 貪婪算法 擴展節(jié)點數(shù) 12 11 5 4 路徑節(jié)點數(shù) 5 4 5 4 人工智能課程報告 8 從運行結果中可以看出，在搜索的過程中： DFS 算法擴展結點數(shù)為 12 BFS 算法擴展結點數(shù)為 11 A*算法擴展結點數(shù)為 5 貪婪算法擴展結點數(shù)為 4 所以在求解該問題時，貪婪算法的效率最高，其次是 A*算法，然后是 BFS算法，最后是 DFS 算法。 A*算法 void A_Search(AdjMGraph G, HeuristicG data[], int v0, int vg, int distance, int *Expand, int visited[]) v0起始節(jié)點 vg目標節(jié)點 distance用來保存已經過路徑值 Expand返回擴展結點數(shù) G、 data[]用來讀取圖的各種信息 A*算法思想 是找到起始節(jié)點 v0 的所有鄰接頂點，比較所有鄰接頂點的 fx值（ fx = 到 v0 已經經過路徑值 +v0 到鄰接頂點 w 的邊的路徑值 distance+鄰接頂