人工智能--N皇后问题回溯法爬山算法的实现及性能分析.doc

N皇后问题爬山法和回溯法的实现及性能分析 云南大学信息学院 专业：计算机软件与理论 目录 一、N皇后问题 4 1.问题描述 4 2. 数据结构 4 二、爬山算法 4 1. 爬山算法一般介绍 4 2. 爬山算法的伪代码 5 3. 算法评价 5 三、回溯法 5 1. 回溯法一般介绍 5 2. 回溯法的伪代码 5 3. 算法评价 6 四、算法实现及性能比较 6 五、两种算法性能分析 7 六、结论 8 七、参考文献 8 附录 9  一、N皇后问题 1.问题描述 （1）n皇后问题在格的上摆放个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线分别用回溯法（递归）、爬山法和GA算法求解n皇后问题。要求：输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率。列表给出结果。逻辑结构线性结构数组存储结构（物理结构）顺序存储结构爬山法是指从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。经过迂回前进,最终达到解决问题的总目标。如果我们把目标函数的几何图形看成一个山峰,那么点的直接移动就像人在爬山,选择方向,逐步向山顶移动。一个描述数据库变化的单极值，且使极值对应目标状态；选取使函数值增长最大的那条规则作用于数据库；重复上步，直到没有规则使函数值继续增爬山法是一种局部有哪些信誉好的足球投注网站算法，也属一种启发式方法。但它一般只能得到局部最优，并且这种解还依赖于起始点的选取。解多变量无约束最优化问题的一类方法通过点的直接移动产生的目标值有所改善的点,经过这样的移动,逐步到达使目标函数最优的点。爬山算法较简单，效率高，处理多约束大规模问题时往往不能得到较好的解。回溯法是一种选优有哪些信誉好的足球投注网站法，按选优条件向前有哪些信誉好的足球投注网站，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。 2. 回溯法的伪代码 回溯法基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。皇后问题，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了 图4-1.部分测试结果 五、两种算法性能分析 在测试中我们根据不同的皇后规模用例进行测试，并给出了各个规模的不同算法所用的运行时间（单位ms）。表1为不同的皇后规模测试后得到的运行时间数据。 规模 时间 10 50 100 150 200 250 爬山法(ms) 42.0564 236.404 670.458 2481.45 6502.89 13210.3 回溯法(ms) 24.3441 436.536 1032.13 5624.18 8359.02 26567.6 表1 不同的皇后规模运行时间（单位ms） 为了直观起见，根据实验数据画出不同的皇后规模以及不同算法的时间变化趋势图如图5-1所示： 图5-1两种算法用时变化趋势图 六、结论 爬山法是一种始终都比较快的算法，它的运行时间与皇后是个数没有必然的联系，而且在n很大时，它显现出来运行时间短，效率高的优势，但它的缺点是会出现山脊、高原，86%的时间会卡住。总的来说，爬山算法较简单，效率高，处理多约束大规模问题时往往不能得到较好的解。1．《Artificial intelligence :;a modern approach 人工智能 : 一种现代方法》 作者：Russell, Stuart J. 出版社：清华大学出版社 2.百度百科网站 附录 /************************************************************************/ /* 爬山法解决N皇后问题 */ /************************************************************************/ #include stdio.h #include stdlib.h #include iostream #include iterator #include vector #include time.h #includewindows.h using namespace std; typedef vectorint CollisionList_t; void print_row_mark(int N) {