人工智能課程設(shè)計(jì)報(bào)告_第1頁(yè)
人工智能課程設(shè)計(jì)報(bào)告_第2頁(yè)
人工智能課程設(shè)計(jì)報(bào)告_第3頁(yè)
人工智能課程設(shè)計(jì)報(bào)告_第4頁(yè)
人工智能課程設(shè)計(jì)報(bào)告_第5頁(yè)
已閱讀5頁(yè),還剩21頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、 課 程:人工智能課程設(shè)計(jì)報(bào)告 班 級(jí):姓 名:學(xué) 號(hào):指導(dǎo)教師:曼 2015年11月- 25 - / 26人工智能課程設(shè)計(jì)報(bào)告課程背景人工智能(Artificial Intelligence),英文縮寫(xiě)為AI。它是研究、開(kāi)發(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ī)視覺(jué)等等,總的說(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é)科。可以說(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)題。即如何能夠在 nn 的國(guó)際象棋棋盤上放置n個(gè)皇后,使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后?為了達(dá)到此目的,任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。要求:. 輸入n,并用運(yùn)行時(shí)間比較幾種算法在一樣規(guī)模的問(wèn)題時(shí)的求解效率,并列表給出結(jié)果。. 比

5、較同一算法在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è)方向上的狀態(tài) :a ai=0表示第i行

6、上還沒(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è)皇后開(kāi)始,在第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)化代數(shù)計(jì)數(shù)器t=0,設(shè)置最大進(jìn)化

7、代數(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è)體作為最優(yōu)解輸出,終止計(jì)算。3

8、)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)/回溯搜索 voidFunction1:DFS(intt,boolisShowTime)if (t = n)/說(shuō)明已經(jīng)排了n行了(從0開(kāi)始的),即排列結(jié)束了for (int i = 0; in; i+)reci = boardi;if (! isShowTime )Pr

9、intChessBoard();/輸出棋局count+;return;for (int i = 0; in; 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)遺傳算法voidCGAQueen:PrintChessBoard(boolPrintChessBoard)bo

10、ol 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)/已經(jīng)完成計(jì)算g = 1;if (DisplayAllAnsures)Prin

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

12、行)/調(diào)整過(guò)后check一下看看是否已經(jīng)沒(méi)有沖突,如果沒(méi)有沖突(達(dá)到終止?fàn)顟B(tài)),返回trueboolCSP_Queens:Adjust_row(introw)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è)位置,看看是否存在沖突數(shù)更小

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)-;cdiagGetC(

14、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í),所以只在滿足上面基本條件后才檢查/否則當(dāng)前點(diǎn)就是最佳點(diǎn),一切都保持不變r(jià)eturnfalse;/如果都沒(méi)變

15、的話,肯定不滿足終止條件,否則上一次就應(yīng)該返回true并終止了/檢查沖突boolCSP_Queens:Qualify()for (int i = 0; i N; i+)if (colRi != 1 |pdiagGetP(i, Ri) != 1 |cdiagGetC(i, Ri) != 1) returnfalse;returntrue;/最終用戶調(diào)用函數(shù),numOfQueens為輸入皇后數(shù),PrintChessBoard判斷是否輸出棋盤表示intCSP_Queens:CSPAlgorithms(boolPrintChessBord)srand(unsigned)time(NULL);Init(

16、);if (Qualify() /運(yùn)氣很好,初始化后就滿足終止條件if (PrintChessBord)Print_result();return 0;bool end = false;while (!end) for (int i = 0; i 100)時(shí),前兩者都不能再解決,此時(shí),CSP最小沖突法的效率最高,且與n值沒(méi)有必然的聯(lián)系??偨Y(jié) 通過(guò)此次課程實(shí)習(xí)不僅大大加深了我對(duì)幾種經(jīng)典搜索算法的理解,而且?guī)椭液芎玫膹?fù)習(xí)了隊(duì)列、堆棧、圖、文件讀寫(xiě)這幾部分的容,使我對(duì)幾種基本的數(shù)據(jù)結(jié)構(gòu)類型的運(yùn)用更加熟練。在解決這些問(wèn)題的過(guò)程中我不但很好的鞏固了數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí),而且提高了編程與程序調(diào)試能力,增強(qiáng)

