05-进阶

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

对旅行商问题的解答都不轻松。这里的朴素解法很快就会变得不再可行。生成的排列数量是n的阶乘（n!），其中n是问题中的城市数量。只要我们再增加1个城市（6个而不是5个），要计算的路径数量就将增加6倍。若在此之后再增加1个城市，问题难度就会再增加7倍。这不是一种可扩展的做法！

在现实世界中，很少会用到旅行商问题的朴素解法。对于包含大量城市的旅行商问题实例，大多数算法都是求出近似解。这些算法尝试求得问题的接近最优（near-optimal）解。接近最优解可能位于围绕完美解的较小可知范围内。例如，它们降低的效率可能不超过5%。

本书已有两种技术可用于尝试求解大数据集的旅行商问题。本章之前用于背包问题的动态规划就是其中的一种技术。另一种技术则是第5章介绍的遗传算法。许多期刊文章已经发表了对于求解包含大量城市的旅行商问题，遗传算法可归于求出接近最优解的解法。