回溯法

一、回溯法分析最小重量机器设计问题
问题定义
机器由 n 个部件组成，每个部件可从 m 个供应商采购。wij​ 为第 i 部件选第 j 供应商的重量，cij​ 为对应成本。要求总重量最小，且总成本不超过上限 C。
1.1 解空间
解空间为 n 元组集合：
X={(x1​,x2​,…,xn​)∣1≤xi​≤m,i=1,2,…,n}
其中 xi​ 表示第 i 个部件选择的供应商编号，解空间大小为 mn。
1.2 解空间树
解空间树是一棵 m 叉树，树深度为 n：

根节点（第 0 层）：未选择任何部件。
第 i 层节点（1≤i≤n）：已确定前 i−1 个部件的供应商，正在决策第 i 个部件的供应商。
分支：每个节点有 m 个分支，对应第 i 个部件的 m 个供应商选择。
叶节点（第 n 层）：对应一个完整的采购方案，共 mn 个。

1.3 结点的状态值
遍历过程中，每个结点需维护 3 个核心状态值：

当前层数 k：已确定前 k 个部件的供应商，下一步决策第 k+1 个部件。
当前总重量 cur_w：前 k 个部件的重量和，cur_w=∑i=1k​wi,xi​​。
当前总成本 cur_c：前 k 个部件的成本和，cur_c=∑i=1k​ci,xi​​。

状态值作用：cur_c>C 时剪枝；k=n 且 cur_c≤C 时，用 cur_w 更新全局最小重量。
二、对回溯算法的理解

核心思想

基于深度优先搜索的枚举策略，遵循试探 - 回溯 - 剪枝原则：逐步构建部分解，若当前路径违反约束或无法得到最优解，则回退到上一层尝试其他分支，通过剪枝减少无效搜索。
关键要素

解空间：问题所有可能解的集合，需结构化表示。
解空间树：解空间的树形可视化，指导深度优先遍历。
状态值：结点维护的当前信息，用于剪枝和可行解判断。
剪枝函数：约束函数（排除违反约束路径）、界函数（排除非最优路径）。

适用场景
组合优化问题（如 0-1 背包、TSP、八皇后），适用于解空间规模大但可剪枝的场景。
特点

优点：相比暴力枚举效率更高，可保证全局最优解。
缺点：最坏时间复杂度为指数级，大规模问题求解效率低。

与分支限界法区别

回溯法：深度优先，找所有可行解 / 最优解，基于栈存储。
分支限界法：广度 / 最小耗费优先，找最优解，基于队列 / 优先队列存储。