求助求助 tsp问题

江山是个艺术家

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

2023-4-5 16:49 上传

点击文件名下载附件

sfqxx

请把里面的内容粘贴过来

isdkz

这是一个关于解决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 = [starting_city]
    
    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[i].distance(path[i + 1])
    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 = [starting_city]
    
    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[i].distance(path[i + 1])
    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问题上可能无法找到最优解，但它仍然可以作为其他更复杂算法（如模拟退火、遗传算法等）的一个参考起点。

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

江山是个艺术家

用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问题上表现较好，因为它能搜索解空间的较大范围，并以较高概率找到全局最优解。

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

示例代码：

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[City]:
    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[0], float(row[1]), float(row[2]))
            cities.append(city)
    return cities

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

class GeneticAlgorithm:
    def __init__(
        self, 
        cities: List[City], 
        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[List[City]]:
        return [random.sample(self.cities, len(self.cities)) for _ in range(self.population_size)]

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

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

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

        child = [None] * len(parent1)
        child[start:end] = parent1[start:end]

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

        return child

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

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

        for i in range(0, len(selected) - 1, 2):
            child1 = self.crossover(selected[i], selected[i + 1])
            child2 = self.crossover(selected[i + 1], selected[i])
            children.extend([child1, child2])
        
            if len(children) < len(population):
                children.append(selected[-1])
        return [self.mutate(child) for child in children]

    def run(self) -> Tuple[List[City], 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 17:07
chatgpt？

？？？

阿奇_o

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

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

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