人工智能課程設(shè)計分析報告

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

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

3、為近三十年來它獲得了迅速的進展，在專門多學(xué)科領(lǐng)域都獲得了廣泛應(yīng)用，并取得了豐碩的成果，人工智能已逐步成為一個獨立的分支，不管在理論和實踐上都已自成一個系統(tǒng)。人工智能是研究使計算機來模擬人的某些思維過程和智能行為（如學(xué)習(xí)、推理、考慮、規(guī)劃等）的學(xué)科，要緊包括計算機實現(xiàn)智能的原理、制造類似于人腦智能的計算機，使計算機能實現(xiàn)更高層次的應(yīng)用。人工智能將涉及到計算機科學(xué)、心理學(xué)、哲學(xué)和語言學(xué)等學(xué)科。能夠講幾乎是自然科學(xué)和社會科學(xué)的所有學(xué)科，其范圍已遠遠超出了計算機科學(xué)的范疇，人工智能與思維科學(xué)的關(guān)系是實踐和理論的關(guān)系，人工智能是處于思維科學(xué)的技術(shù)應(yīng)用層次，是它的一個應(yīng)用分支。從思維觀點看，人工智能不僅限

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

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

6、上還沒有皇后；b bi=0表示第i列反斜線/上沒有皇后；c ci=0表示第i列正斜線上沒有皇后。棋盤中同一反斜線/上的方格的行號與列號相同；同一正斜線上的方格的行號與列號之差均相同，這確實是推斷斜線的依據(jù)。初始時，所有行和斜線上都沒有皇后，從第1列的第1行配置第一個皇后開始，在第m列，colm行放置了一個合理的皇后，預(yù)備考察第m+1列時，在數(shù)組a，b和c中為第m列，colm行的位置設(shè)定有皇后的標志；當從第m列回溯到m-1列時，并預(yù)備調(diào)整第m-1列的皇后配置時，清除在數(shù)組a,b和c對應(yīng)位置的值都為1來確定。 2)遺傳算法遺傳算法的差不多運算過程如下：a)初始化：設(shè)置進化代數(shù)計數(shù)器t=0，設(shè)置最大

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

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

