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

n皇后问题登山法和回溯法的实现和性能分析云南大学信息学院专家：计算机软件和理论目录一、n皇后问题41 .问题的说明42 .数据结构4二、登山算法41 .登山算法一般介绍42 .登山算法的伪代码53 .算法评估5三、回溯法51 .回溯法一般介绍52 .回溯法伪代码53 .算法评估6四、算法的实现和性能比较6五、两种算法的性能分析7六、结论8七、参考文献8附录9一、n皇后问题1 .问题的说明(1)n皇后问题：在n*n格的国际象棋上配置n个皇后，使其不能相互攻击，即任何皇后都不能在同一行、同一列或同一斜线上(2)分别使用回溯法(递归)、登山法、GA算法来解决n皇后问题。 要求：输入n，比较在执行时间内几种算法为相同规模问题时的求解效率。 结果显示在列表中。2 .数据结构1、逻辑结构：线性结构包括排列等。2 .记忆结构(物理结构):顺序记忆结构。二、登山算法1 .登山算法的一般介绍登山法是指从当前节点与周围相邻节点的值进行比较。 如果当前节点是最大的，则将当前节点作为最大值(山的顶点)返回，相反，通过用最高的相邻节点替换当前节点，实现攀登山的目的。 这样循环直到达到最高点。每次选择与目标节点的启发函数值最小的节点，经过迂回前进，最终实现问题解决的总目标。 如果我们把目标函数的几何图形看作山，点的直接移动就像人爬山，选择方向，向山顶移动一样。 爬山法建立了描述数据库变化的单极值函数，选择最大限度增加需要使极值与目标状态对应的函数值的规则来作用于数据库。重复前面的步骤直到没有增加函数值的规则为止。登山法是一种局部搜索算法，也是一种启发式方法。 然而，通常只能获得局部最佳解，这也取决于起点的选择。 以一种解决多变量无约束优化问题的方式，在由点的直接移动引起的目标值得到改善的点经由这种移动而到达优化目标函数的点。在登山法中，h表示相互攻击女王的对数，用它生成启发函数。2 .登山算法的伪代码登山函数(问题)是局部极大值的状态返回输入问题，输入问题局部变量：当前节点。邻居，节点。当前生成的节点(初始状态问题 )循环下去邻居是现在价值最高的接班人如果值邻居值当前，则返回到状态当前现在的邻居3 .算法评估登山法的缺点：出现山脊、高原，堵塞了86%的时间，但登山算法比较简单，皇后人数多时效率最高，处理大规模问题时，不能得到很好的解。三、倒退法1 .回溯法的一般介绍回溯法是择优搜索法，按照择优条件向前搜索，达到目标。 但是，发现某一步时，如果发现最初的选择不优秀或没有达到目标，就后退一步重新选择，如果不通过这条路就返回的技术是后退法。2 .回溯法伪代码回溯法的基本思想是，走一条路，走一条路，不走就退一条路，换一条路试试。 关于n皇后的问题，第一步是依次放置女王，下一步是按要求放置第二个女王，如果位置不符合要求，就改变第一个女王的位置，再次放置第二个女王的位置，直到找到符合条件的位置为止，以目标状态结束。3 .算法评估回溯法女王数量少，占优势，其速度非常快，但随着女王数量的增加，回溯法不实用，n=28时，回溯法不能很好地解决n女王的问题。四、算法的实现和性能比较这里，通过c语言实现了各种排序算法(源代码参照附录)，程序执行环境为windows 7，使用的编译器为vs2010。实验分别用不同女王规模的用例进行了测试。女王的规模设定为10，50，100，150，200，250实验结果如图4-1所示图4-1 .测试结果的一部分五、两种算法的性能分析测试基于女王规模的用例进行了测试，显示了不同规模的算法的执行时间(单位ms )。 表1是测试不同皇后大小后得到的执行时间数据。规模时间1050100150200250登山法(毫秒)42.0564236.404670.4582481.456502.8913210.3回溯法(毫秒)24.3441436.5361032.135624.188359.0226567.6表1不同皇后尺寸的执行时间(单位ms )为了直观地考虑，根据实验数据不同的女王规模和不同算法的时间变化倾向图如图5-1所示图5 -一种算法用时变化趋势图六、结论登山法是一种非常快的算法，其运行时间和女王没有必然的联系，而且n大时运行时间短，表现出效率优势，但其缺点是出现山脊、高原，堵塞了86%的时间。 总体上，登山算法简单，比较快，皇后人数多时效率最高，处理大规模问题时往往得不到好的解。回溯法女王数量少，占优势，其速度非常快，但随着女王数量的增加，回溯法不实用，n=50时，回溯法不能很好地解决n女王的问题。总而言之，背轨在n值小时效率最高，在n值大时不能解决背轨法，此时，爬山法的效率最高，与n值没有必然的联系。七、参考文献1. Artificial intelligence :;a modern approach 人工智能 : 一种现代方法作者：罗素，Stuart J .出版社：清华大学出版社2 .百度百科网站附录我要去找你，我要去找你，我要去找你。用登山法解决n皇后问题*/我要去找你，我要去找你，我要去找你。#include#include#include#include#include#include#includeusing namespace std；typedef vector CollisionList_t；void print_row_mark(int N )举止PC (K 15 )举止返回；以下for (int i=0； i5 )举止返回；以下/cout|；for (int i=0； (icol.size () )/取消之前的交换swap(chessmanrow1、chessmanrow2 )；以下else cl=new_cl；以下return new_cl.size ()；以下int choose _ next _ state (int * ches man，int N，CollisionList_t cl )举止int old_collision=cl.size ()；int new_collision；int row1=-1；int row2=-1；/最后只优化一个冲突解将if (cl.size()=1) )for (int i=0； i old_collision；return new_collision以下/用随机登山法寻找n皇后问题的解int queen_solution(int N )举止int* chessman=new intN；int max_tries=N*N；int max_steps=N*N；整数=0；while (tries max_tries) )树；int steps=0；int collision=0；CollisionList_