求助求助 tsp问题,Python交流,编程语言专区,鱼C论坛

江山是个艺术家 发表于 2023-4-5 16:50:35

求助求助 tsp问题

大佬们，来帮我看看这大一老师布置的作业正常吗
哪位大佬来帮我写个代码出来
万分感谢！！！

sfqxx 发表于 2023-4-5 16:58:43

请把里面的内容粘贴过来

isdkz 发表于 2023-4-5 16:58:43

本帖最后由 isdkz 于 2023-4-5 17:19 编辑

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

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

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

import csv
import math

class City:
def __init__(self, name, x, y):
   self.name = name
   self.x = x
   self.y = y

def distance(self, city):
   return math.sqrt((self.x - city.x)**2 + (self.y - city.y)**2)

def __str__(self):
   return f"{self.name} ({self.x}, {self.y})"

def read_cities_from_csv(file_path):
cities = []
with open(file_path, 'r', encoding='utf-8') as file:
   reader = csv.reader(file, delimiter=';')
   for row in reader:
         name, x, y = row
         cities.append(City(name.strip(), float(x), float(y)))
return cities

cities = read_cities_from_csv("china.csv")

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

def find_shortest_path(cities):
unvisited_cities = cities.copy()
starting_city = unvisited_cities.pop(0)
visited_cities =

while unvisited_cities:
   closest_city = min(unvisited_cities, key=lambda city: visited_cities[-1].distance(city))
   visited_cities.append(closest_city)
   unvisited_cities.remove(closest_city)

visited_cities.append(starting_city)

return visited_cities

path = find_shortest_path(cities)

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

def path_distance(path):
distance = 0
for i in range(len(path) - 1):
   distance += path.distance(path)
return distance

print("最短路径为：")
for city in path:
print(city)

print(f"总距离：{path_distance(path)}")

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

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

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

总代码：
import csv
import math

class City:
def __init__(self, name, x, y):
   self.name = name
   self.x = x
   self.y = y

def distance(self, city):
   return math.sqrt((self.x - city.x)**2 + (self.y - city.y)**2)

def __str__(self):
   return f"{self.name} ({self.x}, {self.y})"

def read_cities_from_csv(file_path):
cities = []
with open(file_path, 'r', encoding='utf-8') as file:
   reader = csv.reader(file, delimiter=';')
   for row in reader:
         name, x, y = row
         cities.append(City(name.strip(), float(x), float(y)))
return cities

def find_shortest_path(cities):
unvisited_cities = cities.copy()
starting_city = unvisited_cities.pop(0)
visited_cities =

while unvisited_cities:
   closest_city = min(unvisited_cities, key=lambda city: visited_cities[-1].distance(city))
   visited_cities.append(closest_city)
   unvisited_cities.remove(closest_city)

visited_cities.append(starting_city)

return visited_cities

def path_distance(path):
distance = 0
for i in range(len(path) - 1):
   distance += path.distance(path)
return distance

def main():
cities = read_cities_from_csv("china.csv")
path = find_shortest_path(cities)
print("最短路径为：")
for city in path:
   print(city)

print(f"总距离：{path_distance(path)}")

if __name__ == '__main__':
main()

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

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

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

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

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

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

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

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

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

江山是个艺术家 发表于 2023-4-5 17:06:28

用Python实现

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

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

chatgpt？

isdkz 发表于 2023-4-5 17:19:49

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

我的代码中就是用的python呀{:5_94:}

江山是个艺术家 发表于 2023-4-5 17:27:33

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

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

isdkz 发表于 2023-4-5 17:28:19

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

什么坐标没了？

江山是个艺术家 发表于 2023-4-5 17:33:23

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

文件里的坐标

isdkz 发表于 2023-4-5 17:38:22

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

不是有吗？

isdkz 发表于 2023-4-5 17:47:37

这个是遗传算法的：

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

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

[*]随机生成初始种群：创建一定数量的随机路径（称为染色体），每个路径表示一个城市访问顺序的解决方案。

[*]评估适应度：计算每个染色体的适应度值，即路径长度的倒数。适应度值越高，表示解决方案越优秀。

