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

1、人工智能課程設(shè)計報告 課 程:人工智能能課程設(shè)計計報告 班 級: 姓 名: 學 號: 指導教師:趙曼 2015年年11月 - 24 -人工智能課課程設(shè)計報報告課程背景 人工智能（AArtifficiaal Inntellligennce），英英文縮寫為為AI。它它是研究、開發(fā)用于于模擬、延延伸和擴展展人的智能能的理論、方法、技技術(shù)及應用用系統(tǒng)的一一門新的技技術(shù)科學。 人工智智能是計算算機科學的的一個分支支，它企圖圖了解智能能的實質(zhì)，并并生產(chǎn)出一一種新的能能以人類智智能相似的的方式做出出反應的智智能機器，該該領(lǐng)域的研研究包括機機器人、語語言識別、圖像識別別、自然語語言處理和和專家系統(tǒng)統(tǒng)等。人工工

2、智能從誕誕生以來，理理論和技術(shù)術(shù)日益成熟熟，應用領(lǐng)領(lǐng)域也不斷斷擴大，可可以設(shè)想，未未來人工智智能帶來的的科技產(chǎn)品品，將會是是人類智慧慧的“容器”。人工智能是是對人的意意識、思維維的信息過過程的模擬擬。人工智智能不是人人的智能，但但能像人那那樣思考、也可能超超過人的智智能。人工智能是是一門極富富挑戰(zhàn)性的的科學，從從事這項工工作的人必必須懂得計計算機知識識，心理學學和哲學。人工智能能是包括十十分廣泛的的科學，它它由不同的的領(lǐng)域組成成，如機器器學習，計計算機視覺覺等等，總總的說來，人人工智能研研究的一個個主要目標標是使機器器能夠勝任任一些通常常需要人類類智能才能能完成的復復雜工作。但不同的的時代、不

3、不同的人對對這種“復雜工作作”的理解是是不同的。人工智能是是計算機學學科的一個個分支，二二十世紀七七十年代以以來被稱為為世界三大大尖端技術(shù)術(shù)之一（空空間技術(shù)、能源技術(shù)術(shù)、人工智智能）。也也被認為是是二十一世世紀三大尖尖端技術(shù)（基基因工程、納米科學學、人工智智能）之一一。這是因因為近三十十年來它獲獲得了迅速速的發(fā)展，在在很多學科科領(lǐng)域都獲獲得了廣泛泛應用，并并取得了豐豐碩的成果果，人工智智能已逐步步成為一個個獨立的分分支，無論論在理論和和實踐上都都已自成一一個系統(tǒng)。人工智能是是研究使計計算機來模模擬人的某某些思維過過程和智能能行為（如如學習、推推理、思考考、規(guī)劃等等）的學科科，主要包包括計算機機

4、實現(xiàn)智能能的原理、制造類似似于人腦智智能的計算算機，使計計算機能實實現(xiàn)更高層層次的應用用。人工智智能將涉及及到計算機機科學、心心理學、哲哲學和語言言學等學科科?？梢哉f說幾乎是自自然科學和和社會科學學的所有學學科，其范范圍已遠遠遠超出了計計算機科學學的范疇，人人工智能與與思維科學學的關(guān)系是是實踐和理理論的關(guān)系系，人工智智能是處于于思維科學學的技術(shù)應應用層次，是是它的一個個應用分支支。從思維維觀點看，人人工智能不不僅限于邏邏輯思維，要要考慮形象象思維、靈靈感思維才才能促進人人工智能的的突破性的的發(fā)展，數(shù)數(shù)學常被認認為是多種種學科的基基礎(chǔ)科學，數(shù)數(shù)學也進入入語言、思思維領(lǐng)域，人人工智能學學科也必須須

5、借用數(shù)學學工具，數(shù)數(shù)學不僅在在標準邏輯輯、模糊數(shù)數(shù)學等范圍圍發(fā)揮作用用，數(shù)學進進入人工智智能學科，它它們將互相相促進而更更快地發(fā)展展。題目二：nn皇后問題題一.問題描描述分別用回溯溯法（遞歸歸）、GAA算法和CSP的的最小沖突突法求解nn皇后問題題。即如何能夠夠在 nn 的國際際象棋棋盤盤上放置nn個皇后，使使得任何一一個皇后都都無法直接接吃掉其他他的皇后？為了達到到此目的，任任兩個皇后后都不能處處于同一條條橫行、縱縱行或斜線線上。要求：. 輸入入n，并用用運行時間間比較幾種種算法在相相同規(guī)模的的問題時的的求解效率率，并列表表給出結(jié)果果。. 比較較同一算法法在n不相相同時的運運行時間，分分析算

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

