人工智能課程設(shè)計(jì)報(bào)告

1、人工智能課程設(shè)計(jì)報(bào)告班級(jí)：191134學(xué)號(hào)：20131000479學(xué)生姓名：陳聰兒指導(dǎo)老師：趙曼日期： 2015年11月目錄第 1 章1羅馬利亞度假問題11.1題目?jī)?nèi)容11.2需求分析11.3設(shè)計(jì)11.3.1設(shè)計(jì)思想11.3.2設(shè)計(jì)表示101.4調(diào)試分析101.4.1調(diào)試結(jié)果與比較101.4.2算法比較與總結(jié)111.4.3調(diào)試中遇到的問題111.5用戶手冊(cè)121.6測(cè)試數(shù)據(jù)及結(jié)果121.7源程序清單12第 2 章13N皇后問題132.1題目?jī)?nèi)容132.2需求分析132.3設(shè)計(jì)132.3.1設(shè)計(jì)思想132.3.2算法代碼142.4調(diào)試分析162.4.1調(diào)試中遇到的問題162.4.2調(diào)試截圖162

2、.4.3對(duì)比和總結(jié)192.5用戶手冊(cè)202.6測(cè)試數(shù)據(jù)及測(cè)試結(jié)果202.7源程序清單20人工智能課程報(bào)告第 1 章羅馬利亞度假問題1.1 題目?jī)?nèi)容分別用代價(jià)一致的寬度優(yōu)先、有限制的深度優(yōu)先（預(yù)設(shè)搜索層次）、貪婪算法和A*算法求解“羅馬利亞度假問題”。1.2 需求分析本題是簡(jiǎn)單的路徑搜索問題Ø 讀入數(shù)據(jù)Ø 建圖，以及相關(guān)方法Ø 分別用代價(jià)一致的寬度優(yōu)先、有限制的深度優(yōu)先（預(yù)設(shè)搜索層次）、貪婪算法和A*算法求解路徑Ø 打印路徑，路徑長(zhǎng)度和擴(kuò)展點(diǎn)數(shù)Ø 對(duì)比擴(kuò)展點(diǎn)數(shù)，對(duì)比算法優(yōu)劣1.3 設(shè)計(jì)1.3.1 設(shè)計(jì)思想（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)本軟件用的主體數(shù)據(jù)結(jié)構(gòu)就

3、是有向圖。這里我用了有向圖的存儲(chǔ)結(jié)構(gòu)有兩種：鄰接矩陣和鄰接表。下面是數(shù)據(jù)結(jié)構(gòu)的聲明：（1）鄰接矩陣類：#001 class AdjMWGraph#002 #003 private:#004SeqList<VT> Vertices;/頂點(diǎn)順序表#005WT EdgeMaxVerticesMaxVertices;/邊權(quán)值數(shù)組#006int numOfEdges;/邊的個(gè)數(shù)#007void DepthFirstSearch(const int v, int visited, void Visit(VT item);#008void BroadFirstSearch(const int v

4、, int visited, void Visit(VT item);#009 public:#010AdjMWGraph(const int sz = MaxVertices);/構(gòu)造函數(shù)#011AdjMWGraph(void);/析構(gòu)函數(shù)#012int NumOfVertices(void)const/取頂點(diǎn)個(gè)數(shù)#013return Vertices.Size();#014int NumOfEdges(void)const/取邊的個(gè)數(shù)#015return numOfEdges;#016VT GetValue(const int v)const;/取頂點(diǎn)數(shù)值#017WT GetWeight(

5、const int v1, const int v2)const;/取邊的權(quán)值#018void InsertVertex(const VT &vertex);/插入頂點(diǎn)#019void InsertEdge(const int v1, const int v2, WT weight);/插入邊#020void DeleteVertex(const int v);/刪除頂點(diǎn)#021void DeleteEdge(const int v1, const int v2);/刪除邊#022int GetFirstNeighbor(const int v)const;/取第一個(gè)鄰接頂點(diǎn)#023i

