第一篇：人工智能课程设计报告-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 << endl;*/ cout << “row:” << i << “ col:” << this->ChromosomeMatrix[i][0] << endl;g = 1;if(DisplayAllAnsures)this->FillArea(k);this->CostMatrix[k] = this->CostFunc(k);bool DisplayAllAnsures=PrintChessBoard;//是否输出所有棋盘结果 int g = 0, num = 0;
//逐个检查第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;+ 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为输入皇后数，PrintChessBoard判断是否输出棋盘表示 int CSP_Queens::CSPAlgorithms(bool PrintChessBord){
srand((unsigned)time(NULL));Init();if(Qualify()){//运气很好，初始化后就满足终止条件
} bool end = false;while(!end){
for(int i = 0;i < N;i++){ if(Adjust_row(i)){ end = true;if(PrintChessBord)Print_result();return 0;for(int i = 0;i < N;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
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值是相同的，但是这个值有可能是负值，最小为
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 <= end1;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行的皇后的位置（初始化时每行都有一个皇后，调整后仍然在第
+ cdiag[GetC(row, optimal_col)]
人工智能课程设计报告
} } //当前点就是最佳点，一切都保持不变
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 N;cin >> N;int time1 = clock();CSP_Queens myQueens(N);myQueens.CSPAlgorithms(end);int time2 = clock();cout << “---” << N << “皇后问题耗时：” << time2
读书的好处
1、行万里路，读万卷书。
2、书山有路勤为径，学海无涯苦作舟。
3、读书破万卷，下笔如有神。
4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文
5、少壮不努力，老大徒悲伤。
6、黑发不知勤学早，白首方悔读书迟。——颜真卿
7、宝剑锋从磨砺出，梅花香自苦寒来。
8、读书要三到：心到、眼到、口到
9、玉不琢、不成器，人不学、不知义。
10、一日无书，百事荒废。——陈寿
11、书是人类进步的阶梯。
12、一日不读口生，一日不写手生。
13、我扑在书上，就像饥饿的人扑在面包上。——高尔基
14、书到用时方恨少、事非经过不知难。——陆游
15、读一本好书，就如同和一个高尚的人在交谈——歌德
16、读一切好书，就是和许多高尚的人谈话。——笛卡儿
17、学习永远不晚。——高尔基
18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向
19、学而不思则惘，思而不学则殆。——孔子
20、读书给人以快乐、给人以光彩、给人以才干。——培根
第二篇：人工智能课程设计(五子棋)解读
《人工智能导论》课程报告
课题名称： 五子棋
姓名: X X 学号：114304xxxx 课题负责人名（学号）： X X114304xxxx 同组成员名单（学号、角色）： x x1143041325 XXX1143041036
指导教师： 张建州 评阅成绩： 评阅意见：
提交报告时间：2014年 1 月 9 日 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
五子棋
计算机科学与技术 专业 学生 XXX 指导老师
张建州
[摘要] 人类之所以不断在进步，是因为我们人类一直不断的在思考，五子棋游戏程序的开发符合人类进步也是促进人类进步的一大动力之一。五子棋游戏程序让人们方便快捷的可以下五子棋，让人们在何时都能通过下棋来提高逻辑思维能力，同时也培养儿童的兴趣以及爱好，让孩子更加聪明。
同时，五子棋游戏程序的开发也使得五子棋这个游戏得到了广泛的推广，让世界各地的人们知道五子棋，玩上五子棋，这已经不是局限。五子棋游戏程序使得越来越多的人喜欢上了五子棋，热爱下五子棋，它是具有很好的带动性的。
关键词：五子棋
进步
思考
-1-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
目录
《人工智能导论》课程报告..................................................................................0 1 引言.....................................................................................................................3
1.1 五子棋简介...........................................................................................3 1.2 五子棋游戏的发展与现状......................................................................3 2 研究问题描述......................................................................................................4
2.1 问题定义...................................................................................................4 2.2 可行性研究...............................................................................................4 2.3 需求分析...................................................................................................5 2.4 总体设计...................................................................................................5 2.5 详细设计...................................................................................................6 2.6编码和单元测试........................................................................................6 3 人工智能技术......................................................................................................6 4 算法设计.............................................................................................................7
4.1α-β剪枝算法.............................................................................................7 4.2极大极小树................................................................................................7 4.3深度优先搜索（DFS）.............................................................................8 4.4静态估值函数............................................................................................9 5 软件设计和实现..................................................................................................9
5.1 数据结构定义...........................................................................................9 5.2 程序流程图.............................................................................................17 6 性能测试...........................................................................................................18
6.1 程序执行结果.........................................................................................18 7 总结...................................................................................................................21 参考文献...............................................................................................................21
-2-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 1 引言
1.1 五子棋简介
五子棋是一种两人对弈的纯策略型汉族棋类益智游戏，棋具与围棋通用，由中国汉族人发明，起源于中国上古时代的传统黑白棋种之一。主要流行于华人和汉字文化圈的国家以及欧美一些地区。
容易上手，老少皆宜，而且趣味横生，引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。已在各个游戏平台有应用。
古代五子棋棋盘与围棋棋盘是通用的，汉魏时为十七路（17×17）棋盘，至南北朝时即已流行十九路（19×19）棋盘，直至1931年出现所谓五子棋专用棋盘。
1.2 五子棋游戏的发展与现状
目前，连珠这一棋类运动已迅速在国际上发展起来。外国人都十分看好这一不起眼的智力游戏，并认为五子棋不仅能提高思维、开发智力、手脑并用、修身养性 而且富含哲理，具有东方的神秘和西方的直观，是中西文化的交汇点。许多国家的人对五子棋都有不同的爱称，例如韩国人把五子棋称之为“情侣棋”，言下之意是情人之间下五子棋有利于增加情感的交流；欧洲人称之为“中老年棋”，表示五子棋适合中老年人的生理特点和思维方式；美洲人喜欢将五子棋称之为“商业棋”，就是说商人谈生意时可一边下棋一边谈生意，棋下完了生意也谈成了。由此可见，尽管国度不同，语言各异，但人们都可以借助五子棋这一简单而又深奥的棋艺进行交流、比赛，增进友谊。
当前，有４０多个国家和地区都在下五子棋，并有各种规模和级别的比赛。１９８９年８月在日本京都、１９９１年８月在俄罗斯联邦的莫斯科、１９９３年８月在瑞典、１９９５年８月在爱沙尼亚的塔林分别举行了第一、二、三、四届世界锦标赛。除第三届的冠军是爱沙尼亚人之外，其余三届的冠军都是日本人。五子棋 的世界锦标赛，每两年举办一次，其申国竞争也十分激烈。日本目前拥有自己的五子棋职业棋手，并且对连珠（五子棋）技术的研究也相当普遍和全面，就水平也正在日益增强。同时，五子棋的理论研究与探索也呈现蓬勃发展的势头，从１８５８年第一部五子棋专著问世以来，目前，全世界有２０００多种五子棋的书籍及期刊，分别以日文、俄文、英文、瑞典文及中文出版发行。五子棋在我国的北京、上海、天津、云南、浙江、广东、四川、湖北、辽宁、新疆、河北等省（区）市都有很大的发展。北京多次举办了北京地区的五子棋赛，如“思曼杯”、“京空杯”、“奇奇童杯”、“北京第六届民族团结杯”和“北京第四岂民族运动会”的五子棋比赛。上海地区举办了“上文杯”五子棋大赛。云南省以及其他省市亦举办过许多五子棋比赛。所有这些赛事都越来越多地吸引了无数人的关注，表明了根植于中国的五子棋有着广泛的群众基础，-3-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 是群众喜闻乐见的体育活动。
而现在，很多很多游戏平台上面都有五子棋游戏供我们玩，任何游戏平台上面只要有棋牌类游戏的，那么它就有五子棋在里面，网络五子棋比赛，在联众，263，QQ游戏，UC里进行了10几年了可见，五子棋游戏在网络上面是非常火暴的，而且在棋牌游戏里面玩家人数排名总会占到很前面，不愧是风靡全球的棋牌游戏啊！在未来中，将会有越来越多的人关注五子棋，喜欢五子棋，那么将其变为商业化也会越来越多，而且还可以以教育孩子的方式来将其嵌套进去，或者用来做测试等等，可以说以后的五子棋游戏会是那么的精彩，那么的让人憧憬。那么对于它的游戏开发和发展也将会上升到举足轻重的地位去，它的发展会是相当之快的，就让我们拭目以待吧。研究问题描述
2.1 问题定义
问题定义的一个的关键问题是“要解决的问题是什么”，这个是这个阶段必须要明确要回答的问题。在没将问题定义好，试图准备下个阶段的任务。这明显是不成熟，甚至不可能的事。
本次系统设计中首先明确了需要解决的问题是五子棋AI算法，基本的要求是设计一款能够实现人机对战、人人对战和禁手的五子棋游戏，提供一些基本的操作如退出系统，向后悔棋等操作，重点是放在AI算法的研究。而并不是美工设计，也不是为了提供各种操作丰富的接口。主要是通过这种可视化的界面探讨AI，当然增加可玩性和美工会给系统润色不少。
上面只是很粗略的明确大概的方向，严格按照软件工程的方法这个阶段需要生产一份书面报告。需要通过对系统的实际用户访问调查，扼要地写出他对问题的理解，并在用户和使用部门负责人的会议上认真讨论这份书面报告，澄清含糊不精的地方，改正理解不正确的地方，最后得出一份双方都满意的文档。本系统的需求很少也很明显了。
2.2 可行性研究
这个阶段要回答的关键问题：“对于上一个阶段所确定的问题是否可行？”为了回答这个问题，我们需要进行一次大大压缩和简化了的系统分析和设计的过程，也就是在较抽象的高层次上进行的分析和设计的过程。
可行性研究应该比较简短，这个阶段的任务不是具体解决问题，而是研究问题的范围，探索这个问题是否值得去解，是否有可行的解决办法。
可行性研究应该比较简短，这个阶段的任务不是具体解决问题，而是研究问题的范围，探索这个问题是否值得去解，是否有可行的解决办法。可行性研
-4-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 究以后的那些阶段将需要投入要多的人力物力。及时中止不值得投资的工程项目，可以避免更大的浪费。
根据这些基本的概念，我在技术上主要是通过相关文档资料的查找后确定可行性，凭着大学期间打下厚实的专业科基础，特别是数据结构和算法，能够在这段时间理解通透并应该有所改进，后来证明是对的。利用剩下时间也应该来说也比较充裕的。经济上暂不考虑。
下面主要从技术上进行分析：
工具: Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaSE, JavaEE, JavaME）的总称。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。所以用java来编写是一个很好的选择。
算法：在这图论搜索技术这方面，前人已有很成熟的算法。如粗糙的有深度优先算法(DFS)和广度优先算法(BFS)这两个基本的算法，关键需要解决的是能够设计出一种高效的剪枝函数，减小搜索问题的规模。目前博弈类游戏中的人工智能基本都采用极大极小值方法这对我来说是个挑战，而剪枝的则采用Alpha-Beta，通过丰富的文档资料初步了解到这些技术已经很成熟了。我们有信心能解决好这个问题。
2.3 需求分析
人工智能的第一大成就是下棋程序，在下棋程度中应用的某些技术，如向前看几步，把困难的问题分解成一些较容易的子问题，发展成为搜索和问题归纳这样的人工智能基本技术。今天的计算机程序已能够达到下各种方盘棋和国际象棋的锦标赛水平。但是，尚未解决包括人类棋手具有的但尚不能明确表达的能力。如国际象棋大师们洞察棋局的能力。另一个问题是涉及问题的原概念，在人工智能中叫做问题表示的选择，人们常能找到某种思考问题的方法，从而使求解变易而解决该问题。到目前为止，人工智能程序已能知道如何考虑它们要解决的问题，即搜索解答空间，寻找较优解答。
在设计本系统时考虑到用户需要的是一个操作简便界面简单的游戏软件，同时要提供人机和人人这样的功能，特别是人机部分，要考虑到不同级别的用户，电脑智能不能太低需要有一定的智能下棋功能等等。所以采用α-β剪枝法算法时就是为了达到这些目标。
2.4 总体设计
这个阶段必须回答的关键问题是：“概括地说，应该如何解决这个问题？”
-5-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 首先，应该考虑几种可能的解决方案。如，目标系统的一些主要功能是用计算机自动完成还是用人工完成；如果使用计算机，那么是使用批处理方式还是人机交互方式；信息存储使用传统的文件系统还是数据库„„。通常至少应该考虑下述几类可能的方案：
低成本的解决方案。系统只能完成最必要的工作，不能多做一点额处的工作。本系统的最基本要求就是能够实现必要的操作，其他额外的一些工作在后面完成
中等成本的解决方案。这样的系统不仅能够很好地完成预定的任务，使用起来很方便，而且可能还具有用户没有具体指定的某些功能和特点。虽然用户没有提出这些具体要求，但是系统分析员根据自己的知识和经验断定，这些附加的能力在实践中将证明是很有价值的。
这个成本方案在完成上面的低成本方案后添加的。如增加保存棋局，美化界面，实现观看电脑与电脑之间的对战等功能。
高成本的“十全十美”的系统。这样的系统具有用户可能希望有的所有功能和特点。
结构设计的一条基本原理就是程序应该模块化，也就是一个大程序应该由许多规模适中的模块按合理的层次结构组织而成。总体设计阶段的第二项主要任务就是设计软件的结构，也就是确定程序由哪些模块组成以及模块间的关系。通常用层次图或结构图描绘软件的结构。
2.5 详细设计
总体设计阶段以比较抽象概括的方式提出了解决问题的办法。详细设计阶段的任务就是把解法具体化，也就是回答下面这个关键问题：“应该怎样具体地实现这个系统呢？”
这个阶段的任务还不是编写程序，而是设计出程序的详细规格说明。这种规格说明的作用很类似于其他工程领域中工程师经常使用的工程蓝图，它们应该包含必要的细节，程序员可以根据它们写出实际的程序代码。
2.6编码和单元测试
这个阶段的关键任务是根据以上阶段分析的软件模型，编写各个功能模块。
要注意的是程序的扩张性和可读性。以便以后软件的升级修改。同时要仔细的测试每个功能编写好的功能模块。人工智能技术
人工智能也就是所谓的AI(Artificial Intelligence)，它是一门很抽象的技术，-6-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 AI程序的编写不需要依据任何既定的思考模式或者规则。尤其是游戏中的AI可以完全依程序设计者本身的思考逻辑制作。我个人认为人工智能的核心应该是使计算机具有自动的处理事件的能力，而我们的所有的研究也应该围绕着这一方向。我们今天讨论的是策略类的人工智能。
策略类人工智能可以说是AI中比较复杂的一种，最常见的策略类AI游戏就是棋盘式游戏。在这类游戏中，通常的策略类AI程序都是使计算机判断目前状况下所有可走的棋与可能的获胜状况，并计算当前计算机可走棋步的获胜分数或者玩家可走棋步的获胜分数，然后再决定出一个最佳走法。本课程设计是基于AI中α-β剪枝算法的五子棋的博弈游戏，下面让我们来具体介绍一下相关的内容。算法设计
4.1α-β剪枝算法
我们的程序主要是用α-β剪枝法实现的。其基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：
(1)对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为α剪枝。
(2)对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为β剪枝。
4.2极大极小树
目前绝大部分的博弈类游戏中的人工算法都采用这种方法。假设己方为MAX点，对方则为MIN点。如果当层的节点为奇数时那么就为MAX层，同样为偶数时就为MIN层。当在MAX层时，该层的值就应该为下一个MIN层中的最大一个的值。当在MIN层是，该层的值就应该为它子层MAX的最小的一个。通俗的说就是当轮到我方时，我们就应该选择一个最有利于我们的点，预测对方可能下的最有利他方的点（相对我方来说就是最坏的点）。这样反复计算下去就能够得到根节点的最大值，这个点也就是我们最佳下棋点。在计算这个点时可以很明显的看出这是一个不断递归的过程，到达叶子节点时根据相关
-7-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 的计算规则算出该值然后向上一层不断的返回。下图中矩形代表极大层，椭圆代表极小层。
4.3深度优先搜索（DFS）
在图论中有两个很重要的遍历的方法，一个是深度优先搜索（DFS）,另外一个是广度优先搜索(BFS).这两个方法的主要区别在于下一个节点的选择。DFS首先选择它的连接节点，若它的下个节点已经全部被遍历过或者不存在的话。则向上返回到上一个节点，在遍历其他的未被访问过的点。很容易想到这要用到堆栈结构，使用一个递归来实现。而BFS则是逐个的遍历它的联接接点，将已经访问过的点放入队列中。然后再依次取出继续这个过程。
DFS遍历过程如下：
首先从A点出发访问它的领接点B，因为B的领接点C,F均未被访问过，所以B点选择C（当然也可以选择F点）作为下一个要访问的点，C点的领接点是D,F选择下个节点D，而D的邻接点只有一个E且未被访问过，就将E作为了它下个节点。这时因为E已经没有可访问的邻点，所以向上一层返回到D，发现D也已经没有可访问的点了，继续向上层返回到C，由于C的邻节点F未被访问过，那么就访问F。所以整个过程的遍历结果为：
-8-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 ABECFD。
BFS的遍历过程为ABECFD。
4.4静态估值函数
当极大极小树到达叶子节点时，需要估算一下当前盘面的值。这个就根据某个计算规则计算也即是估值函数。因为这个值是已经确定的所以称为静态。
当只有一个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物” 就给他50，否则给予10。
当两个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”给予1000，若存在一方有“阻碍物”则给以100，否则给予10。
当是活三的时候给予3600，当存在一边被堵时，就给予500。否则给予10。当是活四的时候给以500000，当一边被堵时，给予50000。否则给予10 当是五连子的时候就给予最高分1000000。最后判断是否是己方的，若不是则给予负号。
静态估值函数会很严重的影响到算法的智能，所以可根据在下棋的过程中不断的做出调整，使其更加的合理。根据一些测试，这组静态估值函数能够很好的反映棋盘重要性指标。软件设计和实现
5.1 数据结构定义
本程序定义15*15的五子棋棋盘，实现算法，在算法中采用的数据结构包括：int isChessOn[][]描述当前棋盘，0表示黑子，1表示白字，2表示无子；int pre[][]用来记录棋点的x，y坐标。
由于本课程设计是基于Java语言开发的，在Java中只能用类来表示并实现所定义的数据结构。所以下面将用类来描述相应的数据结构及算法：
public class ChessPanel extends JPanel{ private ImageIcon map;
//棋盘背景位图
private ImageIcon blackchess;
//黑子位图
private ImageIcon whitechess;
//白子位图
public int isChessOn [][];
//棋局
protected boolean win = false;
// 是否已经分出胜负
protected int win_bw;
// 胜利棋色
protected int deep = 3, weight = 7;
// 搜索的深度以及广度
public int drawn_num = 110;
// 和棋步数
int chess_num = 0;
// 总落子数目
-9-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
public int[][] pre = new int[drawn_num + 1][2];
// 记录下棋点的x,y坐标
最多(drawn_num + 1)个
public int sbw = 0;
//玩家棋色黑色0，白色1
public int bw = 0;
// 当前应该下的棋色
0：黑色(默认)，1：白色
// 边界值,用于速度优化
protected int x_max = 15, x_min = 0;
protected int y_max = 15, y_min = 0;
protected boolean able_flag = true;
// 是否选择禁手标志 0:无禁手
1:有禁手(默认
private int h;
//棋子长
private int w;
//棋子宽
private int insx;
//插入棋子的位置
private int insy;
private Point mousePoint;
//鼠标当前位置
private int winer;
//获胜方
private boolean humanhuman=false;
//是否是人人对弈
private int plast=0;
//走了几步了，public int BLACK_ONE;
//0表黑子
public int WHITE_ONE;
//1表白子
public int NONE_ONE;
//2表无子
public int N;
//棋盘边长
//---------搜索当前搜索状态极大值-//
//alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝
//beta 祖先节点得到的当前最大最小值，用于beta 剪枝。
//step 还要搜索的步数
//return 当前搜索子树极大值
protected int findMax(int alpha, int beta, int step){
int max = alpha;
if(step == 0){
return evaluate();
}
int[][] rt = getBests(1sbw)== 1)
//电脑可取胜
return 100 *(getMark(1)+ step*1000);
isChessOn[x][y] = 11);
isChessOn[x][y] = 2;
// 还原预设边界值
x_min=temp1;
x_max=temp2;
y_min=temp3;
y_max=temp4;
if(t > max)
max = t;
//beta 剪枝
if(max >= beta)
return max;
}
return max;
}
//-----------------------搜索当前搜索状态极小值--//
//alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝
//beta 祖先节点得到的当前最大最小值，用于beta 剪枝
//step 还要搜索的步数
//return 当前搜索子树极小值。
protected int findMin(int alpha, int beta, int step){
int min = beta;
if(step == 0){
return evaluate();
}
int[][] rt = getBests(sbw);
for(int i = 0;i < rt.length;i++){
int x = rt[i][0];
int y = rt[i][1];
int type = getType(x, y, sbw);
if(type == 1)
//玩家成5
return-100 *(getMark(1)+ step*1000);
// 预存当前边界值
int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max;
isChessOn[x][y] = sbw;
resetMaxMin(x,y);
int t = findMax(alpha, min, stepbwf);
if(able_flag && bwf==0 &&(type_1 == 20 || type_1 == 21 || type_1 == 22))// 禁手棋位置,不记录
continue;
rt[n][0] = i;
rt[n][1] = j;
rt[n][2] = getMark(type_1)+ getMark(type_2);
n++;
-12-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
}
// 对二维数组排序
Arrays.sort(rt, new ArrComparator());
int size = weight > n? n:weight;
int[][] bests = new int[size][3];
System.arraycopy(rt, 0, bests, 0, size);
return bests;
} //----------------------------计算指定方位上的棋型-------------------//
// x,y 方向线基准一点。
//ex,ey 指定方向步进向量。
// k 棋子颜色，0：黑色，1：白色
// 该方向上的棋子数目 以及 活度
private int[] count(int x, int y, int ex, int ey, int bwf){
// 该方向没意义,返回0
if(!makesense(x, y, ex, ey, bwf))
return new int[] {0, 1};
// 正方向 以及 反方向棋子个数
int rt_1 = 1,rt_2 = 1;
// 总棋子个数
int rt = 1;
// 正方向 以及 反方向连子的活度
int ok_1 = 0,ok_2 =0;
// 总活度
int ok = 0;
// 连子中间有无空格
boolean flag_mid1 =false,flag_mid2 = false;
// 连子中间空格的位置
int flag_i1 = 1,flag_i2 = 1;
if(isChessOn[x][y]!= 2){
throw new IllegalArgumentException(“position x,y must be empty!..”);
}
int i;
// 往正方向搜索
for(i = 1;x + i * ex < 15 && x + i * ex >= 0 && y + i * ey < 15 && y + i * ey >= 0;i++){
if(isChessOn[x + i * ex][y + i * ey] == bwf)
rt_1++;
-13-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
// 位置为空,若中空标志为false,则记为中空并继续搜索
否则,break
else if(isChessOn[x + i * ex][y + i * ey] == 2){
if(!flag_mid1){
flag_mid1 = true;
flag_i1 = i;
}
else
break;
}
// 位置为对方棋子
else
break;
}
// 计算正方向活度,，// 最后一个位置不超过边界
if(x + i * ex < 15 && x + i * ex >= 0 && y + i * ey < 15 && y + i * ey >= 0){
// 最后一个位置为空位 +1活
if(isChessOn[x + i * ex][y + i * ey] == 2){
ok_1++;
// 若是在尾部检测到连续的空格而退出搜索,则不算有中空
if(rt_1 == flag_i1)
flag_mid1 = false;
// 若中空的位置在4以下 且 棋子数>=4,则这一边的4非活
if(flag_mid1 && rt_1 > 3 && flag_i1 < 4){
ok_1--;
}
}
// 最后一个位置不是空格,且搜索了2步以上,若前一个是空格, 则不算中空,且为活的边
else if(isChessOn[x + i * ex][y + i * ey]!= bwf && i >= 2)
if(isChessOn[x +(i-1)* ex][y +(i-1)* ey] == 2){
ok_1++;
flag_mid1 = false;
}
}
// 最后一个位置是边界
搜索了2步以上,且前一个是空格, 则不算中空,且为活的边
else if(i >= 2 && isChessOn[x +(i-1)* ex][y +(i-1)* ey] == 2){
-14-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
ok_1++;
flag_mid1 = false;
}
// 往反方向搜索
for(i = 1;xi * ex < 15 && yi * ey < 15;i++){
if(isChessOn[xi * ey] == bwf)
ey >= 0){
rt_2++;
else if(isChessOn[xi * ey] == 2){
if(!flag_mid2){
flag_mid2 = true;
flag_i2 = i;
}
else
break;
}
else
break;} // 计算反方向活度
if(xi * ex >= 0 && yi * if(isChessOn[xi * ey] == 2){
ok_2++;
if(rt_2 == flag_i2)
flag_mid2 = false;
if(flag_mid2 && rt_2 > 3 && flag_i2 < 4){
ok_2--;
} } else if(isChessOn[xi * ey]!= bwf && i >= 2)
if(isChessOn[x(i-1)* ey] == 2){
ok_2++;
flag_mid2 = false;
} } else if(i >= 2 && isChessOn[x(i-1)* ey] == 2){ ok_2++;flag_mid2 = false;}
课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
//------------------分析棋子类型
// 两边都没中空,直接合成
if(!flag_mid1 &&!flag_mid2){
rt = rt_1 + rt_21;
// 判断中间的纯连子数,在5以上,直接返回;为4,返回活4;
if(temp >= 5)
return new int[] {temp, 2};
if(temp == 4)
return new int[] {temp, 2};
// 先看有没死4,再看有没活3,剩下只能是死3
if(rt_1 + flag_i21 >= 4)
return new int[] {4, 1};
if(rt_1+flag_i2-1 == 3 && ok_1 > 0 || rt_2+flag_i1-1 == 3 && ok_2 > 0)
return new int[] {3, 2};
return new int[] {3, 1};
}
// 有一边有中空
else {
// 总棋子数少于5,直接合成if(rt_1 + rt_21, ok_1 + ok_2};
// 多于5,先找成5,再找活4,剩下的只能是死4
else {
if(flag_mid1 && rt_2 + flag_i11, ok_2 + 1};
if(flag_mid2 && rt_1 + flag_i21, ok_1 + 1};
if(flag_mid1 &&(rt_2 + flag_i11 == 4 && ok_1 == 1 || flag_i2 == 4))
-16-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
}
}
} return new int[] {4, 2};
return new int[] {4, 1};5.2 程序流程图
-17-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 6 性能测试
6.1 程序执行结果
1.初始界面
2.人机博弈
3.人人博弈
-18-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
4.禁手选择
5.悔棋选择
-19-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
6.规则界面
-20-课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 7 总结
本程序是使用α-β搜索的算法完成的一个简单的五子棋博弈游戏。虽然α-βAlpha-Beta已经尽力做到细致、全面，但由于α-β搜索存在博弈树算法中普遍存在的一个缺点¬一随着搜索层数的增加，算法的效率大大下降。所以该搜索的效率还是不怎么理想，五子棋程序的“智力”也不高。因此可以在上述程序的基础上，针对五子棋本身的特点和规律对α-β搜索算法进行优化与修正，比如用启发式搜索。还有就是虽然使用了禁手思维的算法，但是这并不能平衡先后手之间的差距，依然是“先行必胜”，这个问题还有待进一步解决。
参考文献
[1] 明日科技.Java项目案例分析.清华大学出版社
[2]（美）埃克尔著 陈昊鹏 译.Java编程思想.机械工业出版社-21-
读书的好处
1、行万里路，读万卷书。
2、书山有路勤为径，学海无涯苦作舟。
3、读书破万卷，下笔如有神。
4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文
5、少壮不努力，老大徒悲伤。
6、黑发不知勤学早，白首方悔读书迟。——颜真卿
7、宝剑锋从磨砺出，梅花香自苦寒来。
8、读书要三到：心到、眼到、口到
9、玉不琢、不成器，人不学、不知义。
10、一日无书，百事荒废。——陈寿
11、书是人类进步的阶梯。
12、一日不读口生，一日不写手生。
13、我扑在书上，就像饥饿的人扑在面包上。——高尔基
14、书到用时方恨少、事非经过不知难。——陆游
15、读一本好书，就如同和一个高尚的人在交谈——歌德
16、读一切好书，就是和许多高尚的人谈话。——笛卡儿
17、学习永远不晚。——高尔基
18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向
19、学而不思则惘，思而不学则殆。——孔子
20、读书给人以快乐、给人以光彩、给人以才干。——培根
第三篇：人工智能与专家系统课程设计解读
目录
1.设计任务 1.1 设计题目 1.2设计要求 1.3设计任务 2．方案设计 2.1原理
2.2 具体设计方法 3．系统实施
3.1 系统开发环境 3.2系统主要功能介绍 3.3处理流程图 3.4 核心源程序 3.5系统运行结果 4．开发心得
4.1设计存在的问题
4.2进一步改进提高的设想 4.3经验和体会 5．参考文献 1.设计任务 1.1 设计题目
在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，该问题称八数码难题或者重排九宫问题。
1.2 设计要求
其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。
1.3 设计任务
利用人工智能的图搜索技术进行搜索，解决八数码问题来提高在推理中的水平，同时进行新方法的探讨。
2.方案设计 2.1 原理
八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。
2.2 具体设计方法
启发式搜索
由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。
启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。
3.系统实施
3.1 系统开发环境
Windows操作系统、SQL Server 200X
3.2 系统主要功能介绍
该搜索为一个搜索树。为了简化问题，搜索树节点设计如下： struct Chess//棋盘
3.4 核心源程序
#include “stdio.h” #include “stdlib.h” #include “time.h” #include “string.h” #include
const int N=3;//3*3棋盘
const int Max_Step=30;//最大搜索深度
enum Direction{None,Up,Down,Left,Right};//方向 struct Chess//棋盘 { int cell[N][N];//数码数组
int Value;//评估值
Direction BelockDirec;//所屏蔽方向
struct Chess * Parent;//父节点 };
//打印棋盘
void PrintChess(struct Chess *TheChess){ printf(“----------n”);for(int i=0;i printf(“t”); for(int j=0;j { printf(“%dt”,TheChess->cell[i][j]); } printf(“n”);} printf(“tttt差距:%dn”,TheChess->Value);} break;case Left: t_j++; if(t_j>=N) AbleMove=false; break;case Right: t_j--; if(t_j<0) AbleMove=false; break;};if(!AbleMove)//不可以移动则返回原节点 { return TheChess;} if(CreateNewChess){ NewChess=new Chess(); for(int x=0;x { for(int y=0;y NewChess->cell[x][y]=TheChess->cell[x][y]; } } else NewChess=TheChess;NewChess->cell[i][j]=NewChess->cell[t_i][t_j];NewChess->cell[t_i][t_j]=0; return NewChess;} //初始化一个初始棋盘 struct Chess * RandomChess(const struct Chess * TheChess) p=NULL;queue do{ p1=(struct Chess *)Queue1.front(); Queue1.pop(); for(int i=1;i<=4;i++)//分别从四个方向推导出新子节点 { Direction Direct=(Direction)i; if(Direct==p1->BelockDirec)//跳过屏蔽方向 continue; p2=MoveChess(p1,Direct,true);//移动数码 if(p2!=p1)//数码是否可以移动 { Appraisal(p2,Target);//对新节点估价 if(p2->Value<=p1->Value)//是否为优越节点 { p2->Parent=p1; switch(Direct)//设置屏蔽方向,防止往回推 { case Up:p2->BelockDirec=Down;break; case Down:p2->BelockDirec=Up;break; case Left:p2->BelockDirec=Right;break; case Right:p2->BelockDirec=Left;break; } Queue1.push(p2);//存储节点到待处理队列 if(p2->Value==0)//为0则,搜索完成{ p=p2; i=5; } } else { //打印 if(T){ /*把路径倒序*/ Chess *p=T; stack while(p->Parent!=NULL) { Stack1.push(p); p=p->Parent; } printf(“搜索结果:n”); while(!Stack1.empty()) { PrintChess(Stack1.top()); Stack1.pop(); } printf(“n完成!”);}else printf(“搜索不到结果.深度为%dn”,Max_Step); scanf(“%d”,T);} 3.5 系统运行结果 4.开发心得 4.1 设计存在的问题 完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。4.2 进一步改进提高的设想 可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。 2、内存泄漏。由于采用倒链表的搜索树结 05.参考文献 [1]王汝传.计算机图形学[M].北京：人民邮电出版社，1999：123－130.[2]刘榴娣，刘明奇，党长民.实用数字图像处理[M].北京：北京理工大学出版，2000：12－25..[3]丁兆海.Delphi基础教程[M].北京：电子工业出版社，1999.[4]王小华.Delphi 5程序设计与控件参考[M].北京：电子工业出版社，1999:70－120.[5]赵子江.多媒体技术基础[M].北京：机械工业出版社，2001：118－130.[6]段来盛，郑城荣，曹恒.Delphi实战演练[M].北京：人民邮政出版社，2002：80－95. 读书的好处 1、行万里路，读万卷书。 2、书山有路勤为径，学海无涯苦作舟。 3、读书破万卷，下笔如有神。 4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文 5、少壮不努力，老大徒悲伤。 6、黑发不知勤学早，白首方悔读书迟。——颜真卿 7、宝剑锋从磨砺出，梅花香自苦寒来。 8、读书要三到：心到、眼到、口到 9、玉不琢、不成器，人不学、不知义。 10、一日无书，百事荒废。——陈寿 11、书是人类进步的阶梯。 12、一日不读口生，一日不写手生。 13、我扑在书上，就像饥饿的人扑在面包上。——高尔基 14、书到用时方恨少、事非经过不知难。——陆游 15、读一本好书，就如同和一个高尚的人在交谈——歌德 16、读一切好书，就是和许多高尚的人谈话。——笛卡儿 17、学习永远不晚。——高尔基 18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向 19、学而不思则惘，思而不学则殆。——孔子 20、读书给人以快乐、给人以光彩、给人以才干。——培根 //回溯法之N皇后问题 当N>10，就有点抽了~~ /*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #include int n,stack[100]; //存当前路径 int total; //路径数 void make(int l) //递归搜索以stack[l]为初结点的所有路径 { int i,j; //子结点个数 if(l==n+1) { total=total+1; //路径数+1 for(i=1;i<=n;i++) printf(“%-3d”,stack[i]);//输出第i行皇后的列位置stack[i] printf(“n”); exit; //回溯（若试题仅要求一条路径，则exit改为halt即可） } for(i=1;i<=n;i++) { stack[l]=i;//算符i作用于生成stack[l-1]产生子状态stack[l]; if(!att(l,i)) make(l+1); } //再无算符可用，回溯 } int att(int l,int i){ int k; for(k=1;k if(abs(l-k)==abs(stack[k]-i)||i==stack[k])return 1; return 0;} int main(){ printf(“N=”); scanf(“%d”,&n); total=0;//路径数初始化为0 make(1); //从结点1出发，递归搜索所有的路径 printf(“%dn”,total); system(“pause”); return 0;} 由回溯法的算法流程可以看出，除非边界条件设置不当而导致死循环外，回溯法一般是不会产生内存溢出的。但是，回溯法亦有其致命的弱点——时间效率比数学解析法低。为了改善其时效，我们可以从下述几个方面考虑优化： 1、递归时对尚待搜索的信息进行预处理，减少搜索量； 2、尽可能减少分支（解答树的次数）； 3、增加约束条件，使其在保证出解的前提下尽可能“苛刻”； 4、在约束条件中设置限定搜索层次的槛值。 人工智能学科诞生于20世纪50年代中期，当时由于计算机的产生与发展，人们开始了具有真正意义的人工智能的研究。（虽然计算机为AI提供了必要的技术基础,但直到50年代早期人们才注意到人类智能与机器之间的联系.Norbert Wiener是最早研究反馈理论的美国人之一.最熟悉的反馈控制的例子是自动调温器.它将收集到的房间温度与希望的温度比较,并做出反应将加热器开大或关小,从而控制环境温度.这项对反馈 回路的研究重要性在于: Wiener从理论上指出,所有的智能活动都是反馈机制的结果.而反馈机制是有可 能用机器模拟的.这项发现对早期AI的发展影响很大。） 1956年夏，美国达特莫斯大学助教麦卡锡、哈佛大学明斯基、贝尔实验室申龙、IBM公司信息研究中心罗彻斯特、卡内基——梅隆大学纽厄尔和赫伯特.西蒙、麻省理工学院塞夫里奇和索罗门夫，以及IBM公司塞缪尔和莫尔在美国达特莫斯大学举行了以此为其两个月的学术讨论会，从不同学科的角度探讨人类各种学习和其他职能特征的基础，并研究如何在远离上进行精确的描述，探讨用机器模拟人类智能等问题，并首次提出了人工智能的术语。从此，人工智能这门新兴的学科诞生了。这些青年的研究专业包括数学、心理学、神经生理学、信息论和电脑科学，分别从不同角度共同探讨人工智能的可能性。他们的名字人们并不陌生，例如申龙是《信息论》的创始人，塞缪尔编写了第一个电脑跳棋程序，麦卡锡、明斯基、纽厄尔和西蒙都是“图灵奖”的获奖者。 这次会议之后，在美国很快形成了3个从事人工智能研究的中心，即以西蒙和纽威尔为首的卡内基—梅隆大学研究组，以麦卡锡、明斯基为首的麻省理工学院研究组，以塞缪尔为首的IBM公司研究组。随后，这几个研究组相继在思维模型、数理逻辑和启发式程序方面取得了一批显著的成果： （1）1956年，纽威尔和西蒙研制了一个“逻辑理论家“（简称LT）程序，它将每个问题都表示成一个树形模型,然后选择最可能得到正确结论的那一枝来求解问题，证明了怀特黑德与罗素的数学名著《数学原理》的第2章中52个定理中的38个定理。1963年对程序进行了修改，证明了全部定理。这一工作受到了人们的高度评价，被认为是计算机模拟人的高级思维活动的一个重大成果，是人工智能的真正开端。 （2）1956年，塞缪尔利用对策论和启发式搜索技术编制出西洋跳棋程序Checkers。该程序具有自学习和自适应能力，能在下棋过程中不断积累所获得的经验，并能根据对方的走步，从许多可能的步数中选出一个较好的走法。这是模拟人类学习过程第一次卓有成效的探索。这台机器不仅在1959年击败了塞缪尔本人，而且在1962年击败了美国一个州的跳棋冠军，在世界上引起了大轰动。这是人工智能的一个重大突破。 （3）1958年，麦卡锡研制出表处理程序设计语言LISP，它不仅可以处理数据，而且可以方便的处理各种符号，成为了人工智能程序语言的重要里程碑。目前，LISP语言仍然是研究人工智能何开发智能系统的重要工具。 （4）1960年纽威尔、肖和西蒙等人通过心理学实验，发现人在解题时的思维过程大致可以分为3个阶段：1。首先想出大致的解题计划；2。根据记忆中的公理、定理和解题规划、按计划实施解题过程；3.在实施解题过程中，不断进行方法和目标分析，修改计划。这是一个具有普遍意义的思维活动过程，其中主要是方法和目的的分析。（也就是人们在求解数学问题通常使用试凑的办法进行的试凑是不一定列出所有的可能性，而是用逻辑推理来迅速缩小搜索范围的办法进行的），基于这一发现，他们研制了“通用问题求解程序GPS”，用它来解决不定积分、三角函数、代数方程等11种不同类型的问题，并首次提出启发式搜索概念，从而使启发式程序具有较普遍的意义。 （5）1961年，明斯基发表了一篇名为《迈向人工智能的步骤》的论文，对当时人工智能的研究起了推动作用。 正是由于人工智能在20世纪50年代到60年代的迅速发展和取得的一系列的研究成果，使科学家们欢欣鼓舞，并对这一领域给予了过高的希望。纽威尔和西蒙在1958年曾作出以下预言： ①不出十年，计算机将成为世界象棋冠军，除非规定不让它参加比赛； ②.不出十年，计算机将发现并证明那时还没有被证明的数学定理； ③.不出十年，计算机将谱写出具有较高美学价值并得到评论家认可的乐曲； ④不出十年，大多数心理学家的理论将采用计算机程序来形成。 非常遗憾的是，到目前为止，这样的预言还没有一个得到完全的实现，人工智能的研究状况比纽威尔和西蒙等科学家的设想要复杂和艰难的多。事实上，到了20世纪70年代初，人工智能在经历一段比较快速的发展时期后，很快就遇到了许多问题。这些问题主要表现在： （1）1965年鲁宾逊发明了归结（消解）原理，曾被认为是一个重大的突破，可是很快这种归结法能力有限，证明两个连续函数之和还是连续函数，推证了十万步竟还没有得证。 （2）塞缪尔的下棋程序，赢得了周冠军后，没能赢全国冠军。 （3）机器翻译出了荒谬的结论。如从英语→俄语→英语的翻译中，又一句话：“The spirit is willing but the flesh is weak”(心有余而力不足)，结果变成了”The wine is good but the meat is spoiled”(酒是好的，肉变质了)，闹出了笑话。 （4）大脑约有10的15次方以上的记忆容量，此容量相当于存放几亿本书的容量，现有的技术条件下在机器的结构上模拟人脑是不大可能的。 （5）来自心理学、神经生理学、应用数学、哲学等各界的科学家们对人工智能的本质、基本原理、方法及机理等方面产生了质疑和批评。 由于人工智能研究遇到了困难，使得人工智能在20世纪70年代初走向低落。但是，人工智能的科学家没有被一时的困难所吓倒，他们在认真总结经验教训的基础上，努力探索使人工智能走出实验室，走向实用化的新路子，并取得了令人鼓舞的进展。特别是专家系统的出现，实现了人工智能从理论研究走向实际应用，从一般思维规律探索走向专门知识应用的重大突破，是人工智能发展史上的重大转折，将人工智能的研究推向了新高潮。下面是几个又代表性的专家系统： （1）1968年斯坦福大学费根鲍姆教授和几位遗传学家及物理学家合作研制了一个化学质谱分析系统（DENDARL），该系统能根据质谱仪的数据和核磁谐振的数据，以及有关化学知识推断有机化合物的分子结构，达到了帮助化学家推断分子结构的作用。这是第一个专家系统，标志着人工之能从实验室走了出来，开始进入实际应用时代。 （2）继DENDARAL系统之后，费根鲍姆领导的研究小组又研制了诊断和治疗细菌感染性血液病的专家咨询系统MYCIN。经专家小组对医学专家、实习医师以及MYCIN行为进行正式测试评价，认为MYCIN的行为超过了其他所有人，尤其在诊断和治疗菌血症和脑膜炎方面，显示了该系统作为临床医生实际助手的前途。从技术的角度来看，该系统的特点是：1。使用了经验性知识，用可信度表示，进行不精确推理。2.对推理结果具有解释功能，时系统是透明的。3.第一次使用了知识库的概念。正是由于MYCIN基本解决了知识表示、知识获取、搜索策略、不精确推理以及专家系统的基本结构等重大问题（是怎样解决的呢？），对以后的专家系统产生了很大的影响。 （3）1976年，斯坦福大学国际人工智能中心的杜达等人开始研制矿藏勘探专家系统PROSPECTOR，它能帮助地质学家解释地质矿藏数据，提供硬岩石矿物勘探方面的咨询，包括勘探测评，区域资源估值，钻井井位选择等。该系统用语义网络表示地质知识，拥有15中矿藏知识，采用贝叶斯概率推理处理不确定的数据和知识。PROSPECTOR系统于1981年开始投入实际使用，取得了巨大的经济效益。例如1982年，美国利用该系统在华盛顿发现一处矿藏，据说实用价值可能超过1亿美元。 （4）美国卡内基—梅隆大学于20世纪70年代先后研制了语音理解系统HEARSAY-I加入HEARSAY-II，它完成从输入的声音信号转换成字，组成单词，合成句子，形成数据库查询语句，再到情报数据库中去查询资料。该系统的特点是采用“黑板结构”这种新结构形式，能组合协调专家的知识，进行不同抽象级的问题求解。 在这一时期，人工智能在新方法、程序设计语言、知识表示、推理方法等方面也取得了重大进展。例如70年代许多新方法被用于AI开发,著名的如Minsky的构造理论.另外David Marr提出了机器视觉方面的新理论,例如,如何通过一副图像的阴影,形状,颜色,边界和纹理等基本信息辨别图像.通过分析这些信息,可以推断出图像可能是什么，法国马赛大学的柯尔麦伦和他领导的研究小组于1972年研制成功的第一个PROLOG系统，成为了继LISP语言之后的另一种重要的人工智能程序语言；明斯基1974年提出的框架理论；绍特里夫于1975年提出并在MYCIN中应用的不精确推理；杜达于1976年提出并在PROSPECTOR中应用的贝叶斯方法；等等 人工智能的科学家们从各种不同类型的专家系统和知识处理系统中抽取共性，总结出一般原理与技术，使人工智能又从实际应用逐渐回到一般研究。围绕知识这一核心问题，人们重新对人工智能的原理和方法进行了探索，并在知识获取、知识表示以及知识在推理过程中的利用等方面开始出现一组新的原理、工具和技术。1977年，在第五届国际人工智能联合会（IJCAI）的会议上，费根鲍姆教授在一篇题为《人工智能的艺术：知识工程课题及实例研究》的特约文章中，系统的阐述了专家系统的思想，并提出了知识工程（KnowledgeEngineering）的概念。费根鲍姆认为，知识工程是研究知识信息处理的学科，它应用人工智能的原理和方法，对那些需要专家知识才能解决的应用难题提供了求解的途径。恰当的运用专家知识的获取、表示、推理过程的构成与解释，是设计基于知识的系统的重要技术问题。至此，围绕着开发专家系统而开展的相关理论、方法、技术的研究形成了知识工程学科。知识工程的研究使人工智能的研究从理论转向应用，从基于推理的模型转向基于知识的模型。 为了适应人工智能和知识工程发展的需要，在政府的大力支持下，日本于1982年开始了为期10年的“第五代计算机的研制计划”，即“知识信息处理计算机系统KIPS”，总共投资4.5亿美元。它的目的是使逻辑推理达到数值运算那样快。日本的这一计划形成了一股热潮，推动了世界各国的追赶浪潮。美国、英国、欧共体、苏联等都先后制订了相应的发展计划。随着第五代计算机的研究开发和应用，人工智能进入一个兴盛时期，人工智能界一派乐观情绪。 然而，随着专家系统应用的不断深入，专家系统自身存在的知识获取难、知识领域窄、推理能力弱、只能水平低、没有分布式功能、实用性差等等问题逐步暴露出来。日本、美国、英国和欧洲所制订对那些针对人工智能的大型计划多数执行到20世纪80年代中期就开始面临重重困难，已经看出达不到预想的目标。进一步分析便发现，这些困难不只是个别项目的制订又问题，而是涉及人工智能研究的根本性问题。总的来讲是两个问题：一是所谓的交互（Interaction）问题，即传统方法只能模拟人类深思熟虑的行为，而不包括人与环境的交互行为。另一个问题是扩展（Scaling up）问题，即所谓的大规模的问题，传统人工智能方法只适合于建造领域狭窄的专家系统，不能把这种方法简单的推广到规模更大、领域更宽的复杂系统中去。这些计划的失败，对人工智能的发展是一个挫折。 尽管经历了这些受挫的事件,AI仍在慢慢恢复发展.新的技术在日本被开发出来,如在美国首创的模糊逻辑,它可以从不确定的条件作出决策;还有神经网络,被视为实现人工智能的可能途径.1982年后，人工神经网络像雨后春笋一样迅速发展起来，给人们带来了新的希望。人工神经网络的主要特点是信息的分布存储和信息处理的并行化，并具有自组织自学习能力，这使人们利用机器加工处理信息有了新的途径和方法，解决了一些符号方法难以解决的问题，使人工智能的学术界兴起了神经网络的热潮。1987年美国召开了第一次神经网络国际会议，宣布新学科的诞生。1988年以后，日本和欧洲各国在神经网络方面的投资逐步增加，促进了该领域的研究。但是随着应用的深入，人们又发现人工神经元网络模型和算法也存在问题。 20世纪80年代末，以美国麻省理工学院布鲁克斯（R.A.Brooks）教授为代表的行为主义学派提出了“无须表示和推理”的智能，认为智能只在与环境的交互中表现出来，并认为研制可适应环境的“机器虫”比空想智能机器人要好。以后，人工智能学术界充分认识到已有的人工智能方法仅限于在模拟人类智能活动中使用成功的经验知识处理简单的问题，开始在符号机理与神经网机理的结合及引入Agent系统等方面进一步开展研究工作。20世纪90年代，所谓的符号主义、连接主义和行动主义3种方法并存。对此，中国学者认为这3种方法各有优缺点，他们提出了综合集成的方法，即不同的问题用不同的方法来解决，或用联合（混合、融合）的方法来解决，再加上人工智能系统引入交互机制，系统的智能水平将会大为提高。 总而言之，尽管人工智能的发展经历了曲折的过程，但它在自动推理、认知建模、机器学习、神经元网络、自然语言处理、专家系统、智能机器人等方面的理论和应用上都取得了称得上具有“智能”的成果。许多领域将知识和智能思想引入到自己的领域，使一些问题得以较好的解决。应该说，人工智能的成就是巨大的，影响是深远的。 读书的好处 1、行万里路，读万卷书。 2、书山有路勤为径，学海无涯苦作舟。 3、读书破万卷，下笔如有神。 4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文 5、少壮不努力，老大徒悲伤。 6、黑发不知勤学早，白首方悔读书迟。——颜真卿 7、宝剑锋从磨砺出，梅花香自苦寒来。 8、读书要三到：心到、眼到、口到 9、玉不琢、不成器，人不学、不知义。 10、一日无书，百事荒废。——陈寿 11、书是人类进步的阶梯。 12、一日不读口生，一日不写手生。 13、我扑在书上，就像饥饿的人扑在面包上。——高尔基 14、书到用时方恨少、事非经过不知难。——陆游 15、读一本好书，就如同和一个高尚的人在交谈——歌德 16、读一切好书，就是和许多高尚的人谈话。——笛卡儿 17、学习永远不晚。——高尔基 18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向 19、学而不思则惘，思而不学则殆。——孔子 20、读书给人以快乐、给人以光彩、给人以才干。——培根第四篇：回溯法之N皇后问题(C语言)
第五篇：人工智能发展史解读
点击咨询 