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

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

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

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

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

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

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

8、算。3）csp最小沖突法（1）初始化N個皇后的一個放置，同意有沖突（2）考慮某一行的某個皇后，她可能與x個皇后沖突，然后看看將那個皇后移動到這一行的哪個空位能使得與其沖突的皇后個數最少，就移動到那兒。（也能夠考慮列，是等價的）（3）不斷執行（2），直到沒有沖突為止2.數據結構使用數組結構存儲相關數據一維數組：二維數組：3.算法設計1）/回溯搜索 void Function1:DFS(int t,bool isShowTime)if (t = n)/講明差不多排了n行了（從0開始的），即排列結束了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;/是否輸出所有棋盤結果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最小沖突算法/用最小沖突算法調整第row行的皇后的位置（初始化時每行都有一個皇后，

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

13、置，看看是否存在沖突數更小的位置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;/假如都沒變的話，確信不滿足終止條件，否則上一次就應該返回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;/最終用戶調用函數，numOfQueens為輸入皇后數，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)時，前兩者都不能再解決，現在，CSP最小沖突法的效率最高，且與n值沒有必定的聯系。總結 通過此次課程實習不僅大大加深了我對幾種經典搜索算法的理解，而且關心我專門好的復習了隊列、堆棧、圖、文件讀寫這幾部分的內容，使我對幾種差不多的數據結構類型的運用更加熟練。在解決這些問題的過程中我不但專門好的鞏固了數

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

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

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

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

21、差不多沒有沖突，假如沒有沖突（達到終止狀態），返回truebool Adjust_row(int row);bool Qualify();void Print_result();/最終用戶調用函數 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個數中的隨機的一個int CSP_Queens:My_rand(int begin, int end)/左閉右開begin, end)return rand() % (end - begin

24、) + begin;/原地shuffle算法，算法導論中的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數組void CSP_Queens:Init()for (int i = 0; i N; i+)/首先全部安放在主對角線上Ri = i;/下面隨機抽取調換兩行皇后位置Ran

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

26、ow行）/調整過后check一下看看是否差不多沒有沖突，假如沒有沖突（達到終止狀態），返回truebool CSP_Queens:Adjust_row(int row)int cur_col = Rrow;int optimal_col = cur_col;/最佳列號，設置為當前列，然后更新int min_conflict = coloptimal_col + pdiagGetP(row, optimal_col) - 1+ cdiagGetC(row, optimal_col) - 1;/對角線沖突數為當前對角線皇后數減一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;/假如都沒變的話，確信不滿足終止條件，否則上一次就應該返回true并終止了/檢查沖