旅行商问题（分支限界法）

旅行商问题（TSP）描述如下：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。这是一个经典的NP-hard问题。分支限界法是解决精确求解TSP的常用技术之一，它通过系统性地枚举所有可能的解（分支），并利用界限（界）来剪掉不可能成为最优解的分支，从而避免穷举所有可能性。

接下来，我将详细讲解基于分支限界法（通常采用最小成本优先的策略，并使用降低代价矩阵计算下界）的求解过程。

1. 问题建模与初始代价矩阵
假设有n个城市，编号为0到n-1，并给定一个距离矩阵dist[n][n]，其中dist[i][j]表示从城市i到城市j的距离。我们通常假定dist[i][i] = ∞（或一个很大的数），表示不进行自环移动。目标是找到从城市0出发（可固定起点，由于回路对称性，通常固定起点以简化问题），访问所有其他城市恰好一次，最后返回城市0的一条路径，使得总距离最小。

首先，我们创建一个初始的代价矩阵cost[][]，它最初是距离矩阵的副本。为了计算路径成本的下界，我们使用“降低矩阵”的技术。

2. 计算初始下界（降低代价矩阵）
降低矩阵的思想是：矩阵的每一行和每一列都至少包含一个零，且任何可行解的成本至少等于所有行和列降低值之和。计算步骤如下：

• 行降低：对矩阵的每一行，找到该行的最小值，并将该行的每个元素减去这个最小值。将所有这些最小值累加起来，记为row_reduction。
• 列降低：对行降低后的矩阵的每一列，找到该列的最小值，并将该列的每个元素减去这个最小值。将所有这些最小值累加起来，记为col_reduction。
• 初始下界 LB = row_reduction + col_reduction。这个LB表示从任意城市出发，访问所有城市并返回的最短可能成本（即一个乐观估计）。

例如，假设4个城市的距离矩阵如下：

  0   10  15  20
 10   0   35  25
 15  35   0   30
 20  25  30   0

行降低：第0行最小值10，减去后行和为10；第1行最小值10，和为10；第2行最小值15，和为15；第3行最小值20，和为20。row_reduction=10+10+15+20=55。降低后矩阵为：

  0    0    5   10
  0   25   15   15
  0   20    0   15
  0    5   10    0

列降低：第0列最小值0，和0；第1列最小值0，和0；第2列最小值0，和0；第3列最小值0，和0。col_reduction=0。所以初始下界LB=55。

3. 分支限界法的搜索树结构
搜索树中的每个节点表示一个“部分解”，即已经确定了路径中的一段连续序列（通常从城市0开始）。每个节点存储以下信息：

• 已确定的路径（例如从0出发经过的城市顺序）。
• 降低后的代价矩阵（尺寸随着某些边被禁止而减小）。
• 当前下界LB。
• 禁止的边集合（例如，为了避免子环，需要禁止某些边）。

分支限界法通常采用优先队列（最小堆）来管理活动节点，按照节点的下界LB从小到大排序（最小成本优先），这样我们总是优先扩展最有希望（下界最小）的节点。

4. 分支过程：选择边进行分割
从当前节点出发，我们需要选择一个边(i, j)进行分支。通常选择可以最大化惩罚（或使得下界增加最多）的边，常用策略是：对于当前降低矩阵中值为0的边(i, j)，计算如果“不选择这条边”（即禁止从i直接到j）会导致的下界增加量（惩罚值）。选择惩罚值最大的那个0值边进行分支。具体来说：

• 对于每个0值边(i, j)，惩罚值 = 当前矩阵中第i行（除(i, j)外）的最小值 + 第j列（除(i, j)外）的最小值。
• 选择惩罚值最大的0值边(i, j)进行分支，产生两个子节点：
  • 左子节点：强制选择边(i, j)。这意味着路径中下一步将从i走到j。
  • 右子节点：禁止选择边(i, j)。这意味着在后续解中不允许直接从i到j。

5. 处理左子节点（选择边(i, j)）
如果选择边(i, j)，我们需要更新代价矩阵和计算新的下界：

1. 禁止从i到其他城市：在矩阵中，将第i行所有元素设为∞（因为从i出发后只能去j，不能再从i去其他城市）。
2. 禁止从其他城市到j：将第j列所有元素设为∞（因为j已经有前驱i，其他城市不能再到j）。
3. 禁止形成子环：将(j, i)设为∞，因为选择了(i, j)后，如果再选(j, i)会立即形成一个长度为2的环，这不是有效哈密顿回路（除非是最后一个城市返回起点，但那是特殊处理）。
4. 对新的矩阵进行行降低和列降低，计算降低值之和reduction。
5. 新节点的下界 = 父节点下界 + reduction。
6. 将边(i, j)加入路径。

6. 处理右子节点（禁止边(i, j)）
禁止边(i, j)很简单：在父节点的代价矩阵中，将(i, j)设为∞。然后对这个新矩阵进行行降低和列降低，计算降低值之和reduction。新节点的下界 = 父节点下界 + reduction。

7. 剪枝与终止条件

• 如果一个节点的下界已经大于等于当前已知的最优解成本（初始最优解成本可设为一个很大的数，或者先用启发式算法如最近邻法得到一个可行解作为初始上界），则剪掉该节点（不加入优先队列）。
• 当节点中路径已经包含所有n个城市（即长度达到n），我们需要加上从最后一个城市回到起点0的成本，形成完整回路。如果这个总成本小于当前最优解，则更新最优解。
• 继续从优先队列中取出下界最小的节点进行扩展，直到优先队列为空。此时找到的最优解就是全局最优解。

8. 算法步骤总结

1. 初始化：创建根节点，其路径为[0]，代价矩阵为原始距离矩阵，计算初始下界LB。设置当前最优解成本best_cost = ∞。将根节点加入优先队列。
2. 当优先队列非空：
   a. 从优先队列中取出下界最小的节点。
   b. 如果该节点的下界 ≥ best_cost，剪枝，继续。
   c. 如果该节点的路径包含所有n个城市，计算完整回路成本。如果小于best_cost，更新best_cost和最优路径。继续。
   d. 否则，对该节点进行分支：
   • 在它的降低矩阵中，找到所有0值边，计算每条边的惩罚值。
   • 选择惩罚值最大的0值边(i, j)。
   • 生成左子节点（选择边(i, j)）和右子节点（禁止边(i, j)），计算它们的下界和更新矩阵。
   • 如果子节点下界 < best_cost，将其加入优先队列。
3. 输出best_cost和对应的最优路径。

9. 实例简要说明（接前面的4城市例子）
根节点LB=55，best_cost=∞。根节点矩阵中0值边有多个，计算每个的惩罚值（具体计算略）。假设选择边(0,1)（惩罚值最大）分支。

• 左子节点（选择(0,1)）：更新矩阵（禁止0行、1列，设(1,0)为∞），降低后计算新下界，比如得到LB=55+某个值。路径变为[0,1]。
• 右子节点（禁止(0,1)）：将(0,1)设为∞，降低矩阵，计算新下界，比如LB=55+某个值。
  将这两个子节点加入优先队列。然后继续从队列中取下界最小的节点扩展，直到找到完整路径并更新最优解，最终得到最短回路。

通过这种方式，分支限界法能有效地排除大量非优分支，从而在可行时间内找到小规模TSP问题的最优解。对于大规模问题，它仍可能因组合爆炸而受限，但相对于朴素穷举已大大提升效率。