回溯法（Backtracking）
把问题的“决策过程”当成一棵状态空间树，按深度优先往下试探：做一个选择→继续→不行就撤销（回溯）。
核心是“剪枝”：一旦发现当前部分解违反约束（不可能继续得到可行解），立刻停止扩展这条路径。
-
目标：通常是找可行解（一个、多个或全部），也可带最优性但以可行性剪枝为主。
-
剪枝依据：
-
约束函数：立刻判定“冲突/超界/重复”等非法。
-
（可选）限界估计：给当前前缀能达到的最好成绩做个乐观估计，用来提前止损。
-
-
搜索策略：DFS/递归/栈，先走到底再回头。
伪代码
best = -∞ 或 收集 = ∅
DFS(node):
if 违反约束: return
if 到达叶子(形成完整解):
更新 best 或 收集解
return
for 每个可选决策:
选择
// 可选：做乐观估计，若“最乐观也不如 best”则剪枝
DFS(后继)
撤销选择
分支限界法（Branch and Bound, B&B）
同样沿状态空间树搜索，但面向优化问题：每个结点计算一个界（上界或下界），若这个界也不可能优于当前最优解，就直接丢弃整棵子树。
-
目标：全局最优解。
-
关键：界的设计要“乐观但不犯错”（最大化用上界≥真实最优，最小化用下界≤真实最优）。
-
结点选择：不必 DFS，可用
-
队列（FIFO 分支限界，近似 BFS），
-
优先队列（Best-first / LC 分支限界，按界值挑最有希望的结点），
-
也可用栈（DFS），但通常配合更强的界。
-
伪代码
best = -∞（最大化）; PQ 以 bound 降序
根结点入队（算好 bound）
while PQ 非空:
取出 bound 最大的结点 u
if u.bound ≤ best: continue // 不可能更优，丢
扩展 u 的孩子 v:
计算 v.bound
if v 是完整可行解:
best = max(best, v.value)
else if v.bound > best:
PQ.push(v)
返回 best
例题（01背包）
回溯法
伪代码
best = 0, best_x = []
DFS(i, curW, curV): // 已决策到第 i 件(1..n)，累积重量/价值
if curW > C: return // 约束函数：超重剪枝
if i > n:
if curV > best: best = curV; best_x = 当前选择
return
// 选 i
选[i] = 1
DFS(i+1, curW + w[i], curV + v[i])
// 不选 i
选[i] = 0
DFS(i+1, curW, curV)
搜索解空间树
分支界限法
约束函数 C(i) ：到第 i 层的剩余容量
C(i)=C-\sum_{k=1}^{i}x_k w_k \quad(\text{若 }C(i)<0\text{ 则剪枝})
限界函数 B(i)：对“尚未决定的物品”用分数背包给出乐观上界
（先按价值密度 v_j/w_j 从大到小装满，最后一件可取分数）。
本例密度： 1号：35/15\approx2.33，2、3号=2.0。顺序 1\rightarrow2\rightarrow3。
伪代码
预处理：
// 将物品按价值密度从大到小重排（仅用于计算上界与/或决策顺序）
reorder items so that ρ1 ≥ ρ2 ≥ ... ≥ ρn
// 若不想重排决策顺序，也可以单独保留一个密度序 p[1..n] 专供上界函数遍历
function UPPER_BOUND(i, curW, curV):
// 估计：从第 i 件开始，用“分数背包”把剩余容量装满，得到乐观上界
if curW > C: return curV // 已经超重，返回当前值（也可返回 -∞）
rem = C - curW
ub = curV
for k = i .. n: // 遍历密度降序后的物品
if w[k] <= rem:
ub = ub + v[k]
rem = rem - w[k]
else:
ub = ub + ρ[k] * rem // 允许最后一个取“分数”
break
return ub
DFS分支界限：
global best = 0
global best_x[1..n] = 0
procedure DFS(i, curW, curV, x[1..n]):
ub = UPPER_BOUND(i, curW, curV)
if curW > C: return // 约束剪（超重）
if ub <= best: return // 界剪（最乐观也不可能更优）
if i > n: // 到达叶子（一个完整可行解）
if curV > best:
best = curV
best_x = x
return
// 分支1：选择第 i 件
x[i] = 1
DFS(i + 1, curW + w[i], curV + v[i], x)
// 分支2：不选第 i 件
x[i] = 0
DFS(i + 1, curW, curV, x)
procedure BnB_DFS(w[1..n], v[1..n], C):
// 可选：按密度重排 w,v（或保留单独的密度序供 UPPER_BOUND 使用）
best = 0; best_x = all zeros
x = all zeros
DFS(1, 0, 0, x)
return best, best_x
搜索空间树
