回溯算法

回溯的基本思想是什么？

• 定义: 基于穷举与深度优先遍历的搜索算法;
• 过程: 从初始状态出发穷举所有可能, 直到找到解或确认无解;
• 本质: 在决策树上做一次深度优先遍历;

回溯中的"尝试"与"回退"指什么？

• 尝试: 在当前状态做出一个选择, 更新状态并进入下一层;
• 回退: 撤销上一步选择, 恢复到做选择前的状态, 再尝试其他分支;
• 必要性: 同一状态会被多条路径复用, 不撤销会污染兄弟分支;

剪枝在回溯中起什么作用？

• 定义: 依据问题的约束条件, 提前放弃不可能产生解的分支;
• 作用: 把指数级的解空间压到实际可解规模;
• 常见剪枝: 越界判定、重复元素跳过、当前和超过目标值;

回溯的解题步骤是什么？

• 定义决策树: 明确每一层的"选择"是什么、状态如何表示;
• 明确终止条件: 什么状态算找到一个解、什么状态必须停止搜索;
• 翻译代码: 定义回溯函数, 主体依次为剪枝、选择、递归、回退;

回溯的通用框架是什么？

function backtrack(state, choices, res) {
  // 判断是否为解
  if (isSolution(state)) {
    recordSolution(state, res);
    return; // 不再继续搜索
  }
  for (const choice of choices) {
    // 剪枝: 判断选择是否合法
    if (isValid(state, choice)) {
      makeChoice(state, choice); // 尝试: 更新状态
      backtrack(state, choices, res); // 递归搜索
      undoChoice(state, choice); // 回退: 撤销选择
    }
  }
}

• 要点: makeChoice 与 undoChoice 必须严格对称, 否则状态无法还原;