6、nt GetNextNeighbor(const int v1, const int v2)const;/取下一個(gè)鄰接頂點(diǎn)#024void DepthFirstSearch(void Visit(VT item);/深度優(yōu)先遍歷#025void BroadFirstSearch(void Visit(VT item);/廣度優(yōu)先遍歷/增加函數(shù)#026int IsVertex(VT vertex)const;/*判斷頂點(diǎn)vertex是否是有向圖G的頂點(diǎn)，是則返回頂點(diǎn)在頂點(diǎn)順序表中的序號(hào)，否則返回-1。*/#027int IsVertex(int v)const;#028int IsEdge(in

7、t v1,int v2)const;/*判斷第v1個(gè)頂點(diǎn)到第v2個(gè)頂點(diǎn)的邊是否是有向圖G的邊，是則返回1，否則返回0。 */#029int InDegree(int v)const;/*在帶權(quán)有向圖G中求第v個(gè)頂點(diǎn)的入度*/#030int OutDegree(int v)const;/*在帶權(quán)有向圖G中求第v個(gè)頂點(diǎn)的出度*/#031int Degree(int v)const;/*在帶權(quán)有向圖G中求第v個(gè)頂點(diǎn)的度*/#032 ;鄰接表的邊鏈表的結(jié)點(diǎn)的結(jié)構(gòu)體如下：#001 struct EdgeListNode#002 #003int dest;/*與該頂點(diǎn)鄰接的鄰接頂點(diǎn)的序號(hào)*/#004WT

8、weight;/權(quán)值#005 EdgeListNode *next;/*指向下一條邊或弧結(jié)點(diǎn)*/#006 EdgeListNode(EdgeListNode * ptr =NULL):next(ptr)#007EdgeListNode(int d, WT w, EdgeListNode * ptr = NULL):dest(d), weight(w), #008 next(ptr)/構(gòu)造函數(shù)2#009 ;鄰接表的頂點(diǎn)的結(jié)構(gòu)體如下：#001 struct Vertex#002 #003VT data;/頂點(diǎn)信息#004EdgeListNode *adjhead;/*指向第一條依附該頂點(diǎn)的邊*/#

9、005Vertex(EdgeListNode * ptr =NULL):adjhead(ptr)#006Vertex(VT d, EdgeListNode * ptr =NULL):data(d),adjhead(ptr)#007 ;（2）鄰接表類：#001 class AdjLWGraph#002 #003 private:#004SeqList<Vertex> Vertices;/頂點(diǎn)順序表#005int numOfEdges;/邊數(shù)#006#007void DepthFirstSearch(const int v, int visited, void visit(VT#008

10、 Vertex);/私有的深度優(yōu)先搜索函數(shù)#009void BroadFirstSearch(const int v, int visited, void visit(VT#010 Vertex);/私有的廣度優(yōu)先搜索函數(shù)#011 public:#012AdjLWGraph(const int sz = MaxVertices);/構(gòu)造函數(shù)#013AdjLWGraph(void);/析構(gòu)函數(shù)#014#015int NumOfVertices(void)const/返回頂點(diǎn)數(shù)目#016return Vertices.Size();#017int NumOfEdges(void)const/返回邊

11、數(shù)目#018return numOfEdges;#019VT GetValue(const int i)const;/返回第i個(gè)頂點(diǎn)的信息#020WT GetWeight(const int v1, const int v2)const;/返回第v1個(gè)頂點(diǎn)到第v2個(gè)#021 頂點(diǎn)的邊的權(quán)值#022void InsertVertex(const VT &vertex);/在圖的鄰接表中插入值為vertex的頂點(diǎn)#023void InsertEdge(const int v1, const int v2, WT weight);/在圖的鄰接表中#024 插入第v1個(gè)頂點(diǎn)到第v2個(gè)頂點(diǎn)、權(quán)值

12、為weight的邊#025void DeleteVertex(const int v);/在圖的鄰接表中刪除第v個(gè)頂點(diǎn)#026void DeleteEdge(const int v1, const int v2);/在圖的鄰接表中刪除第v1個(gè)頂#027 點(diǎn)到第v2個(gè)頂點(diǎn)的#028int GetFirstNeighbor(const int v);/返回第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)#029int GetNextNeighbor(const int v1, const int v2);/返回第v個(gè)頂點(diǎn)的v2#030 個(gè)頂點(diǎn)之后的下一個(gè)鄰接頂點(diǎn)#031void DepthFirstSearch(voi

