1 回溯法与搜索树 #
回溯法逐步做选择，沿一条路线向下搜索；到达结束条件或发现无效时，返回上一个选择点，尝试其他分支。一般按深度优先搜索。
- 根节点：尚未做选择的初始状态。
- 树的一层：决定一个位置或物品。
- 从根到节点的路径：当前已经做出的选择。
- 可行解：满足题目约束的完整方案。
- 剪枝：发现当前分支不可能产生所需解时，不再展开后代。
每一位或物品只有0/1两种选择时，可用二叉子集树表示。剪枝能减少部分搜索，但最坏情况下仍可能需要搜索指数级数量的节点。
2 不能出现连续1的二进制串 #
题目与剪枝条件 #
输出所有长度为4且没有连续两个1的二进制串。本例允许前导0，若题目明确规定首位为1，应增加首位限制。
例如0101合法，0110包含连续的11，不合法。已经出现11的前缀，不论后面再加什么都不合法，可以立即停止该分支。
搜索树 #
每层添加一位，根为空串。✓是合法结果，×是因出现11而拒绝或剪去的候选：
空
├── 0
│ ├── 00
│ │ ├── 000
│ │ │ ├── 0000 ✓
│ │ │ └── 0001 ✓
│ │ └── 001
│ │ ├── 0010 ✓
│ │ └── 0011 ×
│ └── 01
│ ├── 010
│ │ ├── 0100 ✓
│ │ └── 0101 ✓
│ └── 011 ×
└── 1
├── 10
│ ├── 100
│ │ ├── 1000 ✓
│ │ └── 1001 ✓
│ └── 101
│ ├── 1010 ✓
│ └── 1011 ×
└── 11 ×合法结果：0000、0001、0010、0100、0101、1000、1001、1010，共8个。
搜索到0000后返回前缀000，再尝试添加1得到0001，这个返回上一个选择点并尝试其他分支的过程就是回溯。
伪代码 #
搜索(s,n)：
如果长度(s)=n：
输出s
返回
搜索(s+"0",n) // 下一位选0
如果s为空 或 s最后一位不是1：
搜索(s+"1",n) // 下一位选1前先检查
调用 搜索(空串,4)图中的×用于展示被拒绝的候选；伪代码先判断条件，因此不会真正递归进入这些分支。
3 回溯法求0–1背包 #
题目与解向量 #
背包容量W=4，物品A重3价值5，B重2价值3，C重2价值3。每件只能选或不选，求总价值最大的可行方案。
解向量x=(x₁,x₂,x₃)分别表示A、B、C；1为选，0为不选。例如100只选A，011选B+C。
未剪枝的完整解空间有8个叶子：111、110、101、100、011、010、001、000。考试要求画完整树时，超重节点的后代也要画出；要求画剪枝后的搜索树时，在剪枝处停止展开。
超重约束剪枝 #
节点标记为（当前重量,当前价值）；每层依次决定A、B、C，按先选1、后选0搜索：
开始 (0,0)
├── A=1 (3,5)
│ ├── B=1 (5,8) × 超重
│ └── B=0 (3,5)
│ ├── C=1 (5,8) × 超重
│ └── C=0 (3,5) ✓ 100，价值5
└── A=0 (0,0)
├── B=1 (2,3)
│ ├── C=1 (4,6) ✓ 011，价值6
│ └── C=0 (2,3) ✓ 010，价值3
└── B=0 (0,0)
├── C=1 (2,3) ✓ 001，价值3
└── C=0 (0,0) ✓ 000，价值0选A后再选B，重量3+2=5>4，后续再怎么选择也无法恢复可行，整棵子树剪去。
先找到100，价值5，记录best=5；再找到011，价值6，更新best=6。最终最优方案是B+C，重量4、价值6。
这张图只使用超重约束剪枝。若采用先检查再递归的实现，图中×表示检查后拒绝进入的候选节点。
考场伪代码 约束剪枝 #
假设重量和价值非负，允许不选任何物品；x记录当前路径，bestChoice保存一种最优方案。
best=0；x=全0数组；bestChoice=全0数组
搜索(i,当前重量,当前价值)：
如果i>n：
如果当前价值>best：
best=当前价值
bestChoice=复制x
返回
如果当前重量+w[i]≤W：
x[i]=1
搜索(i+1,当前重量+w[i],当前价值+v[i])
x[i]=0
搜索(i+1,当前重量,当前价值)
调用 搜索(1,0,0)
输出 best和bestChoice复制x是为了保存当时找到的完整方案；之后搜索其他分支时，x会被继续修改。
限界剪枝的基本思想 #
约束剪枝排除不满足容量的解；限界剪枝则比较某个分支可能达到的价值上界和已知最优值。
当物品价值非负时，可以忽略容量，把剩余物品的价值全部加上：
乐观上界 = 当前价值 + 所有尚未决定物品的价值之和实际方案可能装不下全部物品，因此不会超过这个上界。只要求一种最优方案时，如果上界≤best，该分支不可能产生更优解，可以剪掉。
例：按上述搜索顺序找到best=6后，来到A=0、B=0的节点。当前价值为0，只剩C，乐观上界=0+3=3≤6，可以直接剪掉这个节点下的C分支。上方树为展示约束剪枝而仍列出它的两个孩子；加入此限界后，这两个孩子不用展开。
如果题目要求所有最优方案 ，上界等于best时仍可能有其他同价值最优解，只能在上界严格小于best时剪掉。上面伪代码只实现了超重约束剪枝，限界需要在展开相应子树前另加判断。
4 考场检查 #
- 写清每层决定什么、0和1各表示什么，标注当前重量与价值。
- 超重节点写明约束剪枝；已经找到最优值后用上界剪枝时，写明上界和当前best。
- 要画完整空间树时，不可把已剪枝树当完整树；要画优化后搜索树时，标明剪枝位置及理由。
- 搜索结束给出最优向量、总重量和总价值。若题目指定回溯画树，不能只给DP填表。
- 分支限界法、排列树及其他回溯题型仍需另行复习。