人工智能课程设计报告41318.docx

《人工智能课程设计报告41318.docx》由会员分享，可在线阅读，更多相关《人工智能课程设计报告41318.docx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能课程设计报告 课课 程程:人工智能课课程设计报告告 班 级: 姓 名: 学 号: 指导教师:赵曼曼 2015年111月人工智能课程设设计报告课程背景 人工智能（Arrtificcial IIntellligencce），英文文缩写为AII。它是研究究、开发用于于模拟、延伸伸和扩展人的的智能的理论论、方法、技技术及应用系系统的一门新新的技术科学学。 人工智智能是计算机机科学的一个个分支，它企企图了解智能能的实质，并并生产出一种种新的能以人人类智能相似似的方式做出出反应的智能能机器，该领领域的研究包包括机器人、语语言识别、图图像识别、自自然语言处理理和专家系统统等。人工智智能从诞生以以来，

2、理论和和技术日益成成熟，应用领领域也不断扩扩大，可以设设想，未来人人工智能带来来的科技产品品，将会是人人类智慧的“容器”。人工智能是对人人的意识、思思维的信息过过程的模拟。人人工智能不是是人的智能，但但能像人那样样思考、也可可能超过人的的智能。人工智能是一门门极富挑战性性的科学，从从事这项工作作的人必须懂懂得计算机知知识，心理学学和哲学。人人工智能是包包括十分广泛泛的科学，它它由不同的领领域组成，如如机器学习，计计算机视觉等等等，总的说说来，人工智智能研究的一一个主要目标标是使机器能能够胜任一些些通常需要人人类智能才能能完成的复杂杂工作。但不不同的时代、不不同的人对这这种“复杂工作”的理解是不

3、不同的。人工智能是计算算机学科的一一个分支，二二十世纪七十十年代以来被被称为世界三三大尖端技术术之一（空间间技术、能源源技术、人工工智能）。也也被认为是二二十一世纪三三大尖端技术术（基因工程程、纳米科学学、人工智能能）之一。这这是因为近三三十年来它获获得了迅速的的发展，在很很多学科领域域都获得了广广泛应用，并并取得了丰硕硕的成果，人人工智能已逐逐步成为一个个独立的分支支，无论在理理论和实践上上都已自成一一个系统。人工智能是研究究使计算机来来模拟人的某某些思维过程程和智能行为为（如学习、推推理、思考、规规划等）的学学科，主要包包括计算机实实现智能的原原理、制造类类似于人脑智智能的计算机机，使计算

4、机机能实现更高高层次的应用用。人工智能能将涉及到计计算机科学、心心理学、哲学学和语言学等等学科。可以以说几乎是自自然科学和社社会科学的所所有学科，其其范围已远远远超出了计算算机科学的范范畴，人工智智能与思维科科学的关系是是实践和理论论的关系，人人工智能是处处于思维科学学的技术应用用层次，是它它的一个应用用分支。从思思维观点看，人人工智能不仅仅限于逻辑思思维，要考虑虑形象思维、灵灵感思维才能能促进人工智智能的突破性性的发展，数数学常被认为为是多种学科科的基础科学学，数学也进进入语言、思思维领域，人人工智能学科科也必须借用用数学工具，数数学不仅在标标准逻辑、模模糊数学等范范围发挥作用用，数学进入入

5、人工智能学学科，它们将将互相促进而而更快地发展展。题目二：n皇后后问题一.问题描述分别用回溯法（递递归）、GAA算法和CSP的最最小冲突法求求解n皇后问问题。即如何能够在 nn 的国际象象棋棋盘上放放置n个皇后，使使得任何一个个皇后都无法法直接吃掉其其他的皇后？为了达到此此目的，任两两个皇后都不不能处于同一一条横行、纵纵行或斜线上上。要求：. 输入n，并并用运行时间间比较几种算算法在相同规规模的问题时时的求解效率率，并列表给给出结果。. 比较同一一算法在n不不相同时的运运行时间，分分析算法的时时间复杂性，并并列表给出结结果。如八皇后问题的的一个解二.设计分析1.算法分析 1) 回回溯法（递归归

