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

1、人工智能課程設(shè)計(jì)報(bào)告 課 程:人工智能課程設(shè)計(jì)報(bào)告 班 級(jí): 姓 名: 學(xué) 號(hào): 指導(dǎo)教師:趙曼 2015年11月人工智能課程設(shè)計(jì)報(bào)告課程背景 人工智能（Artificial Intelligence），英文縮寫為AI。它是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。 人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應(yīng)的智能機(jī)器，該領(lǐng)域的研究包括機(jī)器人、語(yǔ)言識(shí)別、圖像識(shí)別、自然語(yǔ)言處理和專家系統(tǒng)等。人工智能從誕生以來(lái)，理論和技術(shù)日益成熟，應(yīng)用領(lǐng)域也不斷擴(kuò)大，可以設(shè)想，未來(lái)人工智能帶來(lái)的科技產(chǎn)品，將會(huì)是人

2、類智慧的“容器”。人工智能是對(duì)人的意識(shí)、思維的信息過(guò)程的模擬。人工智能不是人的智能，但能像人那樣思考、也可能超過(guò)人的智能。人工智能是一門極富挑戰(zhàn)性的科學(xué)，從事這項(xiàng)工作的人必須懂得計(jì)算機(jī)知識(shí)，心理學(xué)和哲學(xué)。人工智能是包括十分廣泛的科學(xué)，它由不同的領(lǐng)域組成，如機(jī)器學(xué)習(xí)，計(jì)算機(jī)視覺等等，總的說(shuō)來(lái)，人工智能研究的一個(gè)主要目標(biāo)是使機(jī)器能夠勝任一些通常需要人類智能才能完成的復(fù)雜工作。但不同的時(shí)代、不同的人對(duì)這種“復(fù)雜工作”的理解是不同的。人工智能是計(jì)算機(jī)學(xué)科的一個(gè)分支，二十世紀(jì)七十年代以來(lái)被稱為世界三大尖端技術(shù)之一（空間技術(shù)、能源技術(shù)、人工智能）。也被認(rèn)為是二十一世紀(jì)三大尖端技術(shù)（基因工程、納米科學(xué)、人工

3、智能）之一。這是因?yàn)榻陙?lái)它獲得了迅速的發(fā)展，在很多學(xué)科領(lǐng)域都獲得了廣泛應(yīng)用，并取得了豐碩的成果，人工智能已逐步成為一個(gè)獨(dú)立的分支，無(wú)論在理論和實(shí)踐上都已自成一個(gè)系統(tǒng)。人工智能是研究使計(jì)算機(jī)來(lái)模擬人的某些思維過(guò)程和智能行為（如學(xué)習(xí)、推理、思考、規(guī)劃等）的學(xué)科，主要包括計(jì)算機(jī)實(shí)現(xiàn)智能的原理、制造類似于人腦智能的計(jì)算機(jī)，使計(jì)算機(jī)能實(shí)現(xiàn)更高層次的應(yīng)用。人工智能將涉及到計(jì)算機(jī)科學(xué)、心理學(xué)、哲學(xué)和語(yǔ)言學(xué)等學(xué)科?？梢哉f(shuō)幾乎是自然科學(xué)和社會(huì)科學(xué)的所有學(xué)科，其范圍已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)科學(xué)的范疇，人工智能與思維科學(xué)的關(guān)系是實(shí)踐和理論的關(guān)系，人工智能是處于思維科學(xué)的技術(shù)應(yīng)用層次，是它的一個(gè)應(yīng)用分支。從思維觀點(diǎn)看

