人工智能课程设计报告皇后问题样本.doc

课 程:人工智能课程设计报告
班 级：
姓 名：
学 号：
指引教师:赵曼

11月

人工智能课程设计报告
课程背景
人工智能（Artificial Intelligence），英文缩写为AI。它是研究、开发用于模仿、延伸和扩展人智能理论、办法、技术及应用系统一门新技术科学。 人工智能是计算机科学一种分支，它企图理解智能实质，并生产出一种新能以人类智能相似方式做出反映智能机器，该领域研究涉及机器人、语言辨认、图像辨认、自然语言解决和专家系统等。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，可以设想，将来人工智能带来科技产品，将会是人类智慧“容器”。
人工智能是对人意识、思维信息过程模仿。人工智能不是人智能，但能像人那样思考、也也许超过人智能。
人工智能是一门极富挑战性科学，从事这项工作人必要懂得计算机知识，心理学和哲学。人工智能是涉及十分广泛科学，它由不同领域构成，如机器学习，计算机视觉等等，总说来，人工智能研究一种重要目的是使机器可以胜任某些普通需要人类智能才干完毕复杂工作。但不同步代、不同人对这种“复杂工作”理解是不同。
人工智能是计算机学科一种分支，二十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人工智能）。也被以为是21世纪三大尖端技术（基因工程、纳米科学、人工智能）之一。这是由于近三十年来它获得了迅速发展，在诸多学科领域都获得了广泛应用，并获得了丰硕成果，人工智能已逐渐成为一种独立分支，无论在理论和实践上都已自成一种系统。
人工智能是研究使计算机来模仿人某些思维过程和智能行为（如学习、推理、思考、规划等）学科，重要涉及计算机实现智能原理、制造类似于人脑智能计算机，使计算机能实现更高层次应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可以说几乎是自然科学和社会科学所有学科，其范畴已远远超过了计算机科学范畴，人工智能与思维科学关系是实践和理论关系，人工智能是处在思维科学技术应用层次，是它一种应用分支。从思维观点看，人工智能不但限于逻辑思维，要考虑形象思维、灵感思维才干增进人工智能突破性发展，数学常被以为是各种学科基本科学，数学也进入语言、思维领域，人工智能学科也必要借用数学工具，数学不但在原则逻辑、模糊数学等范畴发挥作用，数学进入人工智能学科，它们将互相增进而更快地发展。

题目二：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<n；i++)
{
rec[i] = board[i];
}
if (！isShowTime )PrintChessBoard();//输出棋局
count++;
return;
}
for (int i = 0；i<n；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.递归算法

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 once
class 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值是相似，但是这个值有也许是负值，最小为-(N-1)，
//因此可以做个偏移，统一加上N-1，这样这个值就在[0,2*N-2]范畴内，将这个值作为该对角线编号
//pdiag[i]表达当前摆放方式下编号为i对角线上皇后数
int *pdiag;//principal diagonal,主对角线，左上到右下（表达和主对角线平行2N-1条对角线）

//从右上到左下对角线row+col值相似，取值范畴为[0，2 * N - 2]，2*N-1条，作为对角线编号
//cdiag[i]表达编号为i对角线上皇后数
int *cdiag;//counter diagonal,副对角线

//R[]用来存储皇后放置位置，R[row] = 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一下看看与否已经没有冲突，如果没有冲突（达到终结状态），返回true
bool 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 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 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(a[i]，a[x]);
}
}
//初始化皇后摆放，同步初始化row,col,pdiag,cdiag数组
void CSP_Queens::Init()
{
for (int i = 0；i < N；i++){//一方面所有安放在主对角线上
R[i] = i;
}
//下面随机抽取调换两行皇后位置
Randomize(R，0，N);//初始化N个皇后相应R数组为0~N-1一种排列，
//此时 即没有任意皇后同列，也没有任何皇后同行
for (int i = 0；i < N；i++){
row[i] = 1;//每行正好一种皇后
col[i] = 0;
}
for (int i = 0；i < 2 * N - 1；i++){
pdiag[i] = 0;
cdiag[i] = 0;
}
//初始化当前棋局皇后所在位置各个冲突数
for (int i = 0；i < N；i++){
col[R[i]]++;
pdiag[GetP(i，R[i])]++;
cdiag[GetC(i，R[i])]++;
}
}

//用最小冲突算法调节第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;//对角线冲突数为当前对角线皇后数减一
for (int i = 0；i < N；i++) {//逐个检查第row行每个位置
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;
}
}
if (optimal_col != cur_col) {//要更新col,pdiag,cdiag
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;
}
void CSP_Queens::Print_result()
{
cout << "-------成果为:" << endl;
cout << endl;
for (int j = 0；j < N；j++) {
for (int k = 0；k < N；k++) {
if (R[j] == k)
cout << "Q";
else
cout << "+";
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;
}