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