4、，人工智能不僅限于邏輯思維，要考慮形象思維、靈感思維才能促進(jìn)人工智能的突破性的發(fā)展，數(shù)學(xué)常被認(rèn)為是多種學(xué)科的基礎(chǔ)科學(xué)，數(shù)學(xué)也進(jìn)入語(yǔ)言、思維領(lǐng)域，人工智能學(xué)科也必須借用數(shù)學(xué)工具，數(shù)學(xué)不僅在標(biāo)準(zhǔn)邏輯、模糊數(shù)學(xué)等范圍發(fā)揮作用，數(shù)學(xué)進(jìn)入人工智能學(xué)科，它們將互相促進(jìn)而更快地發(fā)展。題目二：n皇后問(wèn)題一.問(wèn)題描述分別用回溯法（遞歸）、GA算法和CSP的最小沖突法求解n皇后問(wèn)題。即如何能夠在 n×n 的國(guó)際象棋棋盤上放置n個(gè)皇后，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。要求：. 輸入n，并用運(yùn)行時(shí)間比較幾種算法在相同規(guī)模的問(wèn)題時(shí)的求解效

5、率，并列表給出結(jié)果。. 比較同一算法在n不相同時(shí)的運(yùn)行時(shí)間，分析算法的時(shí)間復(fù)雜性，并列表給出結(jié)果。如八皇后問(wèn)題的一個(gè)解二.設(shè)計(jì)分析1.算法分析 1) 回溯法（遞歸）回溯法解題的一般步驟編輯（1）針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。引入一個(gè)整型一維數(shù)組col來(lái)存放最終結(jié)果，coli就表示在棋盤第i列、coli行有一個(gè)皇后，為了使程序再找完了全部解后回到最初位置，設(shè)定col0的初值為0，即當(dāng)回溯到第0列時(shí)，說(shuō)明以求得全部解，結(jié)束程序運(yùn)行。為了方便算法的實(shí)現(xiàn)，引入三個(gè)整型數(shù)組來(lái)表示當(dāng)前列在三個(gè)方向上的狀

6、態(tài) ：a ai=0表示第i行上還沒(méi)有皇后；b bi=0表示第i列反斜線/上沒(méi)有皇后；c ci=0表示第i列正斜線上沒(méi)有皇后。棋盤中同一反斜線/上的方格的行號(hào)與列號(hào)相同；同一正斜線上的方格的行號(hào)與列號(hào)之差均相同，這就是判斷斜線的依據(jù)。初始時(shí)，所有行和斜線上都沒(méi)有皇后，從第1列的第1行配置第一個(gè)皇后開始，在第m列，colm行放置了一個(gè)合理的皇后，準(zhǔn)備考察第m+1列時(shí)，在數(shù)組a，b和c中為第m列，colm行的位置設(shè)定有皇后的標(biāo)志；當(dāng)從第m列回溯到m-1列時(shí)，并準(zhǔn)備調(diào)整第m-1列的皇后配置時(shí)，清除在數(shù)組a,b和c對(duì)應(yīng)位置的值都為1來(lái)確定。 2)遺傳算法遺傳算法的基本運(yùn)算過(guò)程如下：a)初始化：設(shè)置進(jìn)化代

7、數(shù)計(jì)數(shù)器t=0，設(shè)置最大進(jìn)化代數(shù)T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。b)個(gè)體評(píng)價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。遺傳算法遺傳算法c)選擇運(yùn)算:將選擇算子作用于群體。選擇的目的是把優(yōu)化的個(gè)體直接遺傳到下一代或通過(guò)配對(duì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的。d)交叉運(yùn)算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。e)變異運(yùn)算：將變異算子作用于群體。即是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。群體P(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體P(t+1)。f)終止條件判斷:若t=T,則以進(jìn)化過(guò)程中所得到的具有最大適應(yīng)度個(gè)體

8、作為最優(yōu)解輸出，終止計(jì)算。3）csp最小沖突法（1）初始化N個(gè)皇后的一個(gè)放置，允許有沖突（2）考慮某一行的某個(gè)皇后，她可能與x個(gè)皇后沖突，然后看看將這個(gè)皇后移動(dòng)到這一行的哪個(gè)空位能使得與其沖突的皇后個(gè)數(shù)最少，就移動(dòng)到那里。（也可以考慮列，是等價(jià)的）（3）不斷執(zhí)行（2），直到?jīng)]有沖突為止2.數(shù)據(jù)結(jié)構(gòu)使用數(shù)組結(jié)構(gòu)存儲(chǔ)相關(guān)數(shù)據(jù)一維數(shù)組：二維數(shù)組：3.算法設(shè)計(jì)1）/回溯搜索 void Function1:DFS(int t,bool isShowTime)if (t = n)/說(shuō)明已經(jīng)排了n行了（從0開始的），即排列結(jié)束了for (int i = 0; i<n; i+)reci = boardi

