算法设计与分析基础论文

《算法设计与分析基础论文》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析论文软件13-224号魏龙回溯法回溯法应用领域回溯法有“通用的解题法”之称。应用回溯法解问题时，首先应该明确问题的解空间。一个复杂问题的解决往往由多部分构成，即，一个大的解决方案可以看作是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来，解任何问题都有一个目标，在约束条件下使目标达到最优的可行解称为该问题的最优解。回溯法概述回溯法可以系统的搜索一个问题的所有解或任一个解，它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空

2、间树。算法搜索到某一结点时，如果断定该结点肯定不包含问题的解，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯这种以深度优先方式搜索问题的解的方法称为回溯法回溯算法的形式描述假设回溯算法要找出所有的答案结点而不是仅仅只找出一个。①　设(x1,x2,…,xi-1)是状态空间树中由根到一个结点(问题状态)的路径。②　T(x1,x2,…,xi-1)是下述所有结点的xi的集合，它使得对于每一个xi,(x1,x2,…,xi)是一条由根到结点xi的路径③　存在一些限界函数Bi(可以表示成一些谓词)，如果路径(x1,x2,…,xi)不可能延伸到一个答案结点，则Bi(x1,

3、x2,…,xi)取假值，否则取真值。　　因此，解向量X(1:n)中的第i个分量就是那些选自集合T(x1,x2,…,xi-1)且使Bi为真的xi。回溯法思想第一步：为问题定义一个状态空间(statespace)，这个空间必须至少包含问题的一个解第二步：组织状态空间以便它能被容易地搜索。典型的组织方法是图或树第三步：按深度优先的方法从开始结点进行搜索–开始结点是一个活结点（也是E-结点：expansionnode）–如果能从当前的E-结点移动到一个新结点，那么这个新结点将变成一个活结点和新的E-结点，旧的E-结点仍是一个活结点。–如果不能移到一个新结点，当前的E-结

4、点就“死”了（即不再是一个活结点），那么便只能返回到最近被考察的活结点（回溯），这个活结点变成了新的E-结点。–当我们已经找到了答案或者回溯尽了所有的活结点时，搜索过程结束。皇后问题---回溯求解国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了N个互不攻击的皇后，他还认为可能有N种不同的放法，这就是有名的“N

5、皇后”问题。如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。回溯法的基本思想：对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删

6、除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省时间。不妨以8皇后为例，设8皇后为xi，她们分别在第i行（i=1,2,3,4,5,6,7,8）,这样问题的解空间就是一个8个皇后所在列的序号，为n元一维向量（x1,x2,,x3,x4,x5,x6,x7,x8），搜索空间是1≤xi≤8（i=1,2,3,4,5,6,7,8）,共88个状态。约束条件是8个点（1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。虽然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为回溯法采用

7、的是“走不通就掉头”的策略，而形如（1,1,x3,x4,x5,x6,x7,x8）的状态共有86个，由于1,2号皇后在同一列不满足约束条件，回溯后这些状态是不会搜索的。八皇后问题是一个古老而著名的问题,首先由数学家高斯提出。该问题要求在8x8格的国际象棋盘上摆放8个皇后,使其不能互相攻击,也即任愈两个皇后都不处于同一行、同一列或同一斜线上。如下图l所示,就是其中的一个方案(用Q代表皇后)。八皇后问题可以一般化为n皇后问题,即在nxn格的棋盘上放工n个皇后,使其不会互相攻击的问题。n皇后问题是非结构化的问题,它不需要寻找最优解,只要找出满足约束条件的可行解即可。回溯

8、法是人工智能搜索策略之一