7、入三個整整型數(shù)組來來表示當前前列在三個個方向上的的狀態(tài) ：a aai=0表示第第i行上還還沒有皇后后；b bbi=0表示第第i列反斜斜線/上沒沒有皇后；c cci=0表示第第i列正斜斜線上沒沒有皇后。棋盤中同一一反斜線/上的方格格的行號與與列號相同同；同一正正斜線上上的方格的的行號與列列號之差均均相同，這這就是判斷斷斜線的依依據(jù)。初始時，所所有行和斜斜線上都沒沒有皇后，從從第1列的的第1行配配置第一個個皇后開始始，在第mm列，coolm行放置了了一個合理理的皇后，準準備考察第第m+1列列時，在數(shù)數(shù)組a，b和c中為第mm列，coolm行的位置置設(shè)定有皇皇后的標志志；當從第第m列回溯溯到m-11列

8、時，并并準備調(diào)整整第m-11列的皇后后配置時，清清除在數(shù)組組a,b和和c對對應位置的的值都為11來確定。 2)遺遺傳算法遺傳算法的的基本運算算過程如下下：a)初始化化：設(shè)置進進化代數(shù)計計數(shù)器t=0，設(shè)置置最大進化化代數(shù)T，隨隨機生成MM個個體作作為初始群群體P(00)。b)個體評評價：計算算群體P(t)中各各個個體的的適應度。遺傳算法遺傳算法c)選擇運運算:將選選擇算子作作用于群體體。選擇的的目的是把把優(yōu)化的個個體直接遺遺傳到下一一代或通過過配對交叉叉產(chǎn)生新的的個體再遺遺傳到下一一代。選擇擇操作是建建立在群體體中個體的的適應度評評估基礎(chǔ)上上的。d)交叉運運算：將交交叉算子作作用于群體體。遺傳算

9、算法中起核核心作用的的就是交叉叉算子。e)變異運運算：將變變異算子作作用于群體體。即是對對群體中的的個體串的的某些基因因座上的基基因值作變變動。群體P(tt)經(jīng)過選選擇、交叉叉、變異運運算之后得得到下一代代群體P(t+1)。f)終止條條件判斷:若t=TT,則以進進化過程中中所得到的的具有最大大適應度個個體作為最最優(yōu)解輸出出，終止計計算。3）cspp最小沖突突法（1）初始始化N個皇皇后的一個個放置，允允許有沖突突（2）考慮慮某一行的的某個皇后后，她可能能與x個皇皇后沖突，然然后看看將將這個皇后后移動到這這一行的哪哪個空位能能使得與其其沖突的皇皇后個數(shù)最最少，就移移動到那里里。（也可可以考慮列列，

10、是等價價的）（3）不斷斷執(zhí)行（22），直到到?jīng)]有沖突突為止2.數(shù)據(jù)結(jié)結(jié)構(gòu)使用數(shù)組結(jié)結(jié)構(gòu)存儲相相關(guān)數(shù)據(jù)一維數(shù)組：二維數(shù)組：3.算法設(shè)設(shè)計1）/回回溯搜索 void Funcctionn1:DDFS(iint t,booll isShhowTiime)if (t = n)/說明已經(jīng)經(jīng)排了n行行了（從00開始的），即即排列結(jié)束束了forr (intt i = 0; in; i+)reeci = bboarddi;if (! iisShoowTimme )PPrinttChesssBoaard();/輸輸出棋局couunt+;retturn;for (intt i = 0; in; i+)/有有沖突i

11、f (verri = 11|ruui - t + nn = 1|rdii + tt = 1) conttinuee;/沒沒有沖突verri = 1;rui - t + nn = 1;rdi + t = 1;boaardtt = i;DFSS(t + 11, issShowwTimee);/深深搜遞歸/后后退處理rdi + t = 0;rui - t + nn = 0;verri = 0;retuurn;2）遺傳算算法void CGAQQueenn:PrrintCChesssBoarrd(boool PrinntCheessBooard)booll DissplayyAllAAnsurres=P