13、d visit(VT Vertex);/公有的深度優(yōu)先搜索函數(shù)#032void BroadFirstSearch(void visit(VT Vertex);/公有的廣度優(yōu)先搜索函數(shù)#033 /補(bǔ)充六個(gè)函數(shù)#034int IsVertex(VT vertex)const;/*判斷頂點(diǎn)vertex是否是有向圖G的頂點(diǎn)，#035 是則返回頂點(diǎn)在頂點(diǎn)順序表中的序號(hào)，否則返回-1。*/#036int IsVertex(int v)const;/*判斷有向圖G是否有第i個(gè)頂點(diǎn)，有則返回#037 1，沒有則返回0。*/#038int IsEdge(int v1,int v2)const;/*判斷第v1個(gè)頂

14、點(diǎn)到第v2個(gè)頂點(diǎn)的邊是否是#039 有向圖G的邊，是則返回1，否則返回0。 */#040int InDegree(int v)const;/*在帶權(quán)有向圖G中求第v個(gè)頂點(diǎn)的入度*/#041int OutDegree(int v)const;/*在帶權(quán)有向圖G中求第v個(gè)頂點(diǎn)的出度*/#042int Degree(int v)const;/*在帶權(quán)有向圖G中求第v個(gè)頂點(diǎn)的度*/#043 鄰接表和鄰接矩陣示意圖如下：（2）算法設(shè)計(jì)要找出城市之間的路徑首先需要將城市之間的路徑圖畫出，就這個(gè)題目我設(shè)計(jì)了兩種構(gòu)造圖的方法，方法設(shè)計(jì)如下：#001 struct RowColWeight#002 #003in

15、t row;/行下標(biāo)#004int col;/列下標(biāo)#005WT weight;/權(quán)值#006 ;#007 void CreatGraph(AdjMWGraph &G, VT V, int n, RowColWeight E,int e)#008 /在圖G中插入n個(gè)頂點(diǎn)V和e條邊E#009 #010/在圖G中插入n個(gè)頂點(diǎn)#011for(int i = 0; i < n; i+) #012G.InsertVertex(Vi);#013/在圖G中插入e條邊#014for(int k = 0; k < e; k+) #015G.InsertEdge(Ek.row, Ek.col,

16、 Ek.weight);#016 #017 void CreatGraph(AdjLWGraph &G, VT V, int n, RowColWeight E,int e)#018 /在圖G中插入n個(gè)頂點(diǎn)V和e條邊E#019 #020/在圖G中插入n個(gè)頂點(diǎn)#021for(int i = 0; i < n; i+) #022G.InsertVertex(Vi);#023/在圖G中插入e條邊#024for(int k = 0; k < e; k+) #025G.InsertEdge(Ek.row, Ek.col, Ek.weight);#026 ;（3）算法思想l 代價(jià)一致寬

17、度優(yōu)先從根節(jié)點(diǎn)開始將擴(kuò)展點(diǎn)的子節(jié)點(diǎn)入優(yōu)先隊(duì)列，選擇最小的路徑的子節(jié)點(diǎn)作為下一個(gè)擴(kuò)展點(diǎn)重復(fù)，直到隊(duì)列為空或找到目標(biāo)節(jié)點(diǎn)為止#1 void Dijkstra(GraphType &G, int v0,int v1,WT distance, int path,int &Expand) /最短路徑算法#2 #3 int n = G.NumOfVertices();#4 int *s = new intn;#5 WT minDis;#6 int i, j, u;#7 int SumExpand = 0;#8 for (i = 0; i < n; i+)#9 #10 distance

18、i = G.GetWeight(v0, i);#11 si = 0;#12 if (i != v0&&distancei < MaxWeight)#13 pathi = v0;#14 else pathi = -1;#15 #16 sv0 = 1;#17 for (i = 1; i < n; i+)#18 #19 minDis = MaxWeight;#20 for (j = 0; j < n; j+)#21 #22 if (sj = 0 && distancej < minDis)#23 #24 u = j;#25 minDis = d