6、）回溯法解题的一一般步骤编辑辑（1）针对所给给问题，定义义问题的解空空间；（2）确定易于于搜索的解空空间结构；（3）以深度优优先方式搜索索解空间，并并在搜索过程程中用剪枝函函数避免无效效搜索。引入一个整型一一维数组cool来存存放最终结果果，coli就表示示在棋盘第ii列、colli行有有一个皇后，为为了使程序再再找完了全部部解后回到最最初位置，设设定col0的初值值为0，即当当回溯到第00列时，说明明以求得全部部解，结束程程序运行。为为了方便算法法的实现，引引入三个整型型数组来表示示当前列在三三个方向上的的状态 ：a aii=0表示示第i行上还还没有皇后；b bii=0表示示第i列反斜斜线/

7、上没有有皇后；c cii=0表示示第i列正斜斜线上没有有皇后。棋盘中同一反斜斜线/上的方方格的行号与与列号相同；同一正斜线线上的方格格的行号与列列号之差均相相同，这就是是判断斜线的的依据。初始时，所有行行和斜线上都都没有皇后，从从第1列的第第1行配置第第一个皇后开开始，在第mm列，collm行放放置了一个合合理的皇后，准准备考察第mm+1列时，在在数组a，b和和c中为为第m列，ccolm行的位置设设定有皇后的的标志；当从从第m列回溯溯到m-1列列时，并准备备调整第m-1列的皇后后配置时，清清除在数组aa,b和c对应位置的的值都为1来来确定。 2)遗传算算法遗传算法的基本本运算过程如如下：a)初

8、始化：设设置进化代数数计数器t=0，设置最最大进化代数数T，随机生生成M个个体体作为初始群群体P(0)。b)个体评价：计算群体PP(t)中各各个个体的适适应度。遗传算法遗传算法c)选择运算:将选择算子子作用于群体体。选择的目目的是把优化化的个体直接接遗传到下一一代或通过配配对交叉产生生新的个体再再遗传到下一一代。选择操操作是建立在在群体中个体体的适应度评评估基础上的的。d)交叉运算：将交叉算子子作用于群体体。遗传算法法中起核心作作用的就是交交叉算子。e)变异运算：将变异算子子作用于群体体。即是对群群体中的个体体串的某些基基因座上的基基因值作变动动。群体P(t)经经过选择、交交叉、变异运运算之后

9、得到到下一代群体体P(t+11)。f)终止条件判判断:若t=T,则以进进化过程中所所得到的具有有最大适应度度个体作为最最优解输出，终终止计算。3）csp最小小冲突法（1）初始化NN个皇后的一一个放置，允允许有冲突（2）考虑某一一行的某个皇皇后，她可能能与x个皇后后冲突，然后后看看将这个个皇后移动到到这一行的哪哪个空位能使使得与其冲突突的皇后个数数最少，就移移动到那里。（也也可以考虑列列，是等价的的）（3）不断执行行（2），直直到没有冲突突为止2.数据结构使用数组结构存存储相关数据据一维数组：二维数组：3.算法设计1）/回溯搜搜索 void Fuunctioon1:DDFS(innt t,boo

10、l isShoowTimee)if (t = n)/说明已已经排了n行行了（从0开开始的），即即排列结束了了for (int i = 0; in; i+)reci = boarddi;if (! isShhowTimme )PrrintChhessBooard();/输出出棋局countt+;returrn;for (iint i = 0; in; i+)/有冲突突if (vveri = 11|rui - tt + n = 11|rdi + t = 1) coontinuue;/没有冲冲突verii = 11;rui - t + n = 1;rdi + t = 11;boarddt = ii;

11、DFS(tt + 1, isShhowTimme);/深搜搜递归/后退处处理rdi + t = 00;rui - t + n = 0;verii = 00;returnn;2）遗传算法void CGGAQueeen:PrrintChhessBooard(bbool PrinttChesssBoardd)bool DDisplaayAllAAnsurees=PriintCheessBoaard;/是否输输出所有棋盘盘结果int gg = 0, num = 0;InitiaalPopuulatioon();while (g = 0 & num Itteratiion)num+;g = 00;for

