9.8. traveling salesman(TSP - traveling Salesman 问题)


给定城市列表,找到一个只访问每个城市的 salesman 最短导览。

该问题由 Wikipedia 定义。它是计算 计算中最广泛调查的问题之一。然而,在现实世界中,这通常只是规划问题的一部分,以及其他约束,如员工切换限制。

问题大小

dj38     has  38 cities with a search space of   10^43.
europe40 has  40 cities with a search space of   10^46.
st70     has  70 cities with a search space of   10^98.
pcb442   has 442 cities with a search space of  10^976.
lu980    has 980 cities with a search space of 10^2504.
Copy to Clipboard Toggle word wrap

问题困难

尽管 TSP 的简单定义,但问题很难解决。因为这是一个 NP-hard 问题(如大多数规划问题),当问题数据集中稍有改变时,特定问题 dataset 的最佳解决方案可能会改变:

tspOptimalSolutionVolatility
Red Hat logoGithubredditYoutubeTwitter

学习

尝试、购买和销售

社区

关于红帽文档

通过我们的产品和服务,以及可以信赖的内容,帮助红帽用户创新并实现他们的目标。 了解我们当前的更新.

让开源更具包容性

红帽致力于替换我们的代码、文档和 Web 属性中存在问题的语言。欲了解更多详情,请参阅红帽博客.

關於紅帽

我们提供强化的解决方案,使企业能够更轻松地跨平台和环境(从核心数据中心到网络边缘)工作。

Theme

© 2026 Red Hat
返回顶部