19、istancej;#26 #27 #28 if (minDis = MaxWeight|u=v1)return;#29#30 su = 1;#31 for (j = 0; j < n; j+)#32 if (sj = 0 && G.GetWeight(u, j) < MaxWeight&&#33 distanceu + G.GetWeight(u, j) < distancej)#34 #35 SumExpand+;#36 distancej = distanceu + G.GetWeight(u, j);#37 pathj = u;#38 #

20、39 Expand = SumExpand;#40 #41 l 有限制的深度搜索從根節(jié)點(diǎn)開始若沒有超過搜索層數(shù)將擴(kuò)展點(diǎn)的子節(jié)點(diǎn)入棧，選擇棧頂元素作為下一個(gè)擴(kuò)展點(diǎn)重復(fù)，直到棧為空或找到目標(biāo)節(jié)點(diǎn)為止#1 void Non_recDfs(AdjMWGraph &G, VT a, VT b, vector<int> &path,int *Expand)#2 #3#4 int tempa = G.IsVertex(a);#5 int tempb = G.IsVertex(b);#6 int n = G.NumOfVertices();#7 int e = G.NumOfEdg

21、es();#8 int SumExpand = 0;/擴(kuò)展節(jié)點(diǎn)總數(shù)#9 SeqStack<int> S;/節(jié)點(diǎn)棧#10 int *visited = new intn;/訪問節(jié)點(diǎn)標(biāo)記數(shù)組#11 int tempw; /記錄下一個(gè)訪問節(jié)點(diǎn)#12 memset(visited, 0, n*sizeof(int);#13 S.Push(tempa);#14 visitedtempa = 1;#15 while (true)#16 #17 int temptop = S.GetTop();#18#19 tempw = G.GetFirstNeighbor(temptop);#20 whil

22、e (visitedtempw = 1)#21 #22 tempw = G.GetNextNeighbor(temptop, tempw);#23 #24 while (tempw = -1)#25 #26 S.Pop();#27 temptop = S.GetTop();#28#29 tempw = G.GetFirstNeighbor(temptop);#30 while (visitedtempw = 1)#31 #32 tempw = G.GetNextNeighbor(temptop, tempw);#33 #34 #35#36 S.Push(tempw);#37 SumExpand

23、+;#38 visitedtempw = 1;#39 if (tempw = tempb)break;#40 #41 *Expand = SumExpand;#42 if (!S.NotEmpty()#43 #44 std:cout << "搜索失?。?quot; << endl;#45 #46 else#47 #48 while (S.NotEmpty()#49 #50 int temptop = S.Pop();#51 path.push_back(temptop);#52 #53 #54 l 貪婪搜索算法從根節(jié)點(diǎn)開始將擴(kuò)展點(diǎn)的子節(jié)點(diǎn)入優(yōu)先隊(duì)列，選擇最小的

24、啟發(fā)函數(shù)值的子節(jié)點(diǎn)作為下一個(gè)擴(kuò)展點(diǎn)重復(fù)，直到隊(duì)列為空或找到目標(biāo)節(jié)點(diǎn)為止#1 void Greedy(AdjMWGraph &G, VT a, VT b, int h, int path, WT distance,int *Expand)#2 #3 int tempa = G.IsVertex(a);#4 int tempb = G.IsVertex(b);#5 int n = G.NumOfVertices();#6 int e = G.NumOfEdges();#7 node = new Noden;#8 int SumExpand = 0; /擴(kuò)展節(jié)點(diǎn)總數(shù)#9 int cur; /

25、當(dāng)前節(jié)點(diǎn)#10 int *visited = new intn;/訪問節(jié)點(diǎn)標(biāo)記數(shù)組#11 int tempw; /記錄下一個(gè)訪問節(jié)點(diǎn)#12 memset(visited, 0, n*sizeof(int);#13 for (int i = 0; i < n; i+)#14 distancei = 0;#15 for (int i = 0; i < n; i+)#16 #17 nodei.Set(i, hi);#18 #19 priority_queue<Node> q;#20 q.push(nodetempa);#21 visitedtempa = 1;#22 whil