9、;if (! isShowTime )PrintChessBoard();/輸出棋局count+;return;for (int i = 0; i<n; i+)/有沖突if (veri = 1|rui - t + n = 1|rdi + t = 1) continue;/沒(méi)有沖突veri = 1;rui - t + n = 1;rdi + t = 1;boardt = i;DFS(t + 1, isShowTime);/深搜遞歸/后退處理rdi + t = 0;rui - t + n = 0;veri = 0;return;2）遺傳算法void CGAQueen:PrintChessBo

10、ard(bool PrintChessBoard)bool DisplayAllAnsures=PrintChessBoard;/是否輸出所有棋盤結(jié)果int g = 0, num = 0;InitialPopulation();while (g = 0 && num < this->Iteration)num+;g = 0;for (int k = 0; k < this->Population ; k+)this->FillArea(k);this->CostMatrixk = this->CostFunc(k);this->P

11、opulationSort();if (this->CostMatrix0 = 0)/已經(jīng)完成計(jì)算g = 1;if (DisplayAllAnsures)PrintTheBestAnsure();/*for (i = 0; i <= ChessBoradLenght - 1; i+)cout << "row:" << i << " col:" << this->ChromosomeMatrixi0 << endl;cout << endl;*/this->Ge

12、nerateCrossOverMatrix();this->Mating();this->ApplyMutation();cout << "實(shí)際迭代：" << num <<" 次"<< endl;if (DisplayAllAnsures)cout << "最佳答案為：" << endl;this->PrintTheBestAnsure();3）CSP最小沖突算法/用最小沖突算法調(diào)整第row行的皇后的位置（初始化時(shí)每行都有一個(gè)皇后，調(diào)整后仍然在第

13、row行）/調(diào)整過(guò)后check一下看看是否已經(jīng)沒(méi)有沖突，如果沒(méi)有沖突（達(dá)到終止?fàn)顟B(tài)），返回truebool CSP_Queens:Adjust_row(int row)int cur_col = Rrow;int optimal_col = cur_col;/最佳列號(hào)，設(shè)置為當(dāng)前列，然后更新/計(jì)算總沖突數(shù)int min_conflict = coloptimal_col + pdiagGetP(row, optimal_col) - 1+ cdiagGetC(row, optimal_col) - 1;/對(duì)角線沖突數(shù)為當(dāng)前對(duì)角線皇后數(shù)減一,三次重疊了/逐個(gè)檢查第row行的每個(gè)位置，看看是否存在

14、沖突數(shù)更小的位置for (int i = 0; i < N; i+) if (i = cur_col) continue;int conflict = coli + pdiagGetP(row, i) + cdiagGetC(row, i);if (conflict < min_conflict) min_conflict = conflict;optimal_col = i;/如果最佳列位置改變，則皇后移向新的最小沖突位置，要更新col,pdiag,cdiag，if (optimal_col != cur_col) colcur_col-;pdiagGetP(row, cur_c

15、ol)-;cdiagGetC(row, cur_col)-;coloptimal_col+;pdiagGetP(row, optimal_col)+;cdiagGetC(row, optimal_col)+;Rrow = optimal_col;if (colcur_col = 1 && coloptimal_col = 1&& pdiagGetP(row, optimal_col) = 1 && cdiagGetC(row, optimal_col) = 1) return Qualify();/qualify相對(duì)更耗時(shí)，所以只在滿足上面基本條

