旅行商问题python
时间: 2023-10-12 10:13:33 浏览: 32
旅行商问题(Traveling Salesman Problem,TSP)是指给定一些城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。这是一个经典的NP问题,没有已知的高效算法可以在多项式时间内解决,但可以使用一些近似算法解决。
以下是一个使用暴力枚举的方法来解决TSP问题的Python代码:
```python
import itertools
def tsp(cities):
# 计算所有城市之间的距离
dist = [[0] * len(cities) for i in range(len(cities))]
for i in range(len(cities)):
for j in range(len(cities)):
if i != j:
dist[i][j] = dist[j][i] = ((cities[i][0] - cities[j][0]) ** 2 + (cities[i][1] - cities[j][1]) ** 2) ** 0.5
# 枚举所有可能的路径
min_dist = float('inf')
for path in itertools.permutations(range(len(cities))):
d = sum(dist[path[i]][path[i+1]] for i in range(len(cities)-1)) + dist[path[-1]][path[0]]
min_dist = min(min_dist, d)
return min_dist
# 示例
cities = [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
print(tsp(cities)) # 输出:8.0
```
该代码使用了 `itertools.permutations` 函数来枚举所有可能的路径,然后计算每个路径的总长度。最后返回最短路径的长度。但是,这种暴力枚举的方法在城市数较大时会变得非常慢,因此需要使用更高效的算法。