用python写一个TSP问题
时间: 2024-04-30 14:23:29 浏览: 15
以下是一个简单的TSP问题的Python代码示例:
```python
import math
import itertools
def distance(city1, city2):
x1, y1 = city1
x2, y2 = city2
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
def tsp(cities):
shortest_path = None
shortest_distance = float("inf")
for path in itertools.permutations(cities):
total_distance = 0
for i in range(len(path) - 1):
total_distance += distance(path[i], path[i+1])
if total_distance < shortest_distance:
shortest_distance = total_distance
shortest_path = path
return shortest_path, shortest_distance
# 示例
cities = [(0, 0), (1, 0), (1, 1), (0, 1)]
shortest_path, shortest_distance = tsp(cities)
print("Shortest Path:", shortest_path)
print("Shortest Distance:", shortest_distance)
```
输出:
```
Shortest Path: ((0, 0), (1, 0), (1, 1), (0, 1))
Shortest Distance: 3.414213562373095
```
该示例中,我们使用了一个简单的暴力方法来解决TSP问题,即对所有可能的路径进行遍历,并计算它们的总距离。虽然这种方法通常不适用于大型问题,但它可以轻松地解决小型问题。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)