16、件后才檢查/否則當(dāng)前點(diǎn)就是最佳點(diǎn)，一切都保持不變r(jià)eturn false;/如果都沒(méi)變的話，肯定不滿足終止條件，否則上一次就應(yīng)該返回true并終止了/檢查沖突bool CSP_Queens:Qualify()for (int i = 0; i < N; i+)if (colRi != 1 |pdiagGetP(i, Ri) != 1 |cdiagGetC(i, Ri) != 1) return false;return true;/最終用戶調(diào)用函數(shù)，numOfQueens為輸入皇后數(shù)，PrintChessBoard判斷是否輸出棋盤表示int CSP_Queens:CSPAlgorithm

17、s(bool PrintChessBord)srand(unsigned)time(NULL);Init();if (Qualify() /運(yùn)氣很好，初始化后就滿足終止條件if (PrintChessBord)Print_result();return 0;bool end = false;while (!end) for (int i = 0; i < N; i+) if (Adjust_row(i) end = true;break;if (PrintChessBord)Print_result();return 0;四.運(yùn)行結(jié)果及分析1.遞歸算法2.遺傳算法3.CSP最小沖突算法4

18、.n=4時(shí)不同算法的比較5.n=8時(shí)不同算法比較結(jié)果分析回溯法在皇后數(shù)目較小的，很占優(yōu)勢(shì)，它的速度非常的快，但隨著皇后數(shù)目的增加，回溯法顯得很不實(shí)用，在n=35時(shí)，用回溯法已不能較好的解決n皇后問(wèn)題。遺傳算法優(yōu)點(diǎn)是能很好的處理約束，能很好的跳出局部最優(yōu)，最終得到全局最優(yōu)解，全局搜索能力強(qiáng)；缺點(diǎn)是收斂較慢，局部搜索能力較弱，運(yùn)行時(shí)間中等，且容易受n值的影響。遺傳算法的運(yùn)行時(shí)間在n很小時(shí)沒(méi)有回溯法快，但是隨著n值的增加，遺產(chǎn)算法的優(yōu)點(diǎn)也就顯現(xiàn)出來(lái)，它能夠解決回溯法不能解決的問(wèn)題。CSP最小沖突法是一種始終都比較快的算法，它的運(yùn)行時(shí)間與皇后是個(gè)數(shù)沒(méi)有必然的聯(lián)系，而且在n很大時(shí)，它顯現(xiàn)出來(lái)運(yùn)行時(shí)間短，

19、效率高的優(yōu)勢(shì)，但它的缺點(diǎn)是會(huì)出現(xiàn)山脊、高原，86%的時(shí)間會(huì)卡住?？偟膩?lái)說(shuō)，CSP最小沖突法較簡(jiǎn)單，也比較快，在皇后的個(gè)數(shù)較多時(shí)體現(xiàn)出來(lái)效率最高，處理多約束大規(guī)模問(wèn)題時(shí)往往不能得到較好的解。 總的來(lái)說(shuō)，回溯在n值很小時(shí)，效率很高，但其求解范圍很小，超過(guò)35基本就解不出來(lái)，遺傳算法求解范圍適中。在n值很大(>100)時(shí)，前兩者都不能再解決，此時(shí)，CSP最小沖突法的效率最高，且與n值沒(méi)有必然的聯(lián)系?？偨Y(jié) 通過(guò)此次課程實(shí)習(xí)不僅大大加深了我對(duì)幾種經(jīng)典搜索算法的理解，而且?guī)椭液芎玫膹?fù)習(xí)了隊(duì)列、堆棧、圖、文件讀寫這幾部分的內(nèi)容，使我對(duì)幾種基本的數(shù)據(jù)結(jié)構(gòu)類型的運(yùn)用更加熟練。在解決這些問(wèn)題的過(guò)程中我不但

