我们将看到两种应用于旅行推销员问题的通用技术。第一种是 "分支与约束"，它是组合优化中的一种经典方法，用于解决各种问题。它可以看作是对蛮力搜索的一种改进：我们尝试逐个构建一个排列组合，但每一步我们都要检查继续构建排列组合是否仍有意义（如果没有意义，我们就切断当前分支）。第二种，动态编程，可以说是最流行的算法技术。它通过一系列更小的子问题来解决问题。

正如我们在前面的模块中所看到的，精确地解决旅行推销员问题是很难的。事实上，我们甚至不指望在最近的将来找到有效的解。因此，我们不禁要问：有没有可能高效地找到一个可能是次优，但同时又接近最优的解呢？事实证明，答案是肯定的！我们将学习两种算法。第一种算法能保证快速找到比最优解最多延长一倍的解。第二种算法没有这样的保证，但它在实践中效果很好。