回溯法解决n皇后问题

《回溯法解决n皇后问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、n溯法解决n皇后问题回溯法是一种选优搜索法，也称为试探法，按照深度优先搜索的策略，从根结点出发深度探索解空间树。回溯算法解决问题的一般步骤。八皇后问题以及8-皇后问题的推广n-皇后问题，等于要求N个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。关键词：回溯法、八皇后、显约束、显约束、树结构一.回溯法回溯法是一种选优搜索法，也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当0前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解

2、过程，回溯到上一步寻找其他求解路径。通过对闷题的归纳分析，找出求解问题的一个线索，沿着这一线索往前试探，若试探成功，即得到解；若试探失败，就逐步往回退，换其他路线再往前试探。因此，回溯法可以形象地概括为“向前走，碰壁回头”。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往使用回溯法。二.回溯的一般方法下面简要阐述回溯的一般方法。回溯求解的问题P，通常要能表达为：对于已知的由n元组（xl，x2，，，，xn）组成的一个状态空间E={（xl,x2,xn）

3、xi^si,i=l,2,n},给定关于n元粗中的一个分量的一个约朿集D,要求E中满足D的企部约束

4、条件的所有n元组。其中si是分量xi的定义域，且

5、si

6、有限，i=l,2，，，,n。称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是穷举法，上面已经作了介绍，即对E屮的所有n元组逐一地检验其是否满足D的全部约束，若满足，则为问题P的一个解。显然，其计算量是相当大的。对于许多问题，所给定的约束集D具有完备性，即i元组&1，*2，，，，*9满足0中仅涉及到xl,x2,，，,xi的所有约來，意味着j（j〈i）元组（xl,x2,，，，xj）—定也满足1）屮仅涉及到xl，x2,，，，xj的所有约束，i=l,2,，，,n。换句话说，只要存在0

7、使得（xl,x2,，，,xj）违反D中仅涉及到xl,x2,，，,xj的约束之一，则以（xl,x2,，，，xj）为前缀的任何n元组（xl,x2,，，，xj,xj+1，，，，xn）也一定违反D中仅涉及到xl,x2,,,，xj的一个约朿，n彡i〉j。因此，对于约束集D具有完备性的问题P,—旦检测断定某个j元组（xl,x2,,，,xj）违反D中仅涉及xl,x2,„，xj的一个约來，就可以肯定，以（xl,x2,，，，xj）为前缀的任何n元组（xl，x2,，，，xj,xj+1，，，,xn）都不会是问题P的解，因而就不必去搜索它们，即省略了对部分元素（xj+1，，，，xn）的操作与测试。回溯

8、法正是针对这类问题。三.基本思想在包含问题的所有解的解空间树屮，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求闷题的所有解时，要回溯到根，且根结点的所有可行的子树都要己被搜索遍才结朿。而若使用冋溯法求任一个解时，只要搜索到问题的一个解就可以结束。回溯算法解决问题的一般步骤：1、定义一个解空间，它包含问题的解。2、利用适于搜索的方法组织解空间。3、利用深度优先法搜索解空间。4、利用限界函数避免移动到不可能产生解的子空间。问

9、题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。问题的解向量：回溯法希望一个问题的解能够表示成一个n元式（xl,x2,…,xn）的形式。显约束：对分量xi的取值限定。隐约朿：为满足问题的解而对不同分量之间施加的约束。解空间.•对于问题的一个实例，解向量满足S式约束条件的所有多元组，构成了该实例的一个解空间。确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结

10、点。如果在当前的扩展结点处不能W向纵深方向移动，则当前扩展结点就成为死结点。此吋，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。回溯法有“通用解题法”之称，是一种比穷举“聪明”的搜索技术，在搜索过程中动态地产生问题的解空间，系统地搜索问题的所有解。当搜索到解空间树的任一结点时，判断该结点是否包含问题的解。如果该结点肯定不包含，则“见壁回头”，跳过以该结点为根的子树的搜索，逐