人工智能课程设计报告-n皇后问题20.docx

人工智能课程设计报告 课 程:人工智能课程设计报告 班 级: 姓 名: 学 号: 指导教师:赵曼 2015年11月人工智能课程设计报告课程背景 人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。题目二：n皇后问题一.问题描述分别用回溯法（递归）、GA算法和CSP的最小冲突法求解n皇后问题。即如何能够在 n×n 的国际象棋棋盘上放置n个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。要求：. 输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率，并列表给出结果。. 比较同一算法在n不相同时的运行时间，分析算法的时间复杂性，并列表给出结果。如八皇后问题的一个解二.设计分析1.算法分析 1) 回溯法（递归）回溯法解题的一般步骤编辑（1）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。引入一个整型一维数组col来存放最终结果，coli就表示在棋盘第i列、coli行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col0的初值为0，即当回溯到第0列时，说明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态 ：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)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价：计算群体P(t)中各个个体的适应度。遗传算法遗传算法c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。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; i<n; i+)reci = boardi;if (! isShowTime )PrintChessBoard();/输出棋局count+;return;for (int i = 0; i<n; 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 PrintChessBoard)bool DisplayAllAnsures=PrintChessBoard;/是否输出所有棋盘结果int g = 0, num = 0;InitialPopulation();while (g = 0 && num < this->Iteration)num+;g = 0;for (int k = 0; k < this->Population ; k+)this->FillArea(k);this->CostMatrixk = this->CostFunc(k);this->PopulationSort();if (this->CostMatrix0 = 0)/已经完成计算g = 1;if (DisplayAllAnsures)PrintTheBestAnsure();/*for (i = 0; i <= ChessBoradLenght - 1; i+)cout << "row:" << i << " col:" << this->ChromosomeMatrixi0 << endl;cout << endl;*/this->GenerateCrossOverMatrix();this->Mating();this->ApplyMutation();cout << "实际迭代：" << num <<" 次"<< endl;if (DisplayAllAnsures)cout << "最佳答案为：" << endl;this->PrintTheBestAnsure();3）CSP最小冲突算法/用最小冲突算法调整第row行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第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行的每个位置，看看是否存在冲突数更小的位置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(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并终止了/检查冲突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(unsigned)time(NULL);Init();if (Qualify() /运气很好，初始化后就满足终止条件if (PrintChessBord)Print_result();return 0;bool end = false;while (!end) for (int i = 0; i < N; i+) if (Adjust_row(i) end = true;break;if (PrintChessBord)Print_result();return 0;四.运行结果及分析1.递归算法2.遗传算法3.CSP最小冲突算法4.n=4时不同算法的比较5.n=8时不同算法比较结果分析回溯法在皇后数目较小的，很占优势，它的速度非常的快，但随着皇后数目的增加，回溯法显得很不实用，在n=35时，用回溯法已不能较好的解决n皇后问题。遗传算法优点是能很好的处理约束，能很好的跳出局部最优，最终得到全局最优解，全局搜索能力强；缺点是收敛较慢，局部搜索能力较弱，运行时间中等，且容易受n值的影响。遗传算法的运行时间在n很小时没有回溯法快，但是随着n值的增加，遗产算法的优点也就显现出来，它能够解决回溯法不能解决的问题。CSP最小冲突法是一种始终都比较快的算法，它的运行时间与皇后是个数没有必然的联系，而且在n很大时，它显现出来运行时间短，效率高的优势，但它的缺点是会出现山脊、高原，86%的时间会卡住。总的来说，CSP最小冲突法较简单，也比较快，在皇后的个数较多时体现出来效率最高，处理多约束大规模问题时往往不能得到较好的解。 总的来说，回溯在n值很小时，效率很高，但其求解范围很小，超过35基本就解不出来，遗传算法求解范围适中。在n值很大(>100)时，前两者都不能再解决，此时，CSP最小冲突法的效率最高，且与n值没有必然的联系。总结 通过此次课程实习不仅大大加深了我对几种经典搜索算法的理解，而且帮助我很好的复习了队列、堆栈、图、文件读写这几部分的内容，使我对几种基本的数据结构类型的运用更加熟练。在解决这些问题的过程中我不但很好的巩固了数据结构的相关知识，而且提高了编程及程序调试能力，增强了自己编程的信心。 总之，在这次课程实习过程中我是实实在在学到了一些课堂上学不到的东西，同时也提高了实践能力。同时在这个过程中也暴露了自己的不少问题，在今后的学习过程成也会更加有针对性。最后还要感谢老师的悉心指导，解答我编程过程中的疑问、指出我程序中的不足，及提出可行的解决方法，让我的程序的功能更加完善。CSP算法源代码：/CSPAlgorithms.h#pragma onceclass CSP_Queenspublic:/构造函数，numOfQueens为输入皇后数，CSP_Queens(int numOfQueens);CSP_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条对角线）/从右上到左下的对角线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, int 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行）/调整过后check一下看看是否已经没有冲突，如果没有冲突（达到终止状态），返回truebool Adjust_row(int row);bool Qualify();void Print_result();/最终用户调用函数 PrintChessBoard判断是否输出棋盘表示int CSPAlgorithms(bool PrintChessBord);/CSPAlgorithms.cpp#include"CSPAlgorithms.h"#include <cstdio>#include <cstdlib>#include <ctime>#include<iostream>using namespace std;CSP_Queens:CSP_Queens(int numOfQueens)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(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 - 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;/下面随机抽取调换两行皇后位置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行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第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+) /逐个检查第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(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并终止了/检查冲突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;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为输入皇后数，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#include <ctime>#include<iostream>#include"CSPAlgorithms.h"using namespace std;int main(int argc, const char *argv)bool end = false;while (!end) cout << "-CSPAlgorithms-" << endl;cout << "-请输入皇后数："int N;cin >> N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout << "-" << N << "皇后问题耗时：" << time2 - time1 << " ms" << endl;char p;cout << "是否继续测试？(y/n):"cin >> p;if (p = 'n')break;return 0;- 19 -