20、很好的鞏固了數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)，而且提高了編程及程序調(diào)試能力，增強(qiáng)了自己編程的信心。 總之，在這次課程實(shí)習(xí)過(guò)程中我是實(shí)實(shí)在在學(xué)到了一些課堂上學(xué)不到的東西，同時(shí)也提高了實(shí)踐能力。同時(shí)在這個(gè)過(guò)程中也暴露了自己的不少問(wèn)題，在今后的學(xué)習(xí)過(guò)程成也會(huì)更加有針對(duì)性。最后還要感謝老師的悉心指導(dǎo)，解答我編程過(guò)程中的疑問(wèn)、指出我程序中的不足，及提出可行的解決方法，讓我的程序的功能更加完善。CSP算法源代碼：/CSPAlgorithms.h#pragma onceclass CSP_Queenspublic:/構(gòu)造函數(shù)，numOfQueens為輸入皇后數(shù)，CSP_Queens(int numOfQueens);CS

21、P_Queens();private:/rowi表示當(dāng)前擺放方式下第i行的皇后數(shù)，int *row;/coli表示當(dāng)前擺放方式下第i列的皇后沖突數(shù)int *col;int N; /放置N個(gè)皇后在N*N棋盤上/從左上到右下的對(duì)角線上row-col值是相同的，但是這個(gè)值有可能是負(fù)值，最小為-(N-1)，/所以可以做個(gè)偏移，統(tǒng)一加上N-1，這樣這個(gè)值就在0,2*N-2范圍內(nèi)，將這個(gè)值作為該對(duì)角線的編號(hào)/pdiagi表示當(dāng)前擺放方式下編號(hào)為i的對(duì)角線上的皇后數(shù)int *pdiag;/principal diagonal,主對(duì)角線，左上到右下（表示和主對(duì)角線平行的2N-1條對(duì)角線）/從右上到左下的對(duì)角線

22、row+col的值相同，取值范圍為0, 2 * N - 2，2*N-1條，作為對(duì)角線編號(hào)/cdiagi表示編號(hào)為i的對(duì)角線上的皇后數(shù)int *cdiag;/counter diagonal,副對(duì)角線/R用來(lái)存儲(chǔ)皇后放置位置，Rrow = col表示(row,col)處,即“第row行第col列”有個(gè)皇后int *R;public:int swap(int &a, int &b);/給定二維矩陣的一個(gè)點(diǎn)坐標(biāo)，返回其對(duì)應(yīng)的左上到右下的對(duì)角線編號(hào)int GetP(int row, int col);/給定二維矩陣的一個(gè)點(diǎn)坐標(biāo)，返回其對(duì)應(yīng)的右上到左下的對(duì)角線編號(hào)int GetC(int

23、 row, int col);/返回begin, begin + 1, . , end - 1 這end - begin個(gè)數(shù)中的隨機(jī)的一個(gè)int My_rand(int begin, int end);/左閉右開begin, end)/原地shuffle算法，算法導(dǎo)論中的randomize in place算法void Randomize(int a, int begin, int end);/ 左閉右開/初始化皇后的擺放，同時(shí)初始化row,col,pdiag,cdiag數(shù)組void Init();/用最小沖突算法調(diào)整第row行的皇后的位置（初始化時(shí)每行都有一個(gè)皇后，調(diào)整后仍然在第row行）/

24、調(diào)整過(guò)后check一下看看是否已經(jīng)沒(méi)有沖突，如果沒(méi)有沖突（達(dá)到終止?fàn)顟B(tài)），返回truebool Adjust_row(int row);bool Qualify();void Print_result();/最終用戶調(diào)用函數(shù) PrintChessBoard判斷是否輸出棋盤表示int CSPAlgorithms(bool PrintChessBord);/CSPAlgorithms.cpp#include"CSPAlgorithms.h"#include <cstdio>#include <cstdlib>#include <ctime>#

25、include<iostream>using namespace std;CSP_Queens:CSP_Queens(int numOfQueens)srand(unsigned)time(NULL);N = numOfQueens;row = new intN;col = new intN;pdiag=new int2 * N;cdiag=new int2 * N;R=new intN;CSP_Queens:CSP_Queens()if (NULL != row)deleterow;if (NULL != col)deletecol;if (NULL != pdiag)delet

