人工智能课程设计报告n皇后问题解读_人工智能课程设计报告

人工智能课程设计报告n皇后问题解读由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“人工智能课程设计报告”。

人工智能课程设计报告

课 程:人工智能课程设计报告

班 级: 姓 名: 学 号: 指导教师:赵曼

2015年11月

人工智能课程设计报告

人工智能课程设计报告

课程背景

人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，未来人工智能带来的科技产品，将会是人类智慧的“容器”。

人工智能是对人的意识、思维的信息过程的模拟。人工智能不是人的智能，但能像人那样思考、也可能超过人的智能。

人工智能是一门极富挑战性的科学，从事这项工作的人必须懂得计算机知识，心理学和哲学。人工智能是包括十分广泛的科学，它由不同的领域组成，如机器学习，计算机视觉等等，总的说来，人工智能研究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完成的复杂工作。但不同的时代、不同的人对这种“复杂工作”的理解是不同的。

人工智能是计算机学科的一个分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被认为是二十一世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无论在理论和实践上都已自成一个系统。

人工智能是研究使计算机来模拟人的某些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展，数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用，数学进入人工智能学科，它们将互相促进而更快地发展。

人工智能课程设计报告

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.数据结构

使用数组结构存储相关数据 一维数组：

t + n] == 1||rd[i + t] == 1)continue;

//没有冲突 ver[i] = 1;ru[i

人工智能课程设计报告

}

} //后退处理 rd[i + t] = 0;ru[i1;i++){

}

cout ChromosomeMatrix[i][0] FillArea(k);this->CostMatrix[k] = this->CostFunc(k);bool DisplayAllAnsures=PrintCheBoard;//是否输出所有棋盘结果 int g = 0, num = 0;

//逐个检查第row行的每个位置，看看是否存在冲突数更小的位置 for(int i = 0;i

} if(i == cur_col)continue;

int conflict = col[i] + pdiag[GetP(row, i)] + cdiag[GetC(row, i)];if(conflict

} min_conflict = conflict;optimal_col = i;+ cdiag[GetC(row, optimal_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(){

} //最终用户调用函数，numOfQueens为输入皇后数，PrintCheBoard判断是否输出棋盘表示 int CSP_Queens::CSPAlgorithms(bool PrintCheBord){

srand((unsigned)time(NULL));Init();if(Qualify()){//运气很好，初始化后就满足终止条件

} bool end = false;while(!end){

for(int i = 0;i

} return true;if(col[R[i]]!= 1 ||

} pdiag[GetP(i, R[i])]!= 1 || cdiag[GetC(i, R[i])]!= 1){ return false;

人工智能课程设计报告

2.遗传算法

3.CSP最小冲突算法

人工智能课程设计报告

总的来说，回溯在n值很小时，效率很高，但其求解范围很小，超过35基本就解不出来，遗传算法求解范围适中。在n值很大(>100)时，前两者都不能再解决，此时，CSP最小冲突法的效率最高，且与n值没有必然的联系。

总结

通过此次课程实习不仅大大加深了我对几种经典搜索算法的理解，而且帮助我很好的复习了队列、堆栈、图、文件读写这几部分的内容，使我对几种基本的数据结构类型的运用更加熟练。在解决这些问题的过程中我不但很好的巩固了数据结构的相关知识，而且提高了编程及程序调试能力，增强了自己编程的信心。

总之，在这次课程实习过程中我是实实在在学到了一些课堂上学不到的东西，同时也提高了实践能力。同时在这个过程中也暴露了自己的不少问题，在今后的学习过程成也会更加有针对性。最后还要感谢老师的悉心指导，解答我编程过程中的疑问、指出我程序中的不足，及提出可行的解决方法，让我的程序的功能更加完善。

CSP算法源代码：

//CSPAlgorithms.h #pragma once

cla CSP_Queens { public: //构造函数，numOfQueens为输入皇后数，CSP_Queens(int numOfQueens);~CSP_Queens();

private:

//row[i]表示当前摆放方式下第i行的皇后数，int *row;//col[i]表示当前摆放方式下第i列的皇后冲突数 int *col;int N;//放置N个皇后在N*N棋盘上

//从左上到右下的对角线上row-col值是相同的，但是这个值有可能是负值，最小为

12]，2*N-1条，作为对角线编号

//R[]用来存储皇后放置位置，R[row] = col表示(row,col)处,即“第row行第col列”//cdiag[i]表示编号为i的对角线上的皇后数 int *cdiag;//counter diagonal,副对角线

有个皇后

int *R;

public:

int swap(int &a, int &b);

//给定二维矩阵的一个点坐标，返回其对应的左上到右下的对角线编号 int GetP(int row, int col);//给定二维矩阵的一个点坐标，返回其对应的右上到左下的对角线编号 int GetC(int row, int col);//返回begin, begin + 1,..., endbegin个数中的随机的一个 int My_rand(int begin, int end);//左闭右开[begin, end)

人工智能课程设计报告

N = numOfQueens;row = new int[N];col = new int[N];pdiag=new int[2 * N];cdiag=new int[2 * N];R=new int[N];}

CSP_Queens::~CSP_Queens(){ if(NULL!= row)delete[]row;if(NULL!= col)delete[]col;if(NULL!= pdiag)delete[]pdiag;if(NULL!= cdiag)delete[]cdiag;if(NULL!= R)delete[]R;} 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 row1;}

int CSP_Queens::GetC(int row, int col){ return row + col;} //返回begin, begin + 1,..., endbegin个数中的随机的一个 int CSP_Queens::My_rand(int begin, int end)//左闭右开[begin, end){ return rand()%(end

人工智能课程设计报告

{

} for(int i = begin;i

+ cdiag[GetC(row, optimal_col)]

人工智能课程设计报告

} } //当前点就是最佳点，一切都保持不变

return false;//如果都没变的话，肯定不满足终止条件，否则上一次就应该返回true并终止了 }

//检查冲突

bool CSP_Queens::Qualify(){ for(int i = 0;i

if(col[R[i]]!= 1 ||

pdiag[GetP(i, R[i])]!= 1 ||

cdiag[GetC(i, R[i])]!= 1){

return false;

} } return true;} void CSP_Queens::Print_result(){

} cout

if(R[j] == k)

cout

else

cout

cout

人工智能课程设计报告

int N;cin >> N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout

读书的好处

1、行万里路，读万卷书。

2、书山有路勤为径，学海无涯苦作舟。

3、读书破万卷，下笔如有神。

4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文

5、少壮不努力，老大徒悲伤。

6、黑发不知勤学早，白首方悔读书迟。——颜真卿

7、宝剑锋从磨砺出，梅花香自苦寒来。

8、读书要三到：心到、眼到、口到

9、玉不琢、不成器，人不学、不知义。

10、一日无书，百事荒废。——陈寿

11、书是人类进步的阶梯。

12、一日不读口生，一日不写手生。

13、我扑在书上，就像饥饿的人扑在面包上。——高尔基

14、书到用时方恨少、事非经过不知难。——陆游

15、读一本好书，就如同和一个高尚的人在交谈——歌德

16、读一切好书，就是和许多高尚的人谈话。——笛卡儿

17、学习永远不晚。——高尔基

18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向

19、学而不思则惘，思而不学则殆。——孔子

20、读书给人以快乐、给人以光彩、给人以才干。——培根