[*]选择：按照某种选择策略（如轮盘赌、锦标赛选择等）从当前种群中选取一定数量的染色体，作为下一代种群的父代。

[*]交叉（或称为杂交、重组）：根据设定的交叉概率，将父代染色体进行配对并交换部分基因，生成新的子代染色体。常用的交叉方法有顺序交叉、部分映射交叉（PMX）等。

[*]变异：根据设定的变异概率，随机调整子代染色体的部分基因。变异可以引入新的基因特征，避免算法陷入局部最优解。常用的变异方法有交换变异、逆序变异等。

[*]更新种群：将子代染色体替换原种群，形成新的种群。

[*]终止条件：如果达到预设的迭代次数或找到满足要求的解，结束算法。否则，返回第2步，继续迭代。

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

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

示例代码：
import csv
import random
import math
from typing import List, Tuple

class City:
def __init__(self, name: str, longitude: float, latitude: float):
   self.name = name
   self.longitude = longitude
   self.latitude = latitude

def __repr__(self):
   return self.name

def euclidean_distance(city1: City, city2: City) -> float:
x_diff = city1.longitude - city2.longitude
y_diff = city1.latitude - city2.latitude
return math.sqrt(x_diff ** 2 + y_diff ** 2)

def load_cities_from_csv(file_path: str) -> List:
cities = []
with open(file_path, "r", encoding="utf-8") as file:
   csv_reader = csv.reader(file, delimiter=";")
   for row in csv_reader:
         city = City(row, float(row), float(row))
         cities.append(city)
return cities

def path_distance(path: List) -> float:
distance = sum(euclidean_distance(path, path) for i in range(1, len(path)))
distance += euclidean_distance(path[-1], path)# 最后一个城市返回到第一个城市
return distance

class GeneticAlgorithm:
def __init__(
   self,
   cities: List,
   population_size: int = 100,
   generations: int = 1000,
   mutation_rate: float = 0.01,
   elite_size: int = 10
):
   self.cities = cities
   self.population_size = population_size
   self.generations = generations
   self.mutation_rate = mutation_rate
   self.elite_size = elite_size

def create_population(self) -> List]:
   return

def fitness(self, path: List) -> float:
   return 1 / path_distance(path)

def selection(self, population: List]) -> List]:
   ranked_population = sorted(population, key=self.fitness, reverse=True)
   selected = ranked_population[:self.elite_size]
   weights =
   selected.extend(random.choices(ranked_population, weights, k=self.population_size - self.elite_size))
   return selected

def crossover(self, parent1: List, parent2: List) -> List:
   start, end = random.sample(range(len(parent1)), 2)
   start, end = min(start, end), max(start, end)

   child = * len(parent1)
   child = parent1

   for city in parent2 + parent2[:end]:
         if city not in child:
            index = child.index(None)
            child = city

   return child

def mutate(self, path: List) -> List:
   for i in range(len(path)):
         if random.random() < self.mutation_rate:
            j = random.randint(0, len(path) - 1)
            path, path = path, path
   return path

def evolve(self, population: List]) -> List]:
   selected = self.selection(population)
   children = []

   for i in range(0, len(selected) - 1, 2):
         child1 = self.crossover(selected, selected)
         child2 = self.crossover(selected, selected)
         children.extend()

         if len(children) < len(population):
            children.append(selected[-1])
   return

def run(self) -> Tuple, float]:
   population = self.create_population()

   for _ in range(self.generations):
         population = self.evolve(population)

   best_path = max(population, key=self.fitness)
   return best_path, path_distance(best_path)

# 读取城市数据
cities = load_cities_from_csv("china.csv")
# 运行遗传算法
ga = GeneticAlgorithm(cities, population_size=100, generations=1000, mutation_rate=0.01, elite_size=10)
best_path, distance = ga.run()
#输出结果
print("最短路径为：")
for city in best_path:
print(f"{city.name} ({city.longitude}, {city.latitude})")
print(f"总距离：{distance}")

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

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

sfqxx 发表于 2023-4-5 18:22:15

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

？？？

阿奇_o 发表于 2023-4-6 09:32:41

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

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

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

页: [1]

鱼C论坛's Archiver

求助求助 tsp问题