9、ime )PrintChessBoard();/輸出棋局count+;return;for (int i = 0; in; i+)/有沖突if (veri = 1|rui - t + n = 1|rdi + t = 1) continue;/沒有沖突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:PrintChessBoard(bool PrintChes

10、sBoard)bool DisplayAllAnsures=PrintChessBoard;/是否輸出所有棋盤結(jié)果int g = 0, num = 0;InitialPopulation();while (g = 0 & num Iteration)num+;g = 0;for (int k = 0; k Population ; k+)this-FillArea(k);this-CostMatrixk = this-CostFunc(k);this-PopulationSort();if (this-CostMatrix0 = 0)/差不多完成計算g = 1;if (DisplayAllAn

11、sures)PrintTheBestAnsure();/*for (i = 0; i = ChessBoradLenght - 1; i+)cout row: i col: ChromosomeMatrixi0 endl;cout GenerateCrossOverMatrix();this-Mating();this-ApplyMutation();cout 實際迭代： num 次 endl;if (DisplayAllAnsures)cout 最佳答案為： PrintTheBestAnsure();3）CSP最小沖突算法/用最小沖突算法調(diào)整第row行的皇后的位置（初始化時每行都有一個皇后，

12、調(diào)整后仍然在第row行）/調(diào)整過后check一下看看是否差不多沒有沖突，假如沒有沖突（達到終止狀態(tài)），返回truebool CSP_Queens:Adjust_row(int row)int cur_col = Rrow;int optimal_col = cur_col;/最佳列號，設(shè)置為當前列，然后更新/計算總沖突數(shù)int min_conflict = coloptimal_col + pdiagGetP(row, optimal_col) - 1+ cdiagGetC(row, optimal_col) - 1;/對角線沖突數(shù)為當前對角線皇后數(shù)減一,三次重疊了/逐個檢查第row行的每個位

13、置，看看是否存在沖突數(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_col

14、)-;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相對更耗時，因此只在滿足上面差不多條件后才檢查/否則當前點確實是最佳點，一切都保持不變ret

15、urn false;/假如都沒變的話，確信不滿足終止條件，否則上一次就應(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:CSPAlgorithms(bool PrintChessBord)srand(unsi

16、gned)time(NULL);Init();if (Qualify() /運氣專門好，初始化后就滿足終止條件if (PrintChessBord)Print_result();return 0;bool end = false;while (!end) for (int i = 0; i 100)時，前兩者都不能再解決，現(xiàn)在，CSP最小沖突法的效率最高，且與n值沒有必定的聯(lián)系?？偨Y(jié) 通過此次課程實習(xí)不僅大大加深了我對幾種經(jīng)典搜索算法的理解，而且關(guān)心我專門好的復(fù)習(xí)了隊列、堆棧、圖、文件讀寫這幾部分的內(nèi)容，使我對幾種差不多的數(shù)據(jù)結(jié)構(gòu)類型的運用更加熟練。在解決這些問題的過程中我不但專門好的鞏固了數(shù)

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

18、s();private:/rowi表示當前擺放方式下第i行的皇后數(shù)，int *row;/coli表示當前擺放方式下第i列的皇后沖突數(shù)int *col;int N; /放置N個皇后在N*N棋盤上/從左上到右下的對角線上row-col值是相同的，然而那個值有可能是負值，最小為-(N-1)，/因此能夠做個偏移，統(tǒng)一加上N-1，如此那個值就在0,2*N-2范圍內(nèi)，將那個值作為該對角線的編號/pdiagi表示當前擺放方式下編號為i的對角線上的皇后數(shù)int *pdiag;/principal diagonal,主對角線，左上到右下（表示和主對角線平行的2N-1條對角線）/從右上到左下的對角線row+col

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

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

21、差不多沒有沖突，假如沒有沖突（達到終止狀態(tài)），返回truebool Adjust_row(int row);bool Qualify();void Print_result();/最終用戶調(diào)用函數(shù) PrintChessBoard推斷是否輸出棋盤表示int CSPAlgorithms(bool PrintChessBord);/CSPAlgorithms.cpp#includeCSPAlgorithms.h#include #include #include #includeusing namespace std;CSP_Queens:CSP_Queens(int numOfQueens)sra

22、nd(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)deletepdiag;if (NULL != cdiag)deletecdiag;if (NULL != R)deleteR;int CSP_Queens:swap(int &

23、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個數(shù)中的隨機的一個int CSP_Queens:My_rand(int begin, int end)/左閉右開begin, end)return rand() % (end - begin

24、) + 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);/初始化皇后的擺放，同時初始化row,col,pdiag,cdiag數(shù)組void CSP_Queens:Init()for (int i = 0; i N; i+)/首先全部安放在主對角線上Ri = i;/下面隨機抽取調(diào)換兩行皇后位置Ran

25、domize(R, 0, N);/初始化N個皇后對應(yīng)的R數(shù)組為0N-1的一個排列，/現(xiàn)在 即沒有任意皇后同列，也沒有任何皇后同行for (int i = 0; i N; i+)rowi = 1;/每行恰好一個皇后coli = 0;for (int i = 0; i 2 * N - 1; i+)pdiagi = 0;cdiagi = 0;/初始化當前棋局的皇后所在位置的各個沖突數(shù)for (int i = 0; i N; i+)colRi+;pdiagGetP(i, Ri)+;cdiagGetC(i, Ri)+;/用最小沖突算法調(diào)整第row行的皇后的位置（初始化時每行都有一個皇后，調(diào)整后仍然在第r

26、ow行）/調(diào)整過后check一下看看是否差不多沒有沖突，假如沒有沖突（達到終止狀態(tài)），返回truebool CSP_Queens:Adjust_row(int row)int cur_col = Rrow;int optimal_col = cur_col;/最佳列號，設(shè)置為當前列，然后更新int min_conflict = coloptimal_col + pdiagGetP(row, optimal_col) - 1+ cdiagGetC(row, optimal_col) - 1;/對角線沖突數(shù)為當前對角線皇后數(shù)減一for (int i = 0; i N; i+) /逐個檢查第row行

27、的每個位置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 != 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, optimal_col) = 1) return Qualify();/qualify相對更耗時，因此只在滿足上面差不多條件后才檢查/當前點確實是最佳點，一切都保持不變return false;/假如都沒變的話，確信不滿足終止條件，否則上一次就應(yīng)該返回true并終止了/檢查沖