当前位置：首页 > news >正文

回溯法的两种实现方式（迭代与递归）本质上都是对解空间树进行深度优先搜索（DFS），区别在于控制搜索过程的机制不同

news 2026/3/27 3:51:39

回溯法的两种实现方式（迭代与递归）本质上都是对解空间树进行深度优先搜索（DFS），区别在于控制搜索过程的机制不同：

迭代方式使用显式栈（或变量k模拟栈顶）管理当前搜索深度，通过循环和手动增减k实现“前进”与“回溯”，避免函数调用开销，空间可控但逻辑较复杂；
递归方式利用系统调用栈天然支持状态保存与自动回溯，代码简洁、符合问题直观结构，但存在栈溢出风险（深度过大时）且额外开销略高。

限界函数（Bounding Function）是回溯法优化的关键——它不同于约束函数（Constraint Function，用于判断当前部分解是否满足问题基本约束），而是面向优化目标（如最大价值、最短路径等），在扩展结点前预估其子树中可能达到的最优值上界（对最大化问题）或下界（对最小化问题）。若该估计值不优于当前最优解，则剪枝。例如在 0-1 背包问题中，常用贪心上界（对剩余物品按单位重量价值降序装入，允许分数装入）作为限界函数，因其计算快且紧致性较好。

# 示例：0-1背包问题的限界函数（最大化价值，w[i], v[i]为重量与价值，cap为剩余容量）defbound(i,cap,current_value,w,v):# i: 当前考虑第i个物品（0-indexed），剩余容量cap，当前已获价值current_valuebound_val=current_value remaining_cap=cap j=iwhilej<len(w)andremaining_cap>0:ifw[j]<=remaining_cap:bound_val+=v[j]remaining_cap-=w[j]else:# 分数装入（贪心上界）bound_val+=v[j]*(remaining_cap/w[j])breakj+=1returnbound_val

在迭代回溯中，需显式模拟递归栈的行为，为每一层深度 $ k $ 维护：

当前候选集合 $ S_k $（通常用列表、队列或迭代器表示）；
已选元素 $ x_k $（或当前尝试的候选索引）；
有时还需保存部分解状态（如已选物品总重/总价值）以支持约束/限界判断。

常用实现策略：
✅ 使用栈stack，每个元素为元组(k, S_k, next_index, state)，其中：

k: 当前深度（第kkk个位置，从 1 开始）；
S_k: 候选集合（可预生成列表，如candidates[k]，或动态计算）；
next_index: 下一个待尝试的候选在S_k中的下标（避免重复构造集合）；
state: 可选，如当前解的部分信息（如背包已用容量、皇后已占列集合等），用于快速验证约束/计算限界。

以下为通用伪代码框架（支持约束检查与限界剪枝）：

1 stack ← empty stack 2 k ← 1 3 S₁ ← generate_candidates_for_level(1) // 初始候选集，如 {1,2,...,n}（n皇后） 4 push(stack, (k, S₁, 0, initial_state)) // next_index=0 表示将尝试 S₁[0] 5 6 while stack is not empty do 7 (k, S_k, idx, state) ← pop(stack) 8 if idx ≥ |S_k| then continue // 本层候选已穷尽，跳过（自动回溯） 9 10 x_k ← S_k[idx] 11 new_state ← update_state(state, x_k) // 如：add_queen(row=k, col=x_k), or add_weight=w[k] 12 13 if not is_feasible(new_state) then // 约束函数：剪去不满足基本条件的分支 14 push(stack, (k, S_k, idx + 1, state)) // 尝试下一个候选 15 continue 16 17 if is_complete_solution(new_state) then 18 output solution from new_state 19 continue 20 21 bound_val ← bound_function(k+1, new_state) // 限界函数：估计扩展后的最优可能值 22 if bound_val ≤ current_best_value then // 剪枝：不可能更优 23 push(stack, (k, S_k, idx + 1, state)) 24 continue 25 26 // 可扩展：进入下一层 k+1 27 S_{k+1} ← generate_candidates_for_level(k+1, new_state) 28 push(stack, (k, S_k, idx + 1, state)) // 本层留痕：下次试下一个x_k 29 push(stack, (k+1, S_{k+1}, 0, new_state)) // 深入下一层，从首个候选开始

📌关键设计说明：