算法分析与设计[回溯法].ppt

《算法分析与设计[回溯法].ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章回溯法什么是回溯法例：迷宫游戏可用回溯法求解的问题问题的解可以用一个n元组(x1,…,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数P(x1,…,xn)（也称限界函数）取极值或满足该规范函数条件。例子：A(1:n)个元素的分类问题问题的解为n元组；xi取自有穷集；规范函数P：A(xi)≤A(xi+1)问题求解的方法硬性处理法列出所有候选解，逐个检查是否为所需要的解理论上，候选解数量有限，并且通过检查所有或部分候选解能够得到所需解时，上述方法可行实际中则很少使用，因为候选解

2、的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模较小的问题。回溯或分枝限界法避免对很大的候选解集合进行完全检查大大减少问题的求解时间通常用来求解规模较大的问题回溯法概述回溯法可以系统的搜索一个问题的所有解或任一个解它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索到某一结点时，如果断定该结点肯定不包含问题的解，则跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯这种以深度优先方式搜索问题的解的方法称为回溯法回溯法思想第一步：为问题定义

3、一个状态空间(statespace)。这个空间必须至少包含问题的一个解第二步：组织状态空间以便它能被容易地搜索。典型的组织方法是图或树第三步：按深度优先的方法从开始结点进行搜索开始结点是一个活结点（也是E-结点：expansionnode）如果能从当前的E-结点移动到一个新结点，那么这个新结点将变成一个活结点和新的E-结点，旧的E-结点仍是一个活结点。如果不能移到一个新结点，当前的E-结点就“死”了（即不再是一个活结点），那么便只能返回到最近被考察的活结点（回溯），这个活结点变成了新的E-结点。当我们已经找

4、到了答案或者回溯尽了所有的活结点时，搜索过程结束。回溯法如何提高效率？由开始结点到当前E-结点构成解向量(x1,…,xi)；其中的xi取自于某个有穷集Si，假设集合Si的大小是mi。如果判定(x1,…,xi)不能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。因此回溯法的测试次数比硬性处理作的测试次数要少得多。如何判定(x1,…,xi)能否导致最优解？约束条件回溯法的解需要满足一组综合的约束条件，通常分为：显式约束和隐式约束显式约束条件限定每个xi只从一个给定的集合上取值，例如：Xi≥0即si={

5、所有非负实数}xi=0或xi=1即si={0,1}l≤xi≤u即si={a:l≤a≤u}满足显式约束的所有元组确定一个可能的解空间隐式约束描述了xi必须彼此相关的情况，如0/1背包问题中的背包重量M回溯法求解的经典问题（1）8-皇后问题在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。8皇后问题的解可以表示为8-元组(x1,…,x8)，其中其中xi是第i行皇后所在的列号。显式约束条件是si={1,2,3,4,5,6,7,8},1≤i≤

6、8隐式约束条件是，没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。QQQQQQQQ1234567812345678由于解向量之间不能相同，所以解空间的大小由88个元组减少到8!个元组。上图中的解表示为一个8-元组即（4，6，8，2，7，1，3，5）。回溯法求解的经典问题（2）子集和数问题已知(w1,w2,…,wn)和M，均为正数。要求找出wi的和数等于M的所有子集。例如：若n=4,(w1,w2,w3,w4)=(11,13,24,7),M=31，则满足要求的子集是(11,13,7)和(24,7).子

7、集和数问题解的一种表示方法若用Wi的下标表示解向量，这两个解向量为(1,2,4)和(3,4)。子集和数问题的解可以表示为k-元组(x1,x2,…,xk),1≤k≤n并且不同的解可以是大小不同的元组。显式约束条件是xi∈{j

8、j为整数且1≤j≤n}。隐式约束条件是1)没有两个xi是相同的;2)wxi的和为M;3)xi＜xi＋1,1≤i＜n（避免产生同一个子集的重复情况）子集和数问题解的另一种表达解由n-元组(x1,x2,…,xn)表示显式约束条件xi∈{0,1}，1≤i≤n，如果没有选择Wi，则xi=0；如果

9、选择了Wi，则xi=1。于是上面的解可以表示为(1，1，0，1)和(0，0，1，1)隐式约束条件(xi×wi)的和数为M解空间的大小为2n个元组解空间的树结构回溯算法通过系统地检索给定问题的解空间来确定问题的解。这检索可以用这个解空间的树结构来简化。为了便于讨论，引进一些关于解空间树结构的术语。问题状态(problemstate)：树中的每一个结点确定所求解问题的一个问题状态。状态空间(statespace)：由