[第五章]回溯法

• 遍历、退回、剪枝

算法框架

问题的解空间

基本思想

1. 针对问题，定义解空间

2. 确定易于搜索的解空间结构

3. 深度优先搜索解空间，避免无效搜索

生成问题状态的基本方法

• 扩展结点：正在生成儿子

• 活结点：已经生成但是儿子没有全部生成

• 死结点：所有儿子已经产生

• 深搜：

• 宽搜

• 回溯：避免不可能产生解

递归回溯

迭代回溯

子集树与排列

• 框架

• 子集问题：n个元素要么选要么不选

• 存0、1

• n*2^n

• 排列问题
存下标
n!

装载问题

• 问题：n个货物，m个船每个船载重量ci和小于货物总重量，问能装满吗

• 等价于w[i]=v[i]的01背包问题

• 第一个尽量装满，再看第二个

解法

• 解空间：子集树

• 约束函数：不能超载

• 上界函数：如果有可能更优才继续运行

批处理作业调度

符号三角形

• 问题描述：+-构成三角形每行相差一个，左右相同下面加，不同为减

解法

• 解向量n元组x[1:n]表示第一行

• 可行性约束，放前方惨叫行的+个数或-个数不超过n*(n-1)/4

• 上界函数总数n*(n-1)/2不为奇数

N皇后问题

• n*n棋盘，n个皇后（横竖斜）互不攻击，有几种解

解法

• 解向量：（x1…xn）

• 显约束：x1[1,n]xZ

• i

最大团问题

• 完全子图：这个子图中的任意两点之间的线都相连，所有线都属于父图

• 团：不包含在更大的完全子图中的完全子图

• 最大团：图中最大的团

• 空子图：不属于原图中的边

• 独立集：不包含在更大的空子图中

• 最大独立集：包含顶点数最多的独立集

• U是G的最大团当且仅当U是的最大独立集

解题

• 解空间：子集树

• 可行性约束：当前的点和所有已选择的点都相连

图的m着色问题

• 无向连通图

旅行售货员问题

圆排列问题

• n个大小不等的圆，各圆与矩形底边相切

连续邮资问题

坏球称重

• 原本n个质量相等的小球，但其中一个小球坏了，质量不同

解法

• 三分n
• 1234 | 5678 | 9 10 11 12
称重1、2
小于在1或2，大于在1或62，等于在3

• 1678 | 59 10 11 | 12
称重1、2