剪枝函数 Pruning Function
回溯法 v.s. 分枝限界法
回溯法
寻找满足约束条件的所有可行解 使用剪枝函数的深度优先生成状态空间树中结点
分支限界法（第七章）
寻找满足约束条件的一个解，或在满足约束条件的可行解 中寻找最优解
使用广度优先生成结点，并使用剪枝函数
【实例1】0/1背包问题
6.1.3 回溯法的适用条件 – 多米诺 （Domino）性质
12 3 1 23
12 3 A B
27
6.1.4 回溯法的效率估计
蒙特卡洛法（Monte Carlo）
蒙特卡洛法之路径选择
蒙特卡洛法之算法实现
蒙特卡洛法之子过程
【实例】4后问题
4后问题之估计结果
6.2 组合问题
① 装载问题 ② 0/1背包问题 ③ n-皇后问题 ④ 图的m着色问题 ⑤ 子集和数问题
第六章 回溯法 Backtracking
6.1 算法思想 6.2 组合问题 6.3 图问题 6.4 算法效率的影响因素及改进途径 6.5 典型问题的C++程序
6.1 算法思想（走不通回头）
在解空间中搜索可行解或最优解的技术
① 以深度优先遍历进行搜索以避免遗漏可行解 ② 以跳跃式搜索改善算法的运行效率
【实例】排序问题
搜索策略 Search Strategy
避免漏掉某些结点 三类策略
① 深度优先搜索（Depth-First Search，DFS） ② 广度优先搜索（Breadth-First Search，BFS） ③ 函数举法 搜索效率较为低下
剪枝：不满足约束条件的内节点的子树
待求解问题的类型
① 搜索问题（一个或全部可行解）
n皇后问题、图的m着色问题、装载问题
② 组合优化问题（一个或全部最优解）
背包问题、子集和数问题、货郎问题
为什么要使用回溯法求解组合优化问题？
① 贪心法需要事先设计好最优量度标准 ② 动态规划需要最优解具有最优子结构特性 ③ 上述算法的这些前提执行起来并非易事！！！！
算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定 不包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其 祖先结点回溯。 否则，进入该子树，继续按深度优先的策略进行搜索。
回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有 子树都已被搜索遍才结束。
回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可 以结束。
第一个数据是背包的容量为c（1≤c≤1500），第二个数据是物品的数量 为n（1≤n≤50）。接下来n行是物品i的重量是wi，其价值为vi。所有的
数据全部为整数，且保证输入数据中物品的总重量大于背包的容量。
当c＝0时，表示输入数据结束。
输出 对每组测试数据，输出装入背包中物品的最大价值。
输入样例
对于第i层，背包的剩余容量为W-cw(i)，采用贪
心算法把剩余的物品放进背包，根据贪心算法理论 ，此时剩余物品的价值已经是最优的，因为对剩余 物品不存在比上述贪心装载方案更优的方案。
0/1背包问题之算法实现 数据结构
6.2.1 装载问题
求解思路
算法设计
算法Loading
算法Backtrack
6.2.2 0/1背包问题
给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是 vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我
们如何选择物品，才能使得物品的总价值最大。
输入
void backtrack (int t) { if (t>n) output(x);
else for (int i=0;i<=1;i++) { x[t]=i; if (legal(t)) backtrack(t+1); } }
遍历排列树需要O(n!)计算时间
void backtrack (int t) { if (t>n) output(x);
else for (int i=t;i<=n;i++) { swap(x[t], x[i]); if (legal(t)) backtrack(t+1); swap(x[t], x[i]); } }
1
2
7
12
3
5
8
10
13
15
4
6
9
11
14
16
显示约束 Explicit Constraint
隐式约束 &判定函数 Implicit Constraint & Criterion Function
6.1.1 基本概念
解空间 状态空间树 & 显示约束 隐式约束 & 判定函数 最优解 & 目标函数 部分向量 & 约束函数 搜索策略 & 剪枝函数
解空间 Solution Space
状态空间树 State Space Tree
两类状态空间树：子集树 & 排列树
遍历子集树需O(2n)计算时间
输出样例
50 3
220
10 60
30 120
20 100
0
0/1背包问题之算法设计
0/1背包问题之算法设计
假设当前最优值为bestv，若Bound(i)＜bestv， 则停止搜索第i层结点及其子树，否则继续搜索。 显然r(i)越小， Bound(i)越小，剪掉的分支就越多
。
为了构造更小的r(i) ，将物品以单位重量价值比 di=vi/wi递减的顺序进行排列： d1≥d2≥… ≥dn
【实例2】4后问题
20
【实例3】货郎问题（TSP）
6.1.2 基本思路
6.1.2 基本思路
6.1.2 基本思路
递归回溯
6.1.2 基本思路
迭代回溯
6.1.2 基本思路
回溯法是一个既带有系统性又带有跳跃性的的搜索算法。
在包含问题的所有解的解空间树中，按照DFS的搜索策略，从根 结点出发搜索解空间树
【实例】排序问题
最优解 & 目标函数 Optimal Solution & Objective Function
目标函数／代价函数（cost function）
衡量每个可行解的优劣
组合优化问题的最优解
使目标函数取最大（或最小）的一个或多个可行解
部分向量 & 约束函数 Partial Vector & Constraint Function