求助求助 tsp问题

江山是个艺术家

大佬们，来帮我看看这大一老师布置的作业正常吗
哪位大佬来帮我写个代码出来
万分感谢！！！
实验2.rar (1.46 KB, 下载次数: 5)

2023-4-5 16:49 上传

点击文件名下载附件

sfqxx

请把里面的内容粘贴过来

isdkz

这是一个关于解决TSP问题的Python作业。我将提供一个基本的解决方案，

使用简单的贪心算法来解决这个问题。你可以优化这个代码并创建一个PPT来解释你的程序。

首先，我们从CSV文件中读取数据并将其存储在City类的实例中。

1. import csv
   
2. import math
   
3. 
   
4. class City:
   
5.     def __init__(self, name, x, y):
   
6.         self.name = name
   
7.         self.x = x
   
8.         self.y = y
   
9.         
   
10.     def distance(self, city):
    
11.         return math.sqrt((self.x - city.x)**2 + (self.y - city.y)**2)
    
12. 
    
13.     def __str__(self):
    
14.         return f"{self.name} ({self.x}, {self.y})"
    
15.    
    
16. def read_cities_from_csv(file_path):
    
17.     cities = []
    
18.     with open(file_path, 'r', encoding='utf-8') as file:
    
19.         reader = csv.reader(file, delimiter=';')
    
20.         for row in reader:
    
21.             name, x, y = row
    
22.             cities.append(City(name.strip(), float(x), float(y)))
    
23.     return cities
    
24. 
    
25. cities = read_cities_from_csv("china.csv")

复制代码

接下来，我们将使用一个简单的贪心算法来解决TSP问题：

1. def find_shortest_path(cities):
   
2.     unvisited_cities = cities.copy()
   
3.     starting_city = unvisited_cities.pop(0)
   
4.     visited_cities = [starting_city]
   
5.    
   
6.     while unvisited_cities:
   
7.         closest_city = min(unvisited_cities, key=lambda city: visited_cities[-1].distance(city))
   
8.         visited_cities.append(closest_city)
   
9.         unvisited_cities.remove(closest_city)
   
10.         
    
11.     visited_cities.append(starting_city)
    
12.    
    
13.     return visited_cities
    
14. 
    
15. path = find_shortest_path(cities)

复制代码

现在我们可以计算路径的总距离，并将结果显示出来。

1. def path_distance(path):
   
2.     distance = 0
   
3.     for i in range(len(path) - 1):
   
4.         distance += path[i].distance(path[i + 1])
   
5.     return distance
   
6. 
   
7. print("最短路径为：")
   
8. for city in path:
   
9.     print(city)
   
10. 
    
11. print(f"总距离：{path_distance(path)}")
    

复制代码

这个程序使用了一个简单的贪心算法，它可能无法找到最优解。

但是，它可以作为一个起点，你可以在此基础上对其进行优化，如使用模拟退火、遗传算法等更高级的算法。

创建一个PPT来解释你的代码，包括如何从CSV文件读取数据，以及你使用的算法原理。不要忘记将你的代码和PPT一起提交。


总代码：

1. import csv
   
2. import math
   
3. 
   
4. class City:
   
5.     def __init__(self, name, x, y):
   
6.         self.name = name
   
7.         self.x = x
   
8.         self.y = y
   
9.         
   
10.     def distance(self, city):
    
11.         return math.sqrt((self.x - city.x)**2 + (self.y - city.y)**2)
    
12. 
    
13.     def __str__(self):
    
14.         return f"{self.name} ({self.x}, {self.y})"
    
15.    
    
16. def read_cities_from_csv(file_path):
    
17.     cities = []
    
18.     with open(file_path, 'r', encoding='utf-8') as file:
    
19.         reader = csv.reader(file, delimiter=';')
    
20.         for row in reader:
    
21.             name, x, y = row
    
22.             cities.append(City(name.strip(), float(x), float(y)))
    
23.     return cities
    
24. 
    
25. def find_shortest_path(cities):
    
26.     unvisited_cities = cities.copy()
    
27.     starting_city = unvisited_cities.pop(0)
    
28.     visited_cities = [starting_city]
    
29.    
    
30.     while unvisited_cities:
    
31.         closest_city = min(unvisited_cities, key=lambda city: visited_cities[-1].distance(city))
    
32.         visited_cities.append(closest_city)
    
33.         unvisited_cities.remove(closest_city)
    
34.         
    
35.     visited_cities.append(starting_city)
    
36.    
    
37.     return visited_cities
    
38. 
    
39. def path_distance(path):
    
40.     distance = 0
    
41.     for i in range(len(path) - 1):
    
42.         distance += path[i].distance(path[i + 1])
    
43.     return distance
    
44. 
    
45. def main():
    
46.     cities = read_cities_from_csv("china.csv")
    
47.     path = find_shortest_path(cities)
    
48.     print("最短路径为：")
    
49.     for city in path:
    