12、 (int k = 0; k Popullationn ; k+)thiss-FilllAreaa(k);thiss-CosstMatrrixk = thhis-CCostFuunc(k);this-PopuulatioonSortt();if (tthis-CostMMatrixx0 = 0)/已经完成成计算g = 1;if (DDisplaayAllAAnsurees)PrinntTheBBestAnnsure();/*foor (i = 0; i = ChesssBoraddLenghht - 11; i+)couut row: i coll: ChrromosoomeMattrixii

13、0 enndl;coutt GeneerateCCrossOOverMaatrix();this-Matiing();this-AppllyMutaation();cout 实际际迭代： nuum 次 endll;if (DiisplayyAllAnnsuress)cout 最最佳答案为： PrinntTheBBestAnnsure();3）CSP最小小冲突算法/用最小冲突突算法调整第第row行的的皇后的位置置（初始化时时每行都有一一个皇后，调调整后仍然在在第row行行）/调整过后ccheck一一下看看是否否已经没有冲冲突，如果没没有冲突（达达到终止状态态），返回ttruebool CSSP_

14、Queeens:Adjusst_roww(int row)int cuur_coll = Rrow;int opptimall_col = curr_col;/最佳列列号，设置为为当前列，然然后更新/计算总冲冲突数int miin_connflictt = coolopttimal_col + pdiiagGeetP(roow, opptimall_col) - 11+ cdiiagGeetC(roow, opptimall_col) - 11;/对角角线冲突数为为当前对角线线皇后数减一一,三次重叠叠了/逐个检查查第row行行的每个位置置，看看是否否存在冲突数数更小的位置置for (iint

15、i = 0; i NN; i+) if (ii = ccur_cool) coontinuue;int cconfliict = colii + ppdiagGetP(row, ii) + cdiaggGetCC(row, ii);if (cconfliict min_cconfliict) min_confllict = confflict;optiimal_ccol = i;/如果最佳佳列位置改变变，则皇后移移向新的最小小冲突位置，要要更新coll,pdiaag,cdiiag，if (opptimall_col != cuur_coll) colccur_cool-;pdiaggGetPP

16、(row, curr_col)-;cdiaggGetCC(row, ccur_cool)-;colooptimaal_coll+;pdiaggGetPP(row, ooptimaal_coll)+;cdiaggGetCC(row, ooptimaal_coll)+;Rroww = ooptimaal_coll;if (ccolcuur_coll = 1 & colooptimaal_coll = 1& ppdiagGetP(row, ooptimaal_coll) = 1 & cdiaagGettC(roww, opttimal_col) = 11) retuurn Quualifyy();/

17、qualiify相对更更耗时，所以以只在满足上上面基本条件件后才检查/否则当前前点就是最佳佳点，一切都都保持不变returnn falsee;/如果都都没变的话，肯肯定不满足终终止条件，否否则上一次就就应该返回ttrue并终终止了/检查冲突bool CSSP_Queeens:Qualiify()for (iint i = 0; i NN; i+)if (ccolRi != 1 |pdiaagGettP(i, Ri) != 1 |cdiaagGettC(i, Ri) != 1) retuurn falsee;returnn true;/最终用户调调用函数，nnumOfQQueenss为输入皇后后

18、数，PriintCheessBoaard判断是是否输出棋盘盘表示int CSPP_Queeens:CCSPAlggorithhms(boool PrinttChesssBord)srand(unsiigned)time(NULL);Init();if (Quualifyy() /运气很很好，初始化化后就满足终终止条件if (PPrintCChessBBord)PPrint_resullt();returrn 0;bool eend = falsee;while (!endd) for (int i = 0; i 100)时，前两者者都不能再解解决，此时，CCSP最小冲冲突法的效率率最高，且与与

19、n值没有必必然的联系。总结 通过此此次课程实习习不仅大大加加深了我对几几种经典搜索索算法的理解解，而且帮助助我很好的复复习了队列、堆堆栈、图、文文件读写这几几部分的内容容，使我对几几种基本的数数据结构类型型的运用更加加熟练。在解解决这些问题题的过程中我我不但很好的的巩固了数据据结构的相关关知识，而且且提高了编程程及程序调试试能力，增强强了自己编程程的信心。 总之，在在这次课程实实习过程中我我是实实在在在学到了一些些课堂上学不不到的东西，同同时也提高了了实践能力。同同时在这个过过程中也暴露露了自己的不不少问题，在在今后的学习习过程成也会会更加有针对对性。最后还还要感谢老师师的悉心指导导，解答我编

20、编程过程中的的疑问、指出出我程序中的的不足，及提提出可行的解解决方法，让让我的程序的的功能更加完完善。CSP算法源代代码：/CSPAllgoritthms.hh#pragmaa onceclass CCSP_Quueenspublic:/构造函数数，numOOfQueeens为输入入皇后数，CSP_Quueens(int nuumOfQuueens);CSP_QQueenss();privatee:/rowi表示当当前摆放方式式下第i行的的皇后数，int *rrow;/coli表示当当前摆放方式式下第i列的的皇后冲突数数int *ccol;int N; /放置置N个皇后在在N*N棋盘盘上/从左

21、上到到右下的对角角线上roww-col值值是相同的，但但是这个值有有可能是负值值，最小为-(N-1)，/所以可以以做个偏移，统统一加上N-1，这样这这个值就在0,2*NN-2范围围内，将这个个值作为该对对角线的编号号/pdiaagi表表示当前摆放放方式下编号号为i的对角角线上的皇后后数int *ppdiag;/priincipaal diaagonall,主对角线线，左上到右右下（表示和和主对角线平平行的2N-1条对角线线）/从右上到到左下的对角角线row+col的值值相同，取值值范围为00, 2 * N - 2，2*N-1条，作作为对角线编编号/cdiaagi表表示编号为ii的对角线上上的皇

22、后数int *ccdiag;/couunter diagoonal,副副对角线/R用用来存储皇后后放置位置，RRrow = cool表示(rrow,cool)处,即即“第roww行第coll列”有个皇皇后int *RR;public:int swwap(innt &a, int &bb);/给定二维维矩阵的一个个点坐标，返返回其对应的的左上到右下下的对角线编编号int GeetP(innt roww, intt col);/给定二维维矩阵的一个个点坐标，返返回其对应的的右上到左下下的对角线编编号int GeetC(innt roww, intt col);/返回beegin, beginn +

23、 1, . , endd - 1 这end - beggin个数中中的随机的一一个int Myy_randd(int beegin, int ennd);/左闭右开beginn, endd)/原地shhufflee算法，算法法导论中的rrandommize iin plaace算法void RRandommize(iint a, innt beggin, iint ennd);/ 左闭右开开/初始化化皇后的摆放放，同时初始始化row,col,ppdiag,cdiagg数组void IInit();/用最小冲冲突算法调整整第row行行的皇后的位位置（初始化化时每行都有有一个皇后，调调整后仍然在在

24、第row行行）/调整过后后checkk一下看看是是否已经没有有冲突，如果果没有冲突（达达到终止状态态），返回ttruebool AAdjustt_row(int roow);bool QQualiffy();void PPrint_resullt();/最终用户户调用函数 PrinttChesssBoardd判断是否输输出棋盘表示示int CSSPAlgoorithmms(boool PriintCheessBorrd);/CSPAllgoritthms.ccpp#includdeCSPPAlgorrithmss.h#includde #includde #includde #includde

25、using nnamesppace sstd;CSP_Queeens:CSP_QQueenss(int numOffQueenns)srand(unsiigned)time(NULL);N = nuumOfQuueens;row = new intN;col = new intN;pdiag=new int2 * N;cdiag=new int2 * N;R=new intN;CSP_Queeens:CSP_Queenns()if (NUULL != row)deletteroow;if (NUULL != col)delettecool;if (NUULL != pdiaag)dellete

26、pdiagg;if (NUULL != cdiaag)delletecdiagg;if (NUULL != R)deeleteR;int CSPP_Queeens:sswap(iint &a, int &b)int t = a; a = b; b = t;returnn 0;/int CSPP_Queeens:GGetP(iint row, int col)returnn row - col + N - 11;int CSPP_Queeens:GGetC(iint row, int col)returnn row + col;/返回beggin, bbegin + 1, . , end - 1

27、 这这end - begiin个数中的的随机的一个个int CSPP_Queeens:MMy_rannd(intt beginn, int end)/左闭右右开beggin, eend)returnn randd() % (end - beginn) + beegin;/原地shuuffle算算法，算法导导论中的raandomiize inn placce算法void CSSP_Queeens:Randoomize(int a, innt beginn, int end)/ 左闭闭右开for (iint i = beggin; ii = eend - 2; i+)int xx = Myy_ra

28、ndd(i, eend);swap(ai, ax);/初始化皇后后的摆放，同同时初始化rrow,cool,pdiiag,cddiag数组组void CSSP_Queeens:Init()for (iint i = 0; i NN; i+)/首首先全部安放放在主对角线线上Ri = i;/下面随机机抽取调换两两行皇后位置置Randommize(RR, 0, N);/初始化N个个皇后对应的的R数组为00N-1的的一个排列，/此时 即即没有任意皇皇后同列，也也没有任何皇皇后同行for (iint i = 0; i NN; i+)rowii = 11;/每行行恰好一个皇皇后colii = 00;for

29、(iint i = 0; i 22 * N - 1; i+)pdiaggi = 0;cdiaggi = 0;/初始化当当前棋局的皇皇后所在位置置的各个冲突突数for (iint i = 0; i NN; i+)colRRi+;pdiaggGetPP(i, RRi)+;cdiaggGetCC(i, RRi)+;/用最小冲突突算法调整第第row行的的皇后的位置置（初始化时时每行都有一一个皇后，调调整后仍然在在第row行行）/调整过后ccheck一一下看看是否否已经没有冲冲突，如果没没有冲突（达达到终止状态态），返回ttruebool CSSP_Queeens:Adjusst_roww(int ro

30、w)int cuur_coll = Rrow;int opptimall_col = curr_col;/最佳列列号，设置为为当前列，然然后更新int miin_connflictt = coolopttimal_col + pdiiagGeetP(roow, opptimall_col) - 11+ cdiiagGeetC(roow, opptimall_col) - 11;/对角角线冲突数为为当前对角线线皇后数减一一for (iint i = 0; i NN; i+) /逐个检查第第row行的的每个位置if (ii = ccur_cool) conttinue;int cconfliict

31、 = colii + ppdiagGetP(row, ii) + cdiaggGetCC(row, ii);if (cconfliict min_cconfliict) min_confllict = confflict;optiimal_ccol = i;if (opptimall_col != cuur_coll) /要更新cool,pdiiag,cddiagcolccur_cool-;pdiaggGetPP(row, ccur_cool)-;cdiaggGetCC(row, ccur_cool)-;colooptimaal_coll+;pdiaggGetPP(row, ooptimaal

32、_coll)+;cdiaggGetCC(row, ooptimaal_coll)+;Rroww = ooptimaal_coll;if (ccolcuur_coll = 1 & colooptimaal_coll = 1& ppdiagGetP(row, ooptimaal_coll) = 1 & cdiaagGettC(roww, opttimal_col) = 11) retuurn Quualifyy();/qualiify相对更更耗时，所以以只在满足上上面基本条件件后才检查/当前点就就是最佳点，一一切都保持不不变returnn falsee;/如果都都没变的话，肯肯定不满足终终止条件，

33、否否则上一次就就应该返回ttrue并终终止了/检查冲突bool CSSP_Queeens:Qualiify()for (iint i = 0; i NN; i+)if (ccolRi != 1 |pdiaagGettP(i, Ri) != 1 |cdiaagGettC(i, Ri) != 1) retuurn falsee;returnn true;void CSSP_Queeens:Printt_resuult()cout -结果为: eendl;cout enddl;for (iint j = 0; j NN; j+) for (int k = 0; k NN; k+) if (Rj =

34、k)couut Q;elseecouut +;coutt ;cout enndl;/最终用户调调用函数，nnumOfQQueenss为输入皇后后数，PriintCheessBoaard判断是是否输出棋盘盘表示int CSPP_Queeens:CCSPAlggorithhms(boool PrinttChesssBord)srand(unsiigned)time(NULL);Init();if (Quualifyy() /运气很很好，初始化化后就满足终终止条件Printt_resuult();returrn 0;bool eend = falsee;while (!endd) for (int

35、i = 0; i NN; i+) if (Adjusst_roww(i) endd = trrue;breeak;Print_resullt();returnn 0;/Sourcce.cppp#includde #includde#includdeCSPPAlgorrithmss.husing nnamesppace sstd;int maiin(intt argc, constt char *argv)bool eend = falsee;while (!endd) cout -CSPAllgoritthms- enddl;cout N;int ttime1 = cloock();CSP_QQueenss myQuueens(N);myQueeens.CCSPAlggorithhms(ennd);int ttime2 = cloock();cout - N 皇后后问题耗时： time22 - tiime1 mms endll;char p;cout p;if (pp = n)breakk;returnn 0;- 32 -