26、e (!q.empty()#23 #24 cur = q.top().index;#25 q.pop();#26 SumExpand+;#27 tempw = G.GetFirstNeighbor(cur);#28 if (visitedtempw = 1)#29 tempw = G.GetNextNeighbor(cur, tempw);#30#31 while (tempw != -1)#32 #33 /nodetempw.Set(tempw, G.GetWeight(cur, tempw)+nodecur.priority);#34 pathtempw = cur;#35 distanc

27、etempw = G.GetWeight(cur, tempw) + distancecur;#36 if (tempw = tempb) return;#37 q.push(nodetempw);#38 visitedtempw = 1;#39 tempw = G.GetNextNeighbor(cur, tempw);#40 #41 *Expand = SumExpand;#42 #43 #44 l A*搜索算法從根節(jié)點(diǎn)開始將擴(kuò)展點(diǎn)的子節(jié)點(diǎn)入優(yōu)先隊(duì)列，選擇最小的路徑與啟發(fā)函數(shù)值之和的子節(jié)點(diǎn)作為下一個(gè)擴(kuò)展點(diǎn)重復(fù)，直到隊(duì)列為空或找到目標(biāo)節(jié)點(diǎn)為止void ASearch(AdjMWGraph &

28、amp;G, VT a, VT b, int h, int path, WT distance, int *Expand)int tempa = G.IsVertex(a);int tempb = G.IsVertex(b);int n = G.NumOfVertices();int e = G.NumOfEdges();node = new Noden;int SumExpand = 0; /擴(kuò)展節(jié)點(diǎn)總數(shù)int cur; /當(dāng)前節(jié)點(diǎn)int *visited = new intn;/訪問節(jié)點(diǎn)標(biāo)記數(shù)組int tempw; /記錄下一個(gè)訪問節(jié)點(diǎn)memset(visited, 0, n*sizeof

29、(int);for (int i = 0; i < n; i+)distancei = 0;priority_queue<Node> q;nodetempa.Set(tempa, htempa);q.push(nodetempa);visitedtempa = 1;while (!q.empty()cur = q.top().index;q.pop();SumExpand+;tempw = G.GetFirstNeighbor(cur);if (visitedtempw = 1)tempw = G.GetNextNeighbor(cur, tempw);while (temp

30、w != -1&&visitedtempw=0)pathtempw = cur;distancetempw = G.GetWeight(cur, tempw) + distancecur;nodetempw.Set(tempw, distancetempw + htempw);if (tempw = tempb) return;q.push(nodetempw);visitedtempw = 1;tempw = G.GetNextNeighbor(cur, tempw);*Expand = SumExpand;1.3.2 設(shè)計(jì)表示主要的函數(shù):#001 DijkPrintLoad

31、/代價(jià)一致的寬度優(yōu)先#002 Non_recDfs/有限制的深度優(yōu)先#003 Greedy/貪婪搜索算法#004 ASearch/A*算法1.4 調(diào)試分析 1.4.1 調(diào)試結(jié)果與比較1. 代價(jià)一致的寬度優(yōu)先2. 有限制的深度優(yōu)先3. 貪婪搜索算法4. A*算法1.4.2 算法比較與總結(jié)節(jié)點(diǎn)數(shù)路徑長(zhǎng)度效率Optimality: Completeness: BFS114182NoYESDFS 126053NoNOGreedy24501NONOA*算法34504YESYES1.4.3 調(diào)試中遇到的問題在程序運(yùn)行時(shí)，解環(huán)復(fù)原的時(shí)候需要傳入std:vector，此時(shí)容易出現(xiàn)內(nèi)存泄漏問題。這個(gè)時(shí)候需要將s

32、td:vector定義為全局變量，并采用引用傳值方式銷毀std:vector，避免內(nèi)存泄漏。一開始在建環(huán)的時(shí)候直接調(diào)用了鏈表的刪除函數(shù)，導(dǎo)致程序陷入死循環(huán)，應(yīng)直接將后續(xù)節(jié)點(diǎn)銷毀，注意，此處可鏈表刪除完全不同。1.5 用戶手冊(cè)直接運(yùn)行程序即可，沒有用戶要操作的地方。1.6 測(cè)試數(shù)據(jù)及結(jié)果請(qǐng)看第1.4.1節(jié)。1.7 源程序清單AdjMWGraph.cppAdjWGraphApp.hCreatAdjWGraph.hread.cppSeqList.hSeqQueue.hSeqStack.hGraphMindTest.cpp20第 2 章N皇后問題2.1 題目?jī)?nèi)容設(shè)計(jì)目的：Ø 分別用回溯法（遞

