xxx 旅行商问题（分支限界法） 题目描述 ： 给定一个完全无向图，其中每个顶点代表一座城市，每条边上的权重代表两座城市之间的距离。旅行商问题要求从某个城市出发，访问所有其他城市恰好一次，最后返回出发城市，并且使得整个旅行路径的总距离最短。这是一个经典的NP-hard组合优化问题。在本题目中，我们将讨论如何使用 分支限界法 来精确求解该问题。 解题过程 ： 分支限界法是一种系统地搜索解空间树的算法，通过“分支”生成子问题，通过“限界”剪去不可能产生最优解的分支。对于旅行商问题，我们采用 最小成本优先 的搜索策略，并利用“归约矩阵”来计算下界。 步骤1：理解归约矩阵与下界计算 对于一个带权完全图，我们可以用一个代价矩阵 \( C = [ c_ {ij}] \) 表示，其中 \( c_ {ij} \) 是从城市 \( i \) 到城市 \( j \) 的距离。 归约操作 ：对矩阵的每一行，减去该行的最小值（称为行归约），再对每一列减去该列的最小值（称为列归约）。所有被减去的数值之和称为 归约成本 ，它构成了从该节点出发的路径长度的下界。 原理 ：任何合法路径都必须从每个城市离开一次，并进入每个城市一次。因此，减去每行/每列的最小值不会影响最优路径的相对长度，但能给出一个保守的下界。 步骤2：构建搜索树与分支策略 每个搜索节点对应一个“部分路径”和一组“已包含的边”。 分支时，我们选择一个尚未决定的边 \((i, j)\) 进行分支，生成两个子节点： 子节点A：强制包含边 \((i, j)\) 在路径中。 子节点B：强制禁止边 \((i, j)\) 在路径中（即设置 \( c_ {ij} = \infty \)）。 分支边的选择通常基于“最大惩罚原则”：选择能最大程度提高下界的边，以便尽快剪枝。 步骤3：限界与剪枝 对每个节点计算下界（归约成本 + 已确定的路径长度）。 维护一个全局最优解的上界（初始可用贪心法或随机路径得到）。 如果某个节点的下界 ≥ 当前上界，则该节点的子树中不可能产生更优解，直接剪枝。 步骤4：算法流程 初始化：创建根节点，对应空路径，用初始代价矩阵计算归约成本作为下界。 使用优先队列（按最小下界优先）存储待处理的节点。 循环直到队列为空： a. 取出下界最小的节点。 b. 如果该节点已构成完整哈密顿回路（访问了所有城市并回到起点），则更新上界，并记录路径。 c. 否则，进行分支： 选择分支边 \((i, j)\)。 对于“包含边”分支：更新矩阵（删除第 \(i\) 行和第 \(j\) 列，并禁止形成子环），重新归约计算新下界。 对于“禁止边”分支：设置 \( c_ {ij} = \infty \) 后重新归约计算下界。 d. 将两个新节点插入优先队列（如果下界小于当前上界）。 输出记录的最优路径和长度。 示例说明 ： 假设有4个城市，代价矩阵如下（行/列对应城市1~4）： \[ \begin{bmatrix} \infty & 10 & 15 & 20 \\ 10 & \infty & 35 & 25 \\ 15 & 35 & \infty & 30 \\ 20 & 25 & 30 & \infty \end{bmatrix} \] 根节点归约：每行减最小值（10, 10, 15, 20），每列减（0, 0, 5, 0），归约成本 = 10+10+15+20+5 = 60。下界 = 60。 分支边选 (1,2)： 包含(1,2)：删除第1行、第2列，并禁止子环（如设置(2,1)=∞），重新归约得到新下界。 禁止(1,2)：设c12=∞后重新归约。 不断重复，最终找到最优回路。 关键点 ： 归约矩阵保证了下界的紧致性，加速剪枝。 优先队列确保先探索有希望的分支。 该算法在中小规模（如城市数 ≤ 20）的TSP中可求得精确解，但规模增大时仍会面临组合爆炸。 通过以上步骤，分支限界法能够系统且高效地搜索TSP的解空间，在可接受时间内为中等规模问题提供最优解。