50.         print(city)
    
51. 
    
52.     print(f"总距离：{path_distance(path)}")
    
53. 
    
54. if __name__ == '__main__':
    
55.     main()
    

复制代码

贪心算法是一种简单但有效的解决问题的方法，它在每一步都选择局部最优解，希望最终得到的结果是全局最优解。

贪心算法的主要优点是它通常具有较低的时间复杂度，因为它不需要遍历所有可能的解空间。

然而，贪心算法的一个缺点是它并不能保证找到全局最优解，特别是在一些需要全局考虑的问题中。

在解决TSP问题的情况下，我们使用的贪心算法是这样的：

• 选择一个初始城市，并将其标记为已访问。
• 从未访问的城市中找到离当前城市最近的城市。
• 将找到的城市标记为已访问，并将其作为当前城市。
• 重复步骤2-3，直到所有城市都被访问过。
• 最后返回到初始城市，完成整个路径。
  

这种贪心算法的想法是，在每一步都选择距离当前城市最近的下一个城市，这样可以在每个步骤中选择较短的路径。

然而，这种方法并不总是能找到最短的路径，因为它只关注局部最优解，而不是全局最优解。

尽管贪心算法在TSP问题上可能无法找到最优解，但它仍然可以作为其他更复杂算法（如模拟退火、遗传算法等）的一个参考起点。

在实际应用中，可以结合不同的算法来解决问题，以获得更好的性能和结果。

江山是个艺术家

用Python实现

歌者文明清理员

sfqxx 发表于 2023-4-5 16:58
请把里面的内容粘贴过来

chatgpt？

isdkz

江山是个艺术家 发表于 2023-4-5 17:06
用Python实现

我的代码中就是用的python呀

江山是个艺术家

isdkz 发表于 2023-4-5 17:19
我的代码中就是用的python呀

老师让用遗传算法，但是你这个坐标怎么没了

isdkz

江山是个艺术家 发表于 2023-4-5 17:27
老师让用遗传算法，但是你这个坐标怎么没了

什么坐标没了？

江山是个艺术家

isdkz 发表于 2023-4-5 17:28
什么坐标没了？

文件里的坐标

isdkz

江山是个艺术家 发表于 2023-4-5 17:33
文件里的坐标

不是有吗？

isdkz

这个是遗传算法的：

遗传算法是一种基于自然选择和遗传原理的全局优化搜索算法。它适用于解决一些较难的优化问题，如TSP问题。

遗传算法的基本思想是通过模拟自然界中的遗传和变异过程，在解空间中搜索全局最优解。以下是使用遗传算法解决TSP问题的基本步骤：

• 随机生成初始种群：创建一定数量的随机路径（称为染色体），每个路径表示一个城市访问顺序的解决方案。
  
• 评估适应度：计算每个染色体的适应度值，即路径长度的倒数。适应度值越高，表示解决方案越优秀。
  
• 选择：按照某种选择策略（如轮盘赌、锦标赛选择等）从当前种群中选取一定数量的染色体，作为下一代种群的父代。
  
• 交叉（或称为杂交、重组）：根据设定的交叉概率，将父代染色体进行配对并交换部分基因，生成新的子代染色体。常用的交叉方法有顺序交叉、部分映射交叉（PMX）等。
  
• 变异：根据设定的变异概率，随机调整子代染色体的部分基因。变异可以引入新的基因特征，避免算法陷入局部最优解。常用的变异方法有交换变异、逆序变异等。
  
• 更新种群：将子代染色体替换原种群，形成新的种群。
  
• 终止条件：如果达到预设的迭代次数或找到满足要求的解，结束算法。否则，返回第2步，继续迭代。
  

遗传算法在TSP问题上表现较好，因为它能搜索解空间的较大范围，并以较高概率找到全局最优解。

然而，遗传算法的时间复杂度和空间复杂度较高，需要调整参数（如交叉概率、变异概率等）以获得最佳性能。

示例代码：

1. import csv
   
2. import random
   
3. import math
   
4. from typing import List, Tuple
   
5. 
   
6. class City:
   
7.     def __init__(self, name: str, longitude: float, latitude: float):
   
8.         self.name = name
   
9.         self.longitude = longitude
   
10.         self.latitude = latitude
    
11. 
    
12.     def __repr__(self):
    
13.         return self.name
    
14. 
    
15. def euclidean_distance(city1: City, city2: City) -> float:
    
16.     x_diff = city1.longitude - city2.longitude
    
17.     y_diff = city1.latitude - city2.latitude
    
18.     return math.sqrt(x_diff ** 2 + y_diff ** 2)
    
19. 
    
20. def load_cities_from_csv(file_path: str) -> List[City]:
    
21.     cities = []
    
22.     with open(file_path, "r", encoding="utf-8") as file:
    
23.         csv_reader = csv.reader(file, delimiter=";")
    
24.         for row in csv_reader:
    