33、歸）、GA算法和CSP的最小沖突法求解n皇后問題。設(shè)計(jì)內(nèi)容： 1. 輸入n，并用運(yùn)行時(shí)間比較幾種算法在相同規(guī)模的問題時(shí)的求解效率，并列表給出結(jié)果。2. 比較同一算法在n不相同時(shí)的運(yùn)行時(shí)間，分析算法的時(shí)間復(fù)雜性，并列表給出結(jié)果。2.2 需求分析n皇后問題：在n*n格的國(guó)際象棋上擺放n個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上2.3 設(shè)計(jì)2.3.1 設(shè)計(jì)思想（1） 回溯法回溯法采用試錯(cuò)的思想，它嘗試分步的去解決一個(gè)問題。在分步解決問題的過程中，當(dāng)它通過嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的解答的時(shí)候，它將取消上一步甚至是上幾步的計(jì)算，再通過其它的可能的分步解答

34、再次嘗試尋找問題的答案。回溯法通常用最簡(jiǎn)單的遞歸方法來(lái)實(shí)現(xiàn)，在反復(fù)重復(fù)上述的步驟后可能出現(xiàn)兩種情況：找到一個(gè)可能存在的正確的答案在嘗試了所有可能的分步方法后宣告該問題沒有答案在最壞的情況下，回溯法會(huì)導(dǎo)致一次復(fù)雜度為指數(shù)時(shí)間的計(jì)算。（2） 遺傳算法遺傳算法通常實(shí)現(xiàn)方式為一種計(jì)算機(jī)模擬。對(duì)于一個(gè)最優(yōu)化問題，一定數(shù)量的候選解（稱為個(gè)體）的抽象表示（稱為染色體）的種群向更好的解進(jìn)化。傳統(tǒng)上，解用二進(jìn)制表示（即0和1的串），但也可以用其他表示方法。進(jìn)化從完全隨機(jī)個(gè)體的種群開始，之后一代一代發(fā)生。在每一代中，整個(gè)種群的適應(yīng)度被評(píng)價(jià)，從當(dāng)前種群中隨機(jī)地選擇多個(gè)個(gè)體（基于它們的適應(yīng)度），通過自然選擇產(chǎn)生新的生

35、命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。（3） CSP最小沖突法約束滿足問題（CSP）是一類數(shù)學(xué)問題，它的定義為一組狀態(tài)必須滿足于若干約束或限制的對(duì)象(object)。 CPSs表示的是問題中的實(shí)體，有限數(shù)量、同類型的約束加之于變量之上, 這類問題通過 約束滿足 方法解決。CSPs是人工智能和運(yùn)籌學(xué) 的熱門主題, 這是因?yàn)樗鼈児街械囊?guī)律提供了一個(gè)分析和解決很多不相關(guān)問題的共同基礎(chǔ)。 CSPs通常表現(xiàn)出高復(fù)雜性, 需要結(jié)合啟發(fā)式搜索 和 聯(lián)合搜索 方法來(lái)在合理的時(shí)間內(nèi)解決問題。 布爾可滿足性問題 (SAT), ,可滿足性的理論 (SMT)和回答集編程 (ASP) 大致可以認(rèn)為是特定形式

36、的約束滿足問題2.3.2 算法代碼（1） 回溯法#1 void Solve(int rowCurrent, int *&NQueen, int n, int &count)#2 #3 if (count = 0)#4 #5 if (rowCurrent = n) /當(dāng)前行數(shù)觸底，即完成了一個(gè)矩陣，將它輸出#6 #7 count+;#8 return;#9 #10 for (int i = 0; i < n; i+)#11 #12 NQueenrowCurrent = i; /row行i列試一試#13 if (Check(rowCurrent, NQueen)#14 #15