17、了自己編程的信心。總之,在這次課程實(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#pragmaonceclassCSP_Queenspublic:/構(gòu)造函數(shù),numOfQueens為輸入皇后數(shù),CSP_Queens(int numOfQueens);CSP_Queens();private:/rowi表示當(dāng)前擺放方式下第i行的

18、皇后數(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圍,將這個(gè)值作為該對(duì)角線的編號(hào)/pdiagi表示當(dāng)前擺放方式下編號(hào)為i的對(duì)角線上的皇后數(shù)int *pdiag;/principal diagonal,主對(duì)角線,左上到右下(表示和主對(duì)角線平行的2N-1條對(duì)角線)/從右上到左下的對(duì)角線row+col的值一樣,取值圍為0, 2 * N - 2,2*N-1條,作為對(duì)

19、角線編號(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 row, int col);/返回begin, begin + 1, . , end - 1

20、這end - begin個(gè)數(shù)中的隨機(jī)的一個(gè)int My_rand(int begin, int end);/左閉右開(kāi)begin, end)/原地shuffle算法,算法導(dǎo)論中的randomize in place算法void Randomize(int a, int begin, int end);/ 左閉右開(kāi)/初始化皇后的擺放,同時(shí)初始化row,col,pdiag,cdiag數(shù)組void Init();/用最小沖突算法調(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

21、Adjust_row(int row);bool Qualify();void Print_result();/最終用戶調(diào)用函數(shù) PrintChessBoard判斷是否輸出棋盤表示int CSPAlgorithms(bool PrintChessBord);/CSPAlgorithms.cpp#includeCSPAlgorithms.h#include#include#include#includeusingnamespace std;CSP_Queens:CSP_Queens(intnumOfQueens)srand(unsigned)time(NULL);N = numOfQueens;

22、row = newintN;col = newintN;pdiag=newint2 * N;cdiag=newint2 * N;R=newintN;CSP_Queens:CSP_Queens()if (NULL != row)deleterow;if (NULL != col)deletecol;if (NULL != pdiag)deletepdiag;if (NULL != cdiag)deletecdiag;if (NULL != R)deleteR;intCSP_Queens:swap(int &a, int &b)int t = a; a = b; b = t;return 0;/i

23、ntCSP_Queens:GetP(introw, intcol)returnrow - col + N - 1;intCSP_Queens:GetC(introw, intcol)returnrow + col;/返回begin, begin + 1, . , end - 1 這end - begin個(gè)數(shù)中的隨機(jī)的一個(gè)intCSP_Queens:My_rand(intbegin, intend)/左閉右開(kāi)begin, end)return rand() % (end - begin) + begin;/原地shuffle算法,算法導(dǎo)論中的randomize in place算法voidCSP

24、_Queens:Randomize(inta, intbegin, intend)/ 左閉右開(kāi)for (int i = begin; i = end - 2; i+)int x = My_rand(i, end);swap(ai, ax);/初始化皇后的擺放,同時(shí)初始化row,col,pdiag,cdiag數(shù)組voidCSP_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)有任何皇

25、后同行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è)沖突數(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)),返回trueboolCSP_Queen

26、s:Adjust_row(introw)int cur_col = Rrow;int optimal_col = cur_col;/最佳列號(hào),設(shè)置為當(dāng)前列,然后更新int min_conflict = coloptimal_col + pdiagGetP(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(r

27、ow, 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相對(duì)更耗時(shí),所以只在滿足上面基本條件后才檢查/當(dāng)前點(diǎn)就是最佳點(diǎn),一切都保持不變r(jià)eturnfalse;/如果都沒(méi)變的話,肯定不滿足終止條件,否則上一次就應(yīng)該返回true并終止了/

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論