课程:人工智能课程设计报告
班级:
姓名: 学号:
指导教师:赵曼
2015年11月
人工智能课程设计报告
课程背景
人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识不、图像识不、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，能够设想，以后人工智能带来的科技产品，将会是人类智慧的“容器”。
人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样考虑、也可能超过人的智能。
人工智能是一门极富挑战性的科学，从事这项工作的人必须明白得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的讲来，人工智能研究的一个要紧目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。
人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三
大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的进展，在专门多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，不管在理论和实践上都已自成一个系统。
人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、考虑、规划等）的学科，要紧包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。能够讲几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的进展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地进展。
题目二：n皇后问题
一.问题描述
分不用回溯法（递归）、GA算法和CSP的最小冲突法求解n皇后问题。
即如何能够在 n×n 的国际象棋棋盘上放置n个皇后，使得任何一个皇
后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
要求：
ⅰ. 输入n，并用运行时刻比较几种算法在相同规模的问题时的求解效率，并列表给出结果。
ⅱ. 比较同一算法在n不相同时的运行时刻，分析算法的时刻复杂性，并列表给出结果。
如八皇后问题的一个解
二.设计分析
1.算法分析
1) 回溯法（递归）
回溯法解题的一般步骤编辑
（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数幸免无效搜索。引入一个整型一维数组col[]来存放最终结果，col[i]就表示在棋盘第i列、col[i]行有一个皇后，为了使程序再找完了全部解后回到最初位置，设定col[0]的初值为0，即当回溯到第0列时，讲明以求得全部解，结束程序运行。为了方便算法的实现，引入三个整型数组来表示当前列在三个方向上的状态：
a[] a[i]=0表示第i行上还没有皇后；
b[] b[i]=0表示第i列反斜线/上没有皇后；
c[] c[i]=0表示第i列正斜线\上没有皇后。
棋盘中同一反斜线/上的方格的行号与列号相同；同一正斜线\上的方格的行号与列号之差均相同，这确实是推断斜线的依据。
初始时，所有行和斜线上都没有皇后，从第1列的第1行配置第一个皇后开始，在第m列，col[m]行放置了一个合理的皇后，预备考察第m+1列时，在数组a[]，b[]和c[]中为第m列，col[m]行的位置设定有皇后的标志；当从第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 { rec[i] = board[i]; } if (! isShowTime )PrintChessBoard();//输出棋局 count++; return; } for (int i = 0; i { //有冲突 if (ver[i] == 1||ru[i - t + n] == 1||rd[i + t] == 1) continue; //没有冲突 ver[i] = 1; ru[i - t + n] = 1; rd[i + t] = 1; board[t] = i; DFS(t + 1, isShowTime);//深搜递归 //后退处理 rd[i + t] = 0; ru[i - t + n] = 0; ver[i] = 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->CostMatrix[k] = this->CostFunc(k); } this->PopulationSort(); if (this->CostMatrix[0] == 0)//差不多完成计算 g = 1; if (DisplayAllAnsures) { PrintTheBestAnsure(); /*for (i = 0; i <= ChessBoradLenght - 1; i++) { cout << "row:" << i << " col:" << this->ChromosomeMatrix[i][0] << endl; } cout << endl;*/ } this->GenerateCrossOverMatrix(); this->Mating(); this->ApplyMutation(); } cout << "实际迭代：" << num <<" 次"<< endl; if (DisplayAllAnsures) { cout << "最佳答案为：" << endl; this->PrintTheBestAnsure(); } } 3）CSP最小冲突算法 //用最小冲突算法调整第row行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第row行） //调整过后check一下看看是否差不多没有冲突，假如没有冲突（达到终止状态），返回true bool CSP_Queens::Adjust_row(int row) { int cur_col = R[row]; int optimal_col = cur_col;//最佳列号，设置为当前列，然后更新 //计算总冲突数 int min_conflict = col[optimal_col] + pdiag[GetP(row, optimal_col)] - 1 + cdiag[GetC(row, optimal_col)] - 1;//对角线冲突数为当前对角线皇后数减一,三次重叠了 //逐个检查第row行的每个位置，看看是否存在冲突数更小的位置 for (int i = 0; i < N; i++) { if (i == cur_col) continue; int conflict = col[i] + pdiag[GetP(row, i)] + cdiag[GetC(row, i)]; if (conflict < min_conflict) { min_conflict = conflict; optimal_col = i; } } //假如最佳列位置改变，则皇后移向新的最小冲突位置，要更新 col,pdiag,cdiag， if (optimal_col != cur_col) { col[cur_col]--; pdiag[GetP(row, cur_col)]--; cdiag[GetC(row, cur_col)]--; col[optimal_col]++; pdiag[GetP(row, optimal_col)]++; cdiag[GetC(row, optimal_col)]++; R[row] = optimal_col; if (col[cur_col] == 1 && col[optimal_col] == 1 && pdiag[GetP(row, optimal_col)] == 1 && cdiag[GetC(row, optimal_col)] == 1) { return Qualify();//qualify相对更耗时，因此只在满足上面差不多条件后才检查 } } //否则当前点确实是最佳点，一切都保持不变 return false;//假如都没变的话，确信不满足终止条件，否则上一次就应该返回true并终止了 } //检查冲突 bool CSP_Queens::Qualify() { for (int i = 0; i < N; i++){ if (col[R[i]] != 1 || pdiag[GetP(i, R[i])] != 1 || cdiag[GetC(i, R[i])] != 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.递归算法
相关主题
文本预览