第7章 分支

基本方法就是把所有路线构成的集合拆分成越来越小的子集，分别计算每个子集的最优路线代价下界。

——John Little等人，1963年¹

_{1.Little, J. D. C., et al. 1963. Operations Research 11, 972–989.}

在1954年Dantzig等人的研究工作之后，直到1973年Chvátal的成果发表之前，是TSP割平面法的蒙昧时代。当时，研究人员倾力研究各种各样的其他解法。其中，最重要的解法是分支定界法（branch-and-bound）。该方法以分而治之为理念，和割平面法一样，都是在旅行商问题的背景下提出的通用方法。如今，最先进的TSP计算软件结合了分支定界算法和割平面法，从而有能力解决包含成千上万座城市的旅行商问题。