资源描述：
《八皇后问题的最佳解决方案 123》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、陕西师大计科院10级《算法设计与分析》课程论文集八皇后问题的最佳解决方案（陕西师范大学计算机科学学院10级计科一班，西安，710062）摘要：回溯法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试中找问题的解，当不满足求解条件就”回溯”(返回)，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法,其采用了一种“走不通就掉头”的思想，作为其控制结构。本文主要描述递归回溯与非递归回溯，并用这两个算法解决经典的“八皇后”问题,找出该问题的最佳解决方案。关键词：回溯法；递归；非递归；深度
2、优先搜索；约束条件；枚举EightqueenproblemthebestsolutionZhaoYa-wen,Zhao-Shanshan,Zhongmei,DuanXi-juan（SchoolofComputerScience,ShanxiNormalUniversity,Xi’an,710062）Abstract:Backtrackingisactuallyasimilarenumeratedsearchtrymethod,Itisthethemeinthesearchtofindthesol
3、utionofproblems.,Whennotsolvingconditionis"back"(return),Trytheotherpath.Backtrackingalgorithmistryingtosearchalgorithmisthemostbasicanalgorithm,Theuseofa"walkimpassabilitywillturn"thought,Asitscontrolstructure.Thispapermainlydescriberecursivebackand
4、therecursiveback,Andthetwoalgorithmstosolvetheclassic"eightqueen",Tofindthebestsolutiontotheproblem.Keywords:Backtracking;Recursive;Therecursive;Depthfirstsearch;Constraintconditions;enumeration.1引言在用回溯算法解决问题中每向前走一步都有很多路需要选择，但当没有决策的信息或决策的信息不充分时，只好尝试某
5、一路线向下走，到一定程度后得知此路不通时，再回溯到上一步尝试其他路线；当然再尝试成功时，则问题得解算法结束。回溯法属于图的搜索算法中的深度优先搜索，通常深度优先搜索法不全保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间最少。回溯法在算法思想上是相同的，用深度优先搜索，但是算法分析课程上，我们要考虑算法的时间、空间复杂度，以及它的实用性，即能较好地解决问题。所以，回溯法也是一样的，在满足约束条件和不满足约束条件进行回溯是不一样的，
6、这就是我们要概述的递归回溯算法和非递归回溯算法，2问题概述八皇后问题：要在8*8的国际象棋棋盘中放八个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。如图2-1为一种方案，求所有的解。5陕西师大计科院10级《算法设计与分析》课程论文集图2-13求解八皇后问题的常用算法贪心算法是一种改进了的分级处理算法，在这里，八皇后的贪心选择的依据就是把下一个皇后放在数字最小的格子里，同样可以采用，适用范围广，直观的蛮力算法，当然最经典的解决八皇后问题的算法是回溯法，这
7、里我们主要介绍加约束条件的枚举算法，非递归回溯算法，递归回溯算法。逐一设计算法，三者进行比较，进行算法的时间、空间复杂度评价，找出最优算法，推而广之，寻找出用以解决n皇后的问题的算法。3.1模型建立设八个皇后为xi,她们分别在第i行(i=1,2,3,4……,8),这样问题的解空间,xi就是一个皇后所在列的序号，为n元一维向量(x1,x2,x3,x4,x5,x6,x7,x8),搜索空间是1≤xi≤8（i=1，2，3，4……，8），共88(每个xi均有8种位置)个状态。约束条件是八个皇后：（1,x1
8、）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)使得(i,xi)不在同一行、同一列和同一对角线上。如图3-1为一种解。图3-1八皇后问题的一种解虽然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为前面已经说明，回溯法采用的是“走不通就掉头”的策略，而形如(1,1,x3,x4,x5,x6,x7,x8)的状态共有86个，由于1，2号皇后在同一列不满足约束条件，回溯后这86个状态是不会搜索的。如图3-2，便是一种不可搜索的情况。5陕西师大计
