给定一些坐标快速求解TSP 路径的TSP代码
时间: 2023-10-26 17:06:09 浏览: 31
如果给定一些坐标,可以使用欧几里得距离来计算城市之间的距离,在此基础上求解 TSP 问题,以下是使用 Python 解决 TSP 问题的代码示例:
```python
import itertools
import numpy as np
# 生成所有可能的路径
def generate_permutations(n):
cities = np.arange(n)
permutations = itertools.permutations(cities)
return permutations
# 计算路径总长度
def calculate_total_distance(route, coordinates):
n = len(route)
total_distance = 0
for i in range(n):
j = (i + 1) % n
city_i, city_j = route[i], route[j]
x_i, y_i = coordinates[city_i]
x_j, y_j = coordinates[city_j]
distance = np.sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)
total_distance += distance
return total_distance
# 求解 TSP 问题
def tsp(coordinates):
n = len(coordinates)
distances = np.zeros((n, n))
for i in range(n):
for j in range(n):
if i != j:
x_i, y_i = coordinates[i]
x_j, y_j = coordinates[j]
distance = np.sqrt((x_i - x_j) ** 2 + (y_i - y_j) ** 2)
distances[i][j] = distance
best_route, best_distance = None, float('inf')
for route in generate_permutations(n):
distance = calculate_total_distance(route, coordinates)
if distance < best_distance:
best_route, best_distance = route, distance
return best_route, best_distance
# 测试
coordinates = np.array([[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]])
best_route, best_distance = tsp(coordinates)
print('Best route:', best_route)
print('Best distance:', best_distance)
```
在这个例子中,我们先计算出每个城市之间的距离,然后使用相同的方法求解 TSP 问题。在实际应用中,随着城市数量的增加,计算距离的时间也会增加,需要使用更加高效的算法来解决。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)