1. 最小重量机器设计问题 - 回溯法分析

1.1 解空间
解空间由所有可能的供应商选择方案组成。每个部件i（1≤i≤n）都可以从m个供应商中选择一个，所以解空间大小为 m^n。一个解可以表示为向量 (x₁, x₂, ..., xₙ)，其中 xᵢ 表示第 i 个部件选择的供应商编号。

1.2 解空间树
解空间树是一棵高度为 n+1 的 m 叉树：
第 0 层：根节点
第 1 层：m 个子节点，表示第一个部件选择哪个供应商
第 2 层：每个节点有 m 个子节点，表示第二个部件选择哪个供应商
...
第 n 层：叶子节点，表示完整的选择方案

1.3 结点状态值
在遍历解空间树时，每个结点需要记录：

  1. 当前总价格

  2. 当前总重量

  3. 已选择的供应商序列（路径）

  4. 当前考虑的是第几个部件（深度）

  5. 对回溯算法的理解

回溯算法是一种通过递归深度优先搜索解空间的方法，当发现当前路径不可能得到最优解时，就回溯到上一步尝试其他选择。它常用于求解组合优化问题，通过"剪枝"来减少不必要的搜索。

在本题中，回溯过程：

  • 深度优先遍历解空间树
  • 记录当前最小重量和对应的供应商选择
  • 当总价格超过 d 时剪枝
  • 当当前总重量已经大于已知最小重量时剪枝