人工智能課程設計報告

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

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

3、是有向圖。這里我用了有向圖的存儲結構有兩種：鄰接矩陣和鄰接表。下面是數據結構的聲明：（1）鄰接矩陣類：#001 class AdjMWGraph#002 #003 private:#004SeqList<VT> Vertices;/頂點順序表#005WT EdgeMaxVerticesMaxVertices;/邊權值數組#006int numOfEdges;/邊的個數#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);/構造函數#011AdjMWGraph(void);/析構函數#012int NumOfVertices(void)const/取頂點個數#013return Vertices.Size();#014int NumOfEdges(void)const/取邊的個數#015return numOfEdges;#016VT GetValue(const int v)const;/取頂點數值#017WT GetWeight(

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

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

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

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

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;/頂點順序表#005int numOfEdges;/邊數#006#007void DepthFirstSearch(const int v, int visited, void visit(VT#008

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

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

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

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

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

15、t row;/行下標#004int col;/列下標#005WT weight;/權值#006 ;#007 void CreatGraph(AdjMWGraph &G, VT V, int n, RowColWeight E,int e)#008 /在圖G中插入n個頂點V和e條邊E#009 #010/在圖G中插入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個頂點V和e條邊E#019 #020/在圖G中插入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 代價一致寬

17、度優(yōu)先從根節(jié)點開始將擴展點的子節(jié)點入優(yōu)先隊列，選擇最小的路徑的子節(jié)點作為下一個擴展點重復，直到隊列為空或找到目標節(jié)點為止#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é)點開始若沒有超過搜索層數將擴展點的子節(jié)點入棧，選擇棧頂元素作為下一個擴展點重復，直到棧為空或找到目標節(jié)點為止#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;/擴展節(jié)點總數#9 SeqStack<int> S;/節(jié)點棧#10 int *visited = new intn;/訪問節(jié)點標記數組#11 int tempw; /記錄下一個訪問節(jié)點#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 << "搜索失??！" << 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é)點開始將擴展點的子節(jié)點入優(yōu)先隊列，選擇最小的

24、啟發(fā)函數值的子節(jié)點作為下一個擴展點重復，直到隊列為空或找到目標節(jié)點為止#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; /擴展節(jié)點總數#9 int cur; /

25、當前節(jié)點#10 int *visited = new intn;/訪問節(jié)點標記數組#11 int tempw; /記錄下一個訪問節(jié)點#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é)點開始將擴展點的子節(jié)點入優(yōu)先隊列，選擇最小的路徑與啟發(fā)函數值之和的子節(jié)點作為下一個擴展點重復，直到隊列為空或找到目標節(jié)點為止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; /擴展節(jié)點總數int cur; /當前節(jié)點int *visited = new intn;/訪問節(jié)點標記數組int tempw; /記錄下一個訪問節(jié)點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 設計表示主要的函數:#001 DijkPrintLoad

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

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

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

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

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

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) /當前行數觸底，即完成了一個矩陣，將它輸出#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 本函數為產生新的種群函數，其中 select（）為選擇操作，crossover（）為交叉操作（3） CSP最小沖突#1 bool adjust_row(int row) #2 int cur_col = Rrow;#3 int o

39、ptimal_col = cur_col;/最佳列號，設置為當前列，然后更新#4 int min_conflict = coloptimal_col + pdiaggetP(row, optimal_col) - 1#5 + cdiaggetC(row, optimal_col) - 1;/對角線沖突數為當前對角線皇后數減一#6 for (int i = 0; i < N; i+) /逐個檢查第row行的每個位置#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相對更耗時，所以只在滿足上面基本條件后才檢查#28 #29 #30 /當前點就是最佳點，一切都保持不變#31 return false;/如果都沒變的話，肯定不滿足終止條件，否則

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