给定一组城市以及每对城市之间的距离，我们要解决的问题是：找到一条尽可能短的路径，能够访问每个城市恰好一次并返回起点。
例如，请看右侧图示。图中的一条 TSP（旅行商）路径是 0-1-3-2-0。该路径的代价为 10+25+30+15，即 80。
我们已经探讨过以下解决方案：
1) 朴素解法与动态规划
2) 使用最小生成树的近似解法
分支限界解法
正如在之前的文章中所见，在分支限界法中，对于树中的当前节点，我们需要计算如果沿着该节点向下进行所能获得的最佳可能解的边界。如果这个最佳可能解的边界本身比当前的“最优解”（迄今为止计算出的最优解）还要差，那么我们就忽略以该节点为根的子树。
请注意，经过某个节点的代价包含两部分。
1) 从根节点到达该节点的代价（当我们到达一个节点时，我们已经计算出了这个代价）
2) 从当前节点到达某个叶子节点（最终答案）的代价（我们要计算这个代价的一个边界，来决定是忽略该节点所在的子树还是继续搜索）。
- 在最大化问题中，上界告诉我们，如果沿着给定节点继续，可能获得的最大解是多少。例如，在0/1 背包问题中，我们使用贪心算法来找到上界。
- 在最小化问题中，下界告诉我们，如果沿着给定节点继续，可能获得的最小解是多少。例如，在工作分配问题中，我们通过将代价最低的工作分配给工人来获得下界。
在分支限界法中，最具挑战性的部分是找出一种计算最佳可能解边界的方法。下面是用于计算旅行商问题边界的思路。
任何路径的代价都可以写成如下形式。
Cost of a tour T = (1/2) * ? (Sum of cost of two edges
adjacent to u and in the
tour T)
where u ? V
For every vertex u, if we consider two edges through it in T,
and sum their costs. The overall sum for all vertices would
be twice of cost of tour T (We have considered every edge
twice.)
(Sum of two tour edges adjacent to u) >= (sum of minimum weight
two edges adjacent to
u)
Cost of any tour >= 1/2) * ? (Sum of cost of two minimum
weight edges adjacent to u)
where u ? V
例如，考虑上面展示的图。以下是每个节点相邻的两条最小代价边。
Node Least cost edges Total cost
0 (0, 1), (0, 2) 25
1 (0, 1), (1, 3) 35
2 (0, 2), (2, 3) 45
3 (0, 3), (1, 3) 45
Thus a lower bound on the cost of any tour =
1/2(25 + 35 + 45 + 45)
= 75
Refer [this](http://lcm.csa.iisc.ernet.in/dsa/node187.html) for one more example.
现在我们已经了解了如何计算下界。让我们看看如何将其应用到状态空间搜索树中。我们开始枚举所有可能的节点（最好按字典序）。
1. 根节点： 在不失一般性的前提下，我们假设从顶点“0”出发，之前已经计算出了该节点的下界。
处理第 2 层： 下一层枚举了我们可以去的所有可能的顶点（请记住，在任何路径中一个顶点只能出现一次），即 1, 2, 3… n（注意该图是完全图）。假设我们正在计算顶点 1 的情况，由于我们从 0 移动到了 1，我们的路径现在已经包含了边 0-1。这使得我们可以对根节点的下界进行必要的调整。
Lower Bound for vertex 1 =
Old lower bound - ((minimum edge cost of 0 +
minimum edge cost of 1) / 2)
+ (edge cost 0-1)
这是如何工作的？为了包含边 0-1，我们要加上边 0-1 的代价，并减去一个边权重，使得下界尽可能紧凑（tight），这个被减去的权重就是 0 和 1 的最小边之和除以 2。显然，减去的边不能比这个值更小。
处理其他层： 当我们继续向下一层移动时，我们再次枚举所有可能的顶点。对于上述情况，在 1 之后继续前进，我们检查 2, 3, 4, …n。
假设我们在计算从 1 移动到 2 时的下界，我们将边 1-2 包含进路径中，并调整该节点的新下界。
Lower bound(2) =
Old lower bound - ((second minimum edge cost of 1 +
minimum edge cost of 2)/2)