25.             city = City(row[0], float(row[1]), float(row[2]))
    
26.             cities.append(city)
    
27.     return cities
    
28. 
    
29. def path_distance(path: List[City]) -> float:
    
30.     distance = sum(euclidean_distance(path[i - 1], path[i]) for i in range(1, len(path)))
    
31.     distance += euclidean_distance(path[-1], path[0])  # 最后一个城市返回到第一个城市
    
32.     return distance
    
33. 
    
34. class GeneticAlgorithm:
    
35.     def __init__(
    
36.         self,
    
37.         cities: List[City],
    
38.         population_size: int = 100,
    
39.         generations: int = 1000,
    
40.         mutation_rate: float = 0.01,
    
41.         elite_size: int = 10
    
42.     ):
    
43.         self.cities = cities
    
44.         self.population_size = population_size
    
45.         self.generations = generations
    
46.         self.mutation_rate = mutation_rate
    
47.         self.elite_size = elite_size
    
48. 
    
49.     def create_population(self) -> List[List[City]]:
    
50.         return [random.sample(self.cities, len(self.cities)) for _ in range(self.population_size)]
    
51. 
    
52.     def fitness(self, path: List[City]) -> float:
    
53.         return 1 / path_distance(path)
    
54. 
    
55.     def selection(self, population: List[List[City]]) -> List[List[City]]:
    
56.         ranked_population = sorted(population, key=self.fitness, reverse=True)
    
57.         selected = ranked_population[:self.elite_size]
    
58.         weights = [self.fitness(path) for path in ranked_population]
    
59.         selected.extend(random.choices(ranked_population, weights, k=self.population_size - self.elite_size))
    
60.         return selected
    
61. 
    
62.     def crossover(self, parent1: List[City], parent2: List[City]) -> List[City]:
    
63.         start, end = random.sample(range(len(parent1)), 2)
    
64.         start, end = min(start, end), max(start, end)
    
65. 
    
66.         child = [None] * len(parent1)
    
67.         child[start:end] = parent1[start:end]
    
68. 
    
69.         for city in parent2[end:] + parent2[:end]:
    
70.             if city not in child:
    
71.                 index = child.index(None)
    
72.                 child[index] = city
    
73. 
    
74.         return child
    
75. 
    
76.     def mutate(self, path: List[City]) -> List[City]:
    
77.         for i in range(len(path)):
    
78.             if random.random() < self.mutation_rate:
    
79.                 j = random.randint(0, len(path) - 1)
    
80.                 path[i], path[j] = path[j], path[i]
    
81.         return path
    
82. 
    
83.     def evolve(self, population: List[List[City]]) -> List[List[City]]:
    
84.         selected = self.selection(population)
    
85.         children = []
    
86. 
    
87.         for i in range(0, len(selected) - 1, 2):
    
88.             child1 = self.crossover(selected[i], selected[i + 1])
    
89.             child2 = self.crossover(selected[i + 1], selected[i])
    
90.             children.extend([child1, child2])
    
91.         
    
92.             if len(children) < len(population):
    
93.                 children.append(selected[-1])
    
94.         return [self.mutate(child) for child in children]
    
95. 
    
96.     def run(self) -> Tuple[List[City], float]:
    
97.         population = self.create_population()
    
98. 
    
99.         for _ in range(self.generations):
    
100.             population = self.evolve(population)
     
101. 
     
102.         best_path = max(population, key=self.fitness)
     
103.         return best_path, path_distance(best_path)
     
104.    
     
105. # 读取城市数据
     
106. cities = load_cities_from_csv("china.csv")
     
107. # 运行遗传算法
     
108. ga = GeneticAlgorithm(cities, population_size=100, generations=1000, mutation_rate=0.01, elite_size=10)
     
109. best_path, distance = ga.run()
     
110. #输出结果
     
111. print("最短路径为：")
     
112. for city in best_path:
     
113.     print(f"{city.name} ({city.longitude}, {city.latitude})")
     
114. print(f"总距离：{distance}")
     

复制代码

这个示例代码实现了一个针对china.csv数据的遗传算法。它首先从csv文件中读取城市数据，然后运行遗传算法以寻找最佳路径。在运行结束时，它将输出所找到的最佳路径以及其总距离。

请注意，由于遗传算法是一种随机算法，每次运行时找到的解可能略有不同。为了获得更好的结果，可以尝试增加种群大小、代数或改变其他参数。

sfqxx

歌者文明清理员 发表于 2023-4-5 17:07
chatgpt？

？？？

阿奇_o

歌者文明清理员 发表于 2023-4-5 17:07
chatgpt？

哈哈，至少利用里类似ChatGPT的工具，并很可能是加上了自动化脚本监测论坛上的提问。。
不然，这位 isdkz 难道是神仙，随时随地盯着论坛，基本每个提问10分钟之内它就会回复，回答的内容也有迹可循。。

反正，我观察 它 好多天了。。