旅行商问题

        这里主要是通过介绍旅行商问题，引出几个我们关注较多的几个经典算法，以供后续进一步解读提供依据。

        旅行商问题（英语：Travelling salesman problem,TSP）是：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

        “旅行商问题”的应用领域包括：如何规划最合理高效的道路交通，以减少拥堵；如何更好地规划物流，以减少运营成本；在互联网环境中如何更好地设置节点，以更好地让信息流动等。

        从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

       笔者在后续的文章中会对遗传算法、模拟退火算法、蚁群算法等做详细的探索。尤其会在“遗传算法深入学习下”中对建模与仿真的重要性做深入的探讨，希望对还处于建模与仿真以下阶段的同学的进一步提升，有所帮助！

最后

以上就是危机星星最近收集整理的关于旅行商问题的全部内容，更多相关旅行商问题内容请搜索靠谱客的其他文章。