算法设计与分析 Chapt6 all

Analysis and Design of Algorithms Analysis and Design of Algorithms Transform CodingChapter 6: BacktrackingSchool of Software Engineering ©Yanling Xu回溯法算法框架回溯法:当需要找出问题的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

回溯法的基本做法是搜索，系统的搜索一个问题的所有解或任一解，具有系统性又有跳跃性或是种组织得井井有条的能避免必要搜索的穷举式搜索法或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。

回溯法适用于解一些组合数相当大的问题。

回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解是否包含问题的解。

¾如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结2点回溯；¾否则，进入该子树，继续按深度优先策略搜索。

回溯法算法框架问题的解空间:问题的解空间问题的解向量回溯法希望个问题的解能够表示成个元式 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x 1,x 2,…,x n )的形式。

的取值限定显约束：对分量x i 的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

解空间：对于问题的个实例解向量满足显式约束条件的所有 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。

注意：同一个问题可以有多种表示有些表示方法更简单所需表注意：同个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）3回溯法算法框架解空间的组织将解空间组织成树或图的形式，方便回溯法进行搜索。

Example:n=30-1背包问题的解空间用完全二叉树表示Example: n3时的01背包问题的解空间用完全叉树表示第i层到第i+1层边上的标号给出了变量的值。

从树根到叶的任一路径表示解空间中的一个元素。

4回溯法算法框架回溯法的基本思想深度优先的问题状态生成法从开始结点（根结点）出发，整个开始结点成为当前的扩展结点从开始结点（根结点）出发整个开始结点成为当前的扩展结点 在当前的扩展结点处搜索向纵深方向发展，移至一个新结点，这个新结点成为新的活结点也成为当前扩展结点个新结点成为新的活结点，也成为当前扩展结点如果在当前的扩展结点处不能向纵深方向移动，则当前结点成为死结点应回溯（往回移动）到最近的一个活结点并使这个活死结点，应回溯（往回移动）到最近的个活结点，并使这个活结点成为当前的扩展结点直到找到所要求的解，或解空间已无活结点时为止。

5回溯法算法框架Example: n=3时的0-1背包问题，w = [16, 15, 15], p= [45, 25, 25], c= 306回溯法算法框架Example: 旅行售货员问题某售货员要到若干城市去推销商品，已知各城市间的路程(或费用)，要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程(总旅费)最小。

用图论的形式描述：E)图中一条周游路线是包括中各顶点在内的一条回路无向带权图G=(V ,E), 图中条周游路线是包括V 中各顶点在内的条回路。

周游路线的费用是这条路线上所有边的权(费用,正数)之和。

对应于解空间树上一条从根结点到叶结点的路径。

解空间树的叶结点的个数(n-1)!30126105473420596625665966回溯法算法框架剪枝函数避免无效搜索，提高回溯法的搜索效率用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。

具有限界函数的深度优先生成法称为回溯法。

Example:•01背包问题的回溯法用剪枝函数剪去导致不可行解的子树•在旅行售货员问题的回溯法中，如果从根结点到当前扩展结点处的部分周游路线的费用已经超过当前找到的最好的周游路线的费用，则可分周游路线的费用已经超过当前找到的最好的周游路线的费用则可以断定以该结点为根的子树中不含最优解，可将该子树剪去8回溯法算法框架回溯法的解题步骤针对所给问题，定义问题的解空间；确定易于搜索的解空间结构；以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯法的效率分析用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。

在任何时刻，算法只保存从根结点到当前扩展结点的路径。

如解空间树中从根结点到叶结点的长路径的长度为如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。

而显式地存储整个解空)或O(h(n)!)内存空间9间则需要O(2h(n))或O(h(n)!)内存空间。