12、PrinttChesssBoaard;/是否否輸出所有有棋盤結(jié)果果int g = 0, num = 0;InittialPPopullatioon();whille (gg = 0 & numm Iteeratiion)numm+;g = 0;forr (intt k = 0; k Poopulaationn ; kk+)thhis-FilllAreaa(k);thhis-CCostMMatriixk = tthis-CosstFunnc(k);thiis-PPopullatioonSorrt();if (thiis-CCostMMatriix0 = 0)/已經(jīng)完成成計算g = 1;if (D

13、issplayyAllAAnsurres)PrrintTTheBeestAnnsuree();/*for (i = 0; i = CheessBooradLLenghht - 1; ii+)ccout row: i col: CChrommosommeMattrixi00 enddl;coout GGenerrateCCrosssOverrMatrrix();thiis-MMatinng();thiis-AApplyyMutaationn();coutt 實際迭迭代： nnum 次次 endll;if (DispplayAAllAnnsurees)couut 最佳佳答案為： PPrinttTh

14、eBBestAAnsurre();3）CSPP最小沖突突算法/用最小小沖突算法法調(diào)整第rrow行的的皇后的位位置（初始始化時每行行都有一個個皇后，調(diào)調(diào)整后仍然然在第roow行）/調(diào)整過過后cheeck一下下看看是否否已經(jīng)沒有有沖突，如如果沒有沖沖突（達到到終止狀態(tài)態(tài)），返回回trueebool CSP_Queeens:Adjuust_rrow(iint row)int cur_col = Rrow;int optiimal_col = cuur_cool;/最佳列號號，設(shè)置為為當前列，然然后更新/計算算總沖突數(shù)數(shù)int min_confflictt = ccolooptimmal_ccol +

15、 pddiagGetPP(roww, opptimaal_cool) - 1+ ccdiaggGettC(roow, ooptimmal_ccol) - 11;/對對角線沖突突數(shù)為當前前對角線皇皇后數(shù)減一一,三次重重疊了/逐個個檢查第rrow行的的每個位置置，看看是是否存在沖沖突數(shù)更小小的位置for (intt i = 0; i N; ii+) if (i = cuur_cool) ccontiinue;intt connflicct = coli + pdiiagGGetP(row, i) + cddiagGetCC(roww, i);if (connflicct min_confflict

16、t) miin_coonfliict = connflicct;opptimaal_cool = i;/如果果最佳列位位置改變，則則皇后移向向新的最小小沖突位置置，要更新新col,pdiaag,cddiag，if (optiimal_col != ccur_ccol) collcurr_coll-;pdiiagGGetP(row, cuur_cool);cdiiagGGetC(row, cur_col)-;collopttimall_coll+;pdiiagGGetP(row, optiimal_col)+;cdiiagGGetC(row, optiimal_col)+;Rrrow = opp

17、timaal_cool;if (collcurr_coll = 1 & coolopptimaal_cool = 1& pdiiagGGetP(row, optiimal_col) = 1 & cddiagGetCC(roww, opptimaal_cool) = 11) reeturnn Quaalifyy();/quaalifyy相對更耗耗時，所以以只在滿足足上面基本本條件后才才檢查/否則則當前點就就是最佳點點，一切都都保持不變變retuurn falsse;/如果果都沒變的的話，肯定定不滿足終終止條件，否否則上一次次就應該返返回truue并終止止了/檢查沖沖突bool CSP_Queee

18、ns:Quallify()for (intt i = 0; i N; ii+)if (collRii != 1 |pddiagGetPP(i, Ri) != 1 |cddiagGetCC(i, Ri) != 1) reeturnn falsse;retuurn truee;/最終用用戶調(diào)用函函數(shù)，nuumOfQQueenns為輸入入皇后數(shù)，PPrinttChesssBoaard判斷斷是否輸出出棋盤表示示int CCSP_QQueenns:CCSPAllgoriithmss(boool PrinntCheessBoord)srannd(uunsiggned)timee(NULLL);Initt(

19、);if (Quallify() /運氣氣很好，初初始化后就就滿足終止止條件if (PriintChhessBBord)Prinnt_reesultt();retturn 0;booll endd = ffalsee;whille (!end) forr (intt i = 0; i 1000)時，前前兩者都不不能再解決決，此時，CCSP最小小沖突法的的效率最高高，且與nn值沒有必必然的聯(lián)系系。總結(jié) 通通過此次課課程實習不不僅大大加加深了我對對幾種經(jīng)典典搜索算法法的理解，而而且?guī)椭椅液芎玫膹蛷土暳岁犃辛小⒍褩?、圖、文件件讀寫這幾幾部分的內(nèi)內(nèi)容，使我我對幾種基基本的數(shù)據(jù)據(jù)結(jié)構(gòu)類型型的運用更更加

20、熟練。在解決這這些問題的的過程中我我不但很好好的鞏固了了數(shù)據(jù)結(jié)構(gòu)構(gòu)的相關(guān)知知識，而且且提高了編編程及程序序調(diào)試能力力，增強了了自己編程程的信心。 總之之，在這次次課程實習習過程中我我是實實在在在學到了了一些課堂堂上學不到到的東西，同同時也提高高了實踐能能力。同時時在這個過過程中也暴暴露了自己己的不少問問題，在今今后的學習習過程成也也會更加有有針對性。最后還要要感謝老師師的悉心指指導，解答答我編程過過程中的疑疑問、指出出我程序中中的不足，及及提出可行行的解決方方法，讓我我的程序的的功能更加加完善。CSP算法法源代碼：/CSPPAlgoorithhms.hh#praggma onceeclasss

21、 CSP_Queeenspubliic:/構(gòu)造造函數(shù)，nnumOffQueeens為輸輸入皇后數(shù)數(shù)，CSP_Queeens(iint nnumOffQueeens);CSPP_Queeens();privaate:/roowi表示當前前擺放方式式下第i行行的皇后數(shù)數(shù)，int *roww;/cooli表示當前前擺放方式式下第i列列的皇后沖沖突數(shù)int *coll;int N; /放置NN個皇后在在N*N棋棋盤上/從左左上到右下下的對角線線上roww-coll值是相同同的，但是是這個值有有可能是負負值，最小小為-(NN-1)，/所以以可以做個個偏移，統(tǒng)統(tǒng)一加上NN-1，這這樣這個值值就在00,2*

22、NN-2范范圍內(nèi)，將將這個值作作為該對角角線的編號號/pddiagi表示示當前擺放放方式下編編號為i的的對角線上上的皇后數(shù)數(shù)int *pdiiag;/priincippal ddiagoonal,主對角線線，左上到到右下（表表示和主對對角線平行行的2N-1條對角角線）/從右右上到左下下的對角線線row+col的的值相同，取取值范圍為為0, 2 * N - 2，22*N-11條，作為為對角線編編號/cddiagi表示示編號為ii的對角線線上的皇后后數(shù)int *cdiiag;/couunterr diaagonaal,副對對角線/R用來存存儲皇后放放置位置，RRroww = col表表示(roow

23、,cool)處,即“第rrow行第第col列列”有個皇皇后int *R;publiic:int swapp(intt &a, intt &b);/給定定二維矩陣陣的一個點點坐標，返返回其對應應的左上到到右下的對對角線編號號int GetPP(intt roww, innt cool);/給定定二維矩陣陣的一個點點坐標，返返回其對應應的右上到到左下的對對角線編號號int GetCC(intt roww, innt cool);/返回回begiin, bbeginn + 11, , end - 1 這endd - bbeginn個數(shù)中的的隨機的一一個int My_rrand(int bbeginn

24、, innt ennd);/左閉右右開beegin, endd)/原地地shufffle算算法，算法法導論中的的randdomizze inn plaace算法法voidd Ranndomiize(iint aa, int bbeginn, innt ennd);/ 左閉閉右開/初初始化皇后后的擺放，同同時初始化化row,col,pdiaag,cddiag數(shù)數(shù)組voidd Iniit();/用最最小沖突算算法調(diào)整第第row行行的皇后的的位置（初初始化時每每行都有一一個皇后，調(diào)調(diào)整后仍然然在第roow行）/調(diào)整整過后chheck一一下看看是是否已經(jīng)沒沒有沖突，如如果沒有沖沖突（達到到終止狀態(tài)態(tài)）

25、，返回回trueebooll Adjjust_row(int rrow);booll Quaalifyy();voidd Priint_rresullt();/最終終用戶調(diào)用用函數(shù) PPrinttChesssBoaard判斷斷是否輸出出棋盤表示示int CSPAAlgorrithmms(boool PPrinttChesssBorrd);/CSPPAlgoorithhms.ccpp#inclludeCSPAAlgorrithmms.h#incllude #incllude #incllude #inclludeusingg nameespacce sttd;CSP_QQueenns:CCSP_

26、QQueenns(innt numOOfQueeens)srannd(uunsiggned)timee(NULLL);N = numOOfQueeens;row = neew intNN;col = neew intNN;pdiaag=neew int22 * NN;cdiaag=neew int22 * NN;R=neew intNN;CSP_QQueenns:CSP_Queeens()if (NULLL != row)deleeterow;if (NULLL != col)deleetecol;if (NULLL != pdiaag)deeleteepddiag;if (NULLL !=

27、cdiaag)deeleteecddiag;if (NULLL != R)deeleteeR;int CCSP_QQueenns:sswap(int &a, intt &b)int t = a; a = b; b = tt;retuurn 00;/int CCSP_QQueenns:GGetP(int row, int col)retuurn row - coll + NN - 11;int CCSP_QQueenns:GGetC(int row, int col)retuurn row + coll;/返回bbeginn, beegin + 1, , eend - 1 這這end - bee

28、gin個個數(shù)中的隨隨機的一個個int CCSP_QQueenns:MMy_raand(iint begiin, intt end)/左閉閉右開bbeginn, ennd)retuurn rrand() % (endd - beegin) + bbeginn;/原地sshufffle算法法，算法導導論中的rrandoomizee in placce算法void CSP_Queeens:Randdomizze(innt a, int begiin, intt end)/ 左左閉右開for (intt i = beggin; i = endd - 22; i+)intt x = My_randd(i

29、, end);swaap(ai, ax);/初始化化皇后的擺擺放，同時時初始化rrow,ccol,ppdiagg,cdiiag數(shù)組組void CSP_Queeens:Initt()for (intt i = 0; i N; ii+)/首先先全部安放放在主對角角線上Rii = i;/下面面隨機抽取取調(diào)換兩行行皇后位置置Randdomizze(R, 0, N);/初始化化N個皇后后對應的RR數(shù)組為00N-11的一個排排列，/此時時 即沒有有任意皇后后同列，也也沒有任何何皇后同行行for (intt i = 0; i N; ii+)rowwi = 1;/每行行恰好一個個皇后colli = 0;for

30、 (intt i = 0; i 2 * N - 1; ii+)pdiiagii = 0;cdiiagii = 0;/初始始化當前棋棋局的皇后后所在位置置的各個沖沖突數(shù)for (intt i = 0; i N; ii+)collRii+;pdiiagGGetP(i, RRi)+;cdiiagGGetC(i, RRi)+;/用最小小沖突算法法調(diào)整第rrow行的的皇后的位位置（初始始化時每行行都有一個個皇后，調(diào)調(diào)整后仍然然在第roow行）/調(diào)整過過后cheeck一下下看看是否否已經(jīng)沒有有沖突，如如果沒有沖沖突（達到到終止狀態(tài)態(tài)），返回回trueebool CSP_Queeens:Adjuust_rr

31、ow(iint row)int cur_col = Rrow;int optiimal_col = cuur_cool;/最佳列號號，設(shè)置為為當前列，然然后更新int min_confflictt = ccolooptimmal_ccol + pddiagGetPP(roww, opptimaal_cool) - 1+ ccdiaggGettC(roow, ooptimmal_ccol) - 11;/對對角線沖突突數(shù)為當前前對角線皇皇后數(shù)減一一for (intt i = 0; i N; ii+) /逐逐個檢查第第row行行的每個位位置if (i = cuur_cool) coontinnue;

32、intt connflicct = coli + pdiiagGGetP(row, i) + cddiagGetCC(roww, i);if (connflicct min_confflictt) miin_coonfliict = connflicct;opptimaal_cool = i;if (optiimal_col != ccur_ccol) /要要更新cool,pddiag,cdiaagcollcurr_coll-;pdiiagGGetP(row, cur_col)-;cdiiagGGetC(row, cur_col)-;collopttimall_coll+;pdiiagGGet

33、P(row, optiimal_col)+;cdiiagGGetC(row, optiimal_col)+;Rrrow = opptimaal_cool;if (collcurr_coll = 1 & coolopptimaal_cool = 1& pdiiagGGetP(row, optiimal_col) = 1 & cddiagGetCC(roww, opptimaal_cool) = 11) reeturnn Quaalifyy();/quaalifyy相對更耗耗時，所以以只在滿足足上面基本本條件后才才檢查/當前前點就是最最佳點，一一切都保持持不變retuurn falsse;/如果果都沒變的的話，肯定定不滿足終終止條件，否