人工智能课程设计报告学号：20091000608姓名：王沙沙班级：191091指导老师：赵老师2011年10月142/23目录1．N皇后问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1需求分析，设计⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1设计表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯1运行结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2用户手册即测试数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2结论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯5主要算法代码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯52罗马尼亚问题⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯9需求分析，设计⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯9设计表示，详细设计⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯9用户手册⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11运行结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11主要算法代码⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯123.实习心得⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯213/231N皇后问题1．问题描述、需求分析在N*N的棋盘上分布N个皇后，其中N个皇后不能在同一行同一列，也不能出现在同一对角线上，此时N个皇后不会相互攻击。程序需能手动输入皇后个数，并分别采用回溯法、爬山法、遗传法得出皇后的分布情况，输出皇后的位置即棋盘。2．设计思想2.1形式化N个皇后的位置可用一个N维数组表示，如921543⋯⋯，意思是第一个皇后在第一列的第9行。2.2程序模块CreatIndividual()函数用于产生一组表示皇后不在同一行也不再同一列的的一位数组，即产生一组互不相等的0~N之间的整数，便于快速求解。IsLegal()函数用于判断新放置的皇后是否合法，在回溯法中用到。AttackQueenNum()用于计算整个棋盘的攻击皇后个数，相当于一个评价函数，在爬山法和遗传法中用到；Find()回溯法求解函数ClimbHill()爬山法求解函数；GA()遗传算法求解函数；（1）函数调用关系图如下：（2）函数接口规格说明：下图中的箭头指向表示为被指向函数所用2.3详细设计a:CreatIndividual(int*A,intQueenNum)：以当时时间为种子循环产生随机数，为了使得产生的随机数都不想等，设计集合S[N]并初始化为0，表示还没有产生一个皇后，当产生的皇后不在S[N]中即S[N]！=1时将S[n]置为1，接着产生下一个皇后，如此循环便产生一组互不相等的值。b:IsLegal(int*A,intt)此函数用于判断第t列的皇后是否合法，即有CreatIndividual()AttackQueenNum()Find()IsLegal()主函数GA()ClimbHill()4/23没有皇后在同一行、同一列，同一对角线上，并返回true或者false。c:AttackQueenNum(int*A,intQueenNum)循环调用IsLegal()函数对攻击数进行累加并返回其值，此函数作为棋盘的评价函数。d:Find(int*A,intk,intQueenNum,longbeginTime)回溯法求解，因为回溯法的每一层都是for循环，所以不能单纯的用break语句进行控制，因为即使当前层循环停止了，程序还会继续执行上一层的循环，所以将起始时间作为参数进行传递，以便求出算法执行时间，然后用exit（0）语句终止程序，所以要将回溯法放在其它两个算法的后面执行。e:ClimbHill(int*A,intQueenNum)：由于在产生一个棋盘个体的时候所有的皇后就不在同一行同一列，所以在爬山法中只对棋盘的列进行交换，这样即使再怎么交换所有的皇后还是不在同一行同一列，但在交换的时候需要调用AttackQueenNum()函数进行棋盘的评价，如果交换前的攻击数大于交换后的攻击数则进行交换，否则与下一列进行交换比较，如此循环直到找出解。f:GA()3．用户手册运行程序，输入皇后个数N，各种算法得到的皇后分布情况、耗时自动显示；4．测试数据及测试结果分别测试4，20,30,50皇后，测试结果如下：程序运行结果：4皇后运行结果20皇后运行结果如下5/236/2330皇后运行结果如下：7/2350皇后运行结果如下由于50皇后的棋盘稍大，这里只给出运行时间结论：根据输入皇后个数递增的运行结果可以看出爬山法的速度是相当快的，在皇后个数比较少时回溯法的速度要快于遗传算法，而当皇后个数比较多时，回溯法的深度搜索明显慢于遗传算法。主要算法程序代码：1：boolIsLegal(int*A...