回溯法算法框架递归回溯用递归来实现回溯法void backtrack (int t){if (t > n) output(x);elsefor (int i=f(n,t);i<=g(n,t);i++) { //当前扩展结点处未搜过的子树的起始/终止编号x[t]=h(i);x[t]=h(i); //当前扩展结点处x [t ]的第i 个可选值if (constraint(t)&&bound(t)) backtrack(t+1); //约束函数与限界函数// 在当前扩展结点处，x[1:t]的取值满足约束条件，且未使目标函数越界，需要对其相应的子树做进一步的搜索}10}回溯法算法框架迭代回溯void iterativeBacktrack (){i t t 1int t=1;while (t>0) {if (f(n,t)<=g(n,t))for (int i=f(n,t);i<=g(n,t);i++) {x[t]=h(i);if (constraint(t)&&bound(t)){if (constraint(t)&&bound(t)) {if (solution(t)) output(x);//solution(t)判断在当前扩展结点处是否已得到问题的可行解l }else t++;}}else t--;11}}回溯法算法框架子集树与排列树子集树所给的问题是从n个元素的集合S中找出满足某种性质的子集时，所给的问题是从个元素的集合S中找出满足某种性质的子集时相应的解空间树称为子集树n个叶结点，其结点总数为2n＋1－1子集树通常有2个叶结点其结点总数为21遍历子集树的算法均需Ω(2n)12回溯法算法框架用递归法搜索子集树void backtrack (int t){if (t > n) output(x);elsefor (int i=0; i<=1; i++) {f(i i0i1i){x[t] = i;(g())();if (legal(t)) backtrack(t+1);}01背包问题}13回溯法算法框架排列树所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树排列树通常有n!个叶结点遍历排列树需Ω(n!)()14回溯法算法框架用回溯法搜索排列树void backtrack (int t){if (t>n) output(x);elsefor (int i=t;i<=n;i++) {f(i i i i){swap(x[t], x[i]);(g())();if (legal(t)) backtrack(t+1);swap(x[t], x[i]);旅行售货员问题}}150-101背包问题0-1背包问题是子集选取问题，解空间可用子集树表示在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。

就进入其左子树¾当右子树中可能包含最优解时，才进入右子树搜索；¾否则将右子树剪去设r是当前剩余物品价值总和，cp是当前价值，bestp是当前最优价值。

当cp+r≤ bestp时，可剪去右子树。

160-101背包问题上界函数：计算右子树中解的上界：将剩余物品按单位重量价值排序，依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，得到的价值是右子树中解的上界。

得到的价值是右子树中解的上界Example:n = 4, c = 7, p= [9, 10, 7,4], w= [3, 5, 2, 1]物品的单位重量价值分别为[3, 2, 3.5, 4],[3,2,3.5,4],按递单位重量价值的减序装入：4－3－1－0.2的物品2相应的价值为22故最优值的上界不超过22170-101背包问题上界函数template<class Typew, class Typep>Typep Knap<Typew, Typep>::Bound(int i){// 计算上界Typew cleft = c -cw; // 剩余容量Typep b =cp;Typep b cp;// 以物品单位重量价值递减序装入物品while (i <= n && w[i] <= cleft) {cleft -= w[i];b += p[i];i++;}if (i <= n) b += p[i]/w[i] * cleft; // 装满背包18return b;}旅行售货员问题旅行售货员问题的解空间是一颗排列树当i=n 时，当前扩展结点是排列树的叶结点的父结点，此时检测图G 是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。

¾如果这两条边都存在，则找到一条旅行售货员回路•此时还需判断这条回路的费用是否优于已找到的当前最优回路的费用bestc 。

如果是，则必须更新当前的最优值bestc 和当前最优解bestx 时i 1层图x[i 1] 当i<n 时，当前扩展结点位于排列树的第i-1层，图G 中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G 的一条路径，且当x[1:i]的费用小于当层否则剪去相应的子树前的最优值时算法进入排列树的第i 层，否则剪去相应的子树。

复杂度分析在最坏情下能需要更新当前最优解次每次更19算法backtrack 在最坏情况下可能需要更新当前最优解O((n-1)!)次，每次更新bestx 需计算时间O(n)，从而整个算法的计算时间复杂性为O(n!)。

旅行售货员问题template<class Type>void Traveling<Type>::Backtrack(int i)g yp (){if (i == n) {if (a[x[n-1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge &&(+[[1]][[]]+[[]][1]<b t ||b t N Ed )){(cc + a[x[n-1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge)) {for (int j = 1; j <= n; j++) bestx[j] = x[j];bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];}}else {for (int j = i; j <= n; j++)// 是否可进入x[j]子树?if (a[[i 1]][[j]]!NoEdge &&if (a[x[i-1]][x[j]] != NoEdge &&(cc + a[x[i-1]][x[i]] < bestc || bestc == NoEdge)) {// 搜索子树Swap(x[i], x[j]);p([],[j]);cc += a[x[i-1]][x[i]];Backtrack(i+1);cc -= a[x[i-1]][x[i]];Swap(x[i]x[j]);}20Swap(x[i], x[j]);}}}。