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

1N皇后问题爬山法和回溯法的实现及性能分析云南大学信息学院专业：计算机软件与理论2目录一、N皇后问题............................................................................................................31.问题描述.......................................................................................................................................32.数据结构.....................................................................................................................................3二、爬山算法...............................................................................................................31.爬山算法一般介绍......................................................................................................................32.爬山算法的伪代码......................................................................................................................43.算法评价.....................................................................................................................................4三、回溯法...................................................................................................................41.回溯法一般介绍..........................................................................................................................42.回溯法的伪代码..........................................................................................................................43.算法评价.....................................................................................................................................5四、算法实现及性能比较...........................................................................................5五、两种算法性能分析...............................................................................................6六、结论.......................................................................................................................7七、参考文献...............................................................................................................7附录...............................................................................................................................83一、N皇后问题1.问题描述（1）n皇后问题：在n*n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，（2）分别用回溯法（递归）、爬山法和GA算法求解n皇后问题。要求：输入n，并用运行时间比较几种算法在相同规模的问题时的求解效率。列表给出结果。2.数据结构1、逻辑结构：用到线性结构包括数组等。2、存储结构（物理结构）：顺序存储结构。二、爬山算法1.爬山算法一般介绍爬山法是指从当前的节点开始，和周围的邻居节点的值进行比较。如果当前节点是最大的，那么返回当前节点，作为最大值(既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。每次都选择是与目标结点启发函数值最小的那个结点，经过迂回前进,最终达到解决问题的总目标。如果我们把目标函数的几何图形看成一个山峰,那么点的直接移动就像人在爬山,选择方向,逐步向山顶移动。爬山法需要建立一个描述数据库变化的单极值函数，且使极值对应目标状态；选取使函数值增长最大的那条规则作用于数据库；重复上步，直到没有规则使函数值继续增长。爬山法是一种局部搜索算法，也属一种启发式方法。但它一般只能得到局部最优，并且这种解还依赖于起始点的选取。它是一种解多变量无约束最优化问题的一类方法，通过点的直接移动产生的目标值有所改善的点,经过这样的移动,逐步到达使目标函数最优的点。在爬山法中，h表示相互攻击的皇后的对数，用它来生成启发函数。42.爬山算法的伪代码爬山函数（问题）是局部极大值的一种状态返回输入问题，一个问题局部变量：当前，一个节点。邻居，一个节点。[问题]）循环做如果值[邻居]≤价值[当前]，然后返回状态[当前]3.算法评价爬山法的缺点：会出现山脊、高原，86%的时间会卡住；但是爬山算法较简单，在皇后的个数较多时体现出来效率最高，处理多约束大规模问题时往往不能得到较好的解。三、回溯法1.回溯法一般介绍回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。2.回溯法的伪代码回溯法基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。对于n皇后问题，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有符合位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了，在目标状态终止。53.算法评价回溯法在皇后数目较小的，很占优势，它的速度非常的快，但随着皇后数目的增加，回溯法显得很不实用，在n=28时，用回溯法已不能较好的解决n皇后问题。四、算法实现及性能比较这里通过c++语言来实现各种排序算法（源码见附录），程序运行环境为windows7，所用编译器为vs2010。实验分别以不同的皇后规模用例进行测试。皇后规模设置为10,50,100,150,200,250实验部分结果如图4-1：6图4-1.部分测试结果五、两种算法性能分析在测试中我们根据不同的皇后规模用例进行测试，并给出了各个规模的不同算法所用的运行时间（单位ms）。表1为不同的皇后规模测试后得到的运行时间数据。规模时间1050100150200250爬山法(ms)42.0564236.404670.4582481.456502.8913210.3回溯法(ms)24.3441436.5361032.135624.188359.0226567.6表1不同的皇后规模运行时间（单位ms）为了直观起见，根据实验数据画出不同的皇后规模以及不同算法的时间变化趋势图如图5-1所示：7050100150200250-20000200040006000800010000120001400016000180002000022000240002600028000时间(ms)N爬山法回溯法图5-1两种算法用时变化趋势图六、结论爬山法是一种始终都比较快的算法，它的运行时间与皇后是个数没有必然的联系，而且在n很大时，它显现出来运行时间短，效率高的优势，但它的缺点是会出现山脊、高原，86%的时间会卡住。总的来说，爬山算法较简单，也比较快，在皇后的个数较多时体现出来效率最高，处理多约束大规模问题时往往不能得到较好的解。回溯法在皇后数目较小的，很占优势，它的速度非常的快，但随着皇后数目的增加，回溯法显得很不实用，在n=50时，用回溯法已不能较好的解决n皇后问题。总的来说，回溯在n值很小时，效率最高，在n值很大时，回溯法不能再解决，此时，爬山法的效率最高，且与n值没有必然的联系。七、参考文献1．《Artificialintelligence:;amodernapproach人工智能:一种现代方法》作者：Russell,StuartJ.出版社：清华大学出版社2.百度百科网站8附录/************************************************************************//*爬山法解决N皇后问题*//************************************************************************/#includestdio.h#includestdlib.h#includeiostream#includeiterator#includevector#includetime.h#includewindows.husingnamespacestd;typedefvectorintCollisionList_t;voidprint_row_mark(intN){if(N15){return;}for(inti=0;iN;++i){cout+---;}cout+endl;}voidprint_row(intN,intfill){if(N5){return;}//cout|;for(inti=0;iN;++i){/*if(i==fill)coutX;elsecout0;*/cout|((i==fill)?'X':'');}cout|endl;9print_row_mark(N);}//皇后位置的表示方法://使用数组chessman[N]来表示N个皇后的位置//第i个皇后chessman[i]的下标i表示其行所在的位置，//chessman[j]表示其列的位置。//一个四皇后问题的表示方法如下所示：//(0,1)(1,3)(2,0)(3,2)//+---+---+---+---+//||X|||//+---+---+---+---+//||||X|//+---+---+---+---+//|X||||//+---+---+---+---+//|||X||//+---+---+---+---+//voidprint_chessboard(int*chessman,intN){for(i