26、epdiag;if (NULL != cdiag)deletecdiag;if (NULL != R)deleteR;int CSP_Queens:swap(int &a, int &b)int t = a; a = b; b = t;return 0;/int CSP_Queens:GetP(int row, int col)return row - col + N - 1;int CSP_Queens:GetC(int row, int col)return row + col;/返回begin, begin + 1, . , end - 1 這end - begin個(gè)數(shù)中

27、的隨機(jī)的一個(gè)int CSP_Queens:My_rand(int begin, int end)/左閉右開begin, end)return rand() % (end - begin) + begin;/原地shuffle算法，算法導(dǎo)論中的randomize in place算法void CSP_Queens:Randomize(int a, int begin, int end)/ 左閉右開for (int i = begin; i <= end - 2; i+)int x = My_rand(i, end);swap(ai, ax);/初始化皇后的擺放，同時(shí)初始化row,col,p

28、diag,cdiag數(shù)組void CSP_Queens:Init()for (int i = 0; i < N; i+)/首先全部安放在主對(duì)角線上Ri = i;/下面隨機(jī)抽取調(diào)換兩行皇后位置Randomize(R, 0, N);/初始化N個(gè)皇后對(duì)應(yīng)的R數(shù)組為0N-1的一個(gè)排列，/此時(shí) 即沒(méi)有任意皇后同列，也沒(méi)有任何皇后同行for (int i = 0; i < N; i+)rowi = 1;/每行恰好一個(gè)皇后coli = 0;for (int i = 0; i < 2 * N - 1; i+)pdiagi = 0;cdiagi = 0;/初始化當(dāng)前棋局的皇后所在位置的各個(gè)沖突

29、數(shù)for (int i = 0; i < N; i+)colRi+;pdiagGetP(i, Ri)+;cdiagGetC(i, Ri)+;/用最小沖突算法調(diào)整第row行的皇后的位置（初始化時(shí)每行都有一個(gè)皇后，調(diào)整后仍然在第row行）/調(diào)整過(guò)后check一下看看是否已經(jīng)沒(méi)有沖突，如果沒(méi)有沖突（達(dá)到終止?fàn)顟B(tài)），返回truebool CSP_Queens:Adjust_row(int row)int cur_col = Rrow;int optimal_col = cur_col;/最佳列號(hào)，設(shè)置為當(dāng)前列，然后更新int min_conflict = coloptimal_col + pdi

30、agGetP(row, optimal_col) - 1+ cdiagGetC(row, optimal_col) - 1;/對(duì)角線沖突數(shù)為當(dāng)前對(duì)角線皇后數(shù)減一for (int i = 0; i < N; i+) /逐個(gè)檢查第row行的每個(gè)位置if (i = cur_col) continue;int conflict = coli + pdiagGetP(row, i) + cdiagGetC(row, i);if (conflict < min_conflict) min_conflict = conflict;optimal_col = i;if (optimal_col !

31、= cur_col) /要更新col,pdiag,cdiagcolcur_col-;pdiagGetP(row, cur_col)-;cdiagGetC(row, cur_col)-;coloptimal_col+;pdiagGetP(row, optimal_col)+;cdiagGetC(row, optimal_col)+;Rrow = optimal_col;if (colcur_col = 1 && coloptimal_col = 1&& pdiagGetP(row, optimal_col) = 1 && cdiagGetC(row

32、, optimal_col) = 1) return Qualify();/qualify相對(duì)更耗時(shí)，所以只在滿足上面基本條件后才檢查/當(dāng)前點(diǎn)就是最佳點(diǎn)，一切都保持不變r(jià)eturn false;/如果都沒(méi)變的話，肯定不滿足終止條件，否則上一次就應(yīng)該返回true并終止了/檢查沖突bool CSP_Queens:Qualify()for (int i = 0; i < N; i+)if (colRi != 1 |pdiagGetP(i, Ri) != 1 |cdiagGetC(i, Ri) != 1) return false;return true;void CSP_Queens:Print_result()cout << "-結(jié)果為:" << endl;cout << endl;for (int j = 0; j &