37、 Solve(rowCurrent + 1, NQueen, n, count); /移向下一行#16 #17 #18 #19 （2） 遺傳算法#1 void evolution()#2 #3 #4 int i = 0, mate1, mate2;#5 while (i<POPSIZE)#6 #7 mate1 = select();#8 mate2 = select();#9 /cout<<mate1<<" "<<mate2<<endl;#10 crossover(oldpopmate1, oldpopmate2, ne

38、wpopi, newpopi + 1);#11 mutation(newpopi);#12 newpopi.fitness = fitness_count(newpopi);#13 mutation(newpopi + 1);#14 newpopi + 1.fitness = fitness_count(newpopi + 1);#15 i += 2;#16 #17 本函數(shù)為產(chǎn)生新的種群函數(shù)，其中 select（）為選擇操作，crossover（）為交叉操作（3） CSP最小沖突#1 bool adjust_row(int row) #2 int cur_col = Rrow;#3 int o

39、ptimal_col = cur_col;/最佳列號(hào)，設(shè)置為當(dāng)前列，然后更新#4 int min_conflict = coloptimal_col + pdiaggetP(row, optimal_col) - 1#5 + cdiaggetC(row, optimal_col) - 1;/對(duì)角線沖突數(shù)為當(dāng)前對(duì)角線皇后數(shù)減一#6 for (int i = 0; i < N; i+) /逐個(gè)檢查第row行的每個(gè)位置#7 if (i = cur_col) #8 continue;#9 #10 int conflict = coli + pdiaggetP(row, i) + cdiagget

40、C(row, i);#11 if (conflict < min_conflict) #12 min_conflict = conflict;#13 optimal_col = i;#14 #15 #16 if (optimal_col != cur_col) /要更新col,pdiag,cdiag#17 colcur_col-;#18 pdiaggetP(row, cur_col)-;#19 cdiaggetC(row, cur_col)-;#20#21 coloptimal_col+;#22 pdiaggetP(row, optimal_col)+;#23 cdiaggetC(row

41、, optimal_col)+;#24 Rrow = optimal_col;#25 if (colcur_col = 1 && coloptimal_col = 1#26 && pdiaggetP(row, optimal_col) = 1 && cdiaggetC(row, optimal_col) = 1) #27 return qualify();/qualify相對(duì)更耗時(shí)，所以只在滿足上面基本條件后才檢查#28 #29 #30 /當(dāng)前點(diǎn)就是最佳點(diǎn)，一切都保持不變#31 return false;/如果都沒變的話，肯定不滿足終止條件，否則

42、上一次就應(yīng)該返回true并終止了#32 2.4 調(diào)試分析2.4.1 調(diào)試中遇到的問題用C/C+編程過程中遇到的問題，最令人頭疼的莫過于對(duì)指針的管理了，有時(shí)候一不小心就成了野指針，運(yùn)行時(shí)往往出錯(cuò)。由于我的編程習(xí)慣還是相對(duì)比較好的，所以在寫這個(gè)程序的時(shí)候沒有遇到野指針的問題，但是遇到了和指針相關(guān)的問題。就是在程序運(yùn)行時(shí)突然跳出個(gè)對(duì)話框說(shuō)某某指針指向的內(nèi)存區(qū)不可寫或不可讀，一般這類問題比較好解決，直接去使用該指針的地方查看指針即可。由于思路清晰，所以在整個(gè)程序的寫作過程中我并沒有遇到太多的問題。2.4.2 調(diào)試截圖（1） 回溯法回溯法在皇后數(shù)目較小的，很占優(yōu)勢(shì)，它的速度非常的快，但隨著皇后數(shù)目的增加，回溯法顯得很不實(shí)用，在n>30時(shí)，用回溯法已不能較好的解決n皇后問題（2） 遺傳算法遺傳算法優(yōu)點(diǎn)是能很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全局最優(yōu)解，全局搜索能力強(qiáng)；缺點(diǎn)是收斂較慢，局部搜索能力較弱，運(yùn)行時(shí)間長(zhǎng)，且容易受參數(shù)的影響。（3） 最小沖突算法這