人工智能课程设计报告-n皇后问题解读(共22页).doc

《人工智能课程设计报告-n皇后问题解读(共22页).doc》由会员分享，可在线阅读，更多相关《人工智能课程设计报告-n皇后问题解读(共22页).doc（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个

6、方向上的状态 ：a ai=0表示第i行上还没有皇后；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)初始化：

7、设置进化代数计数器t=0，设置最大进化代数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 = board

9、i;if (! isShowTime )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

10、(bool PrintChessBoard)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

11、 (DisplayAllAnsures)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;/对角线冲突数为当前对角线皇后数减一,三次重叠了/

13、逐个检查第row行的每个位置，看看是否存在冲突数更小的位置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

14、(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相对更耗时，所以只在满足上面基本条件后才检查/否则当前点就是最佳点

15、，一切都保持不变return 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

16、)srand(unsigned)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);CS

18、P_Queens();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条对角线）/从右上到左下的对角线

19、row+col的值相同，取值范围为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, in

20、t col);/返回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行）/调整过后chec

21、k一下看看是否已经没有冲突，如果没有冲突（达到终止状态），返回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 numOfQuee

22、ns)srand(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

23、(int &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 -

24、 begin) + 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;/下面随机抽取调换两行皇

25、后位置Randomize(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行的皇后的位置（初始化时每行都有一个皇后，调整

26、后仍然在第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;/对角线冲突数为当前对角线皇后数减一for (int i = 0; i N; i+) /逐个检查

27、第row行的每个位置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(ro

28、w, 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并终止了/检查冲突bool CSP

29、_Queens:Qualify()for (int i = 0; i N; i+)if (colRi != 1 |pdiagGetP(i, Ri) != 1 |cdiagGetC(i, Ri) != 1) return false;return true;void CSP_Queens:Print_result()cout -结果为: endl;cout endl;for (int j = 0; j N; j+) for (int k = 0; k N; k+) if (Rj = k)cout Q;elsecout +;cout ;cout endl;/最终用户调用函数，numOfQueens

30、为输入皇后数，PrintChessBoard判断是否输出棋盘表示int CSP_Queens:CSPAlgorithms(bool PrintChessBord)srand(unsigned)time(NULL);Init();if (Qualify() /运气很好，初始化后就满足终止条件Print_result();return 0;bool end = false;while (!end) for (int i = 0; i N; i+) if (Adjust_row(i) end = true;break;Print_result();return 0;/Source.cpp#inclu

31、de #include#includeCSPAlgorithms.husing namespace std;int main(int argc, const char *argv)bool end = false;while (!end) cout -CSPAlgorithms- endl;cout N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout - N 皇后问题耗时： time2 - time1 ms endl;char p;cout p;if

32、(p = n)break;return 0; 读书的好处1、行万里路，读万卷书。2、书山有路勤为径，学海无涯苦作舟。3、读书破万卷，下笔如有神。4、我所学到的任何有价值的知识都是由自学中得来的。达尔文5、少壮不努力，老大徒悲伤。6、黑发不知勤学早，白首方悔读书迟。颜真卿7、宝剑锋从磨砺出，梅花香自苦寒来。8、读书要三到：心到、眼到、口到9、玉不琢、不成器，人不学、不知义。10、一日无书，百事荒废。陈寿11、书是人类进步的阶梯。12、一日不读口生，一日不写手生。13、我扑在书上，就像饥饿的人扑在面包上。高尔基14、书到用时方恨少、事非经过不知难。陆游15、读一本好书，就如同和一个高尚的人在交谈歌德16、读一切好书，就是和许多高尚的人谈话。笛卡儿17、学习永远不晚。高尔基18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。刘向19、学而不思则惘，思而不学则殆。孔子20、读书给人以快乐、给人以光彩、给人以才干。培根