用A*算法、爬山法、遗传算法解决旅行商问题

Question

编写TSP（旅行商问题）的实例生成器，城市的位置用在单位正方形内的随机点表示。并分别用A*算法与爬山法、遗传算法来求解TSP问题实例。
以下是具体题目要求，用c++、python、java都可以！要标明并附上代码！

Answer 1

TechWhizKid参考GPT回答：

以下是使用A*算法、爬山法和遗传算法解决旅行商问题的示例代码：

A*算法：

import heapq

# 定义城市类
class City:
    def __init__(self, name, x, y):
        self.name = name
        self.x = x
        self.y = y

    def __str__(self):
        return self.name

# 计算两个城市之间的距离
def calculate_distance(city1, city2):
    return ((city2.x - city1.x) ** 2 + (city2.y - city1.y) ** 2) ** 0.5

# A*算法求解TSP问题
def solve_tsp_A_star(cities, start_city):
    # 定义优先队列
    pq = []
    heapq.heappush(pq, (0, [start_city], set()))

    while pq:
        cost, path, visited = heapq.heappop(pq)
        current_city = path[-1]

        # 判断是否已经访问过所有城市
        if len(path) == len(cities):
            return path, cost

        for city in cities:
            if city != current_city and city not in visited:
                new_cost = cost + calculate_distance(current_city, city)
                heuristic = calculate_distance(city, start_city)
                heapq.heappush(pq, (new_cost + heuristic, path + [city], visited | {city}))

    return None

# 示例生成器：生成随机城市列表
def generate_cities(num_cities):
    import random
    cities = []
    for i in range(num_cities):
        name = chr(ord('A') + i)
        x = random.random()
        y = random.random()
        cities.append(City(name, x, y))
    return cities

# 测试示例
cities = generate_cities(5)
start_city = cities[0]
path, cost = solve_tsp_A_star(cities, start_city)
print("Path:", ' -> '.join(str(city) for city in path))
print("Total Cost:", cost)

爬山法：

import random

# 评估路径的总距离
def evaluate_path(cities, path):
    total_distance = 0
    for i in range(len(path)):
        city1 = path[i]
        city2 = path[(i + 1) % len(path)]
        total_distance += calculate_distance(cities[city1], cities[city2])
    return total_distance

# 随机生成初始路径
def generate_initial_path(num_cities):
    path = list(range(num_cities))
    random.shuffle(path)
    return path

# 爬山法求解TSP问题
def solve_tsp_hill_climbing(cities):
    num_cities = len(cities)
    current_path = generate_initial_path(num_cities)
    current_cost = evaluate_path(cities, current_path)

    while True:
        neighbors = []
        for i in range(num_cities):
            for j in range(i + 1, num_cities):
                neighbor = current_path.copy()
                neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
                neighbors.append(neighbor)

        best_neighbor = None
        best_neighbor_cost = float('inf')
        for neighbor in neighbors:
            neighbor_cost = evaluate_path(cities, neighbor)
            if neighbor_cost < best_neighbor_cost:
                best_neighbor = neighbor
                best_neighbor_cost = neighbor_cost

        if best_neighbor_cost < current_cost:
            current_path = best_neighbor
            current_cost = best_neighbor_cost
        else:
            break

    return current_path, current_cost

# 测试示例
cities = generate_cities(5)
path, cost = solve_tsp_hill_climbing(cities)
print("Path:", ' -> '.join(cities[i].name for i in path))
print("Total Cost:", cost)

遗传算法：

import random

# 生成初始种群
def generate_initial_population(num_cities, population_size):
    population = []
    for _ in range(population_size):
        path = list(range(num_cities))
        random.shuffle(path)
        population.append(path)
    return population

# 评估个体路径的适应度（倒数距离）
def evaluate_fitness(cities, path):
    distance = evaluate_path(cities, path)
    return 1 / distance

# 选择父代个体
def selection(population, fitness):
    # 使用轮盘赌选择方法
    total_fitness = sum(fitness)
    probabilities = [fit / total_fitness for fit in fitness]
    selected_indices = random.choices(range(len(population)), probabilities, k=2)
    return [population[idx] for idx in selected_indices]

# 交叉生成子代个体
def crossover(parent1, parent2):
    # 使用顺序交叉算子
    num_cities = len(parent1)
    start = random.randint(0, num_cities - 2)
    end = random.randint(start + 1, num_cities - 1)
    child = [-1] * num_cities

    # 保留父代1的部分路径
    for i in range(start, end + 1):
        child[i] = parent1[i]

    # 填充子代剩余部分
    index = 0
    for i in range(num_cities):
        if child[index] == -1:
            while parent2[index] in child:
                index = (index + 1) % num_cities
            child[index] = parent2[index]
            index = (index + 1) % num_cities

    return child

# 变异个体
def mutate(individual):
    # 使用交换变异算子
    index1 = random.randint(0, len(individual) - 1)
    index2 = random.randint(0, len(individual) - 1)
    individual[index1], individual[index2] = individual[index2], individual[index1]
    return individual

# 遗传算法求解TSP问题
def solve_tsp_genetic(cities, population_size, num_generations):
    num_cities = len(cities)
    population = generate_initial_population(num_cities, population_size)
    best_path = None
    best_cost = float('inf')

    for _ in range(num_generations):
        fitness = [evaluate_fitness(cities, path) for path in population]

        for i in range(population_size):
            if fitness[i] > best_cost:
                best_path = population[i]
                best_cost = fitness[i]

        new_population = [best_path]

        while len(new_population) < population_size:
            parent1, parent2 = selection(population, fitness)
            child = crossover(parent1, parent2)
            child = mutate(child)
            new_population.append(child)

        population = new_population

    return best_path, 1 / best_cost

# 测试

示例
cities = generate_cities(5)
path, cost = solve_tsp_genetic(cities, population_size=10, num_generations=100)
print("Path:", ' -> '.join(cities[i].name for i in path))
print("Total Cost:", cost)

4.3

import random

# 评估路径的总距离
def evaluate_path(cities, path):
    total_distance = 0
    for i in range(len(path)):
        city1 = path[i]
        city2 = path[(i + 1) % len(path)]
        total_distance += calculate_distance(cities[city1], cities[city2])
    return total_distance

# 随机生成初始路径
def generate_initial_path(num_cities):
    path = list(range(num_cities))
    random.shuffle(path)
    return path

# 爬山法求解TSP问题
def solve_tsp_hill_climbing(cities):
    num_cities = len(cities)
    current_path = generate_initial_path(num_cities)
    current_cost = evaluate_path(cities, current_path)

    while True:
        neighbors = []
        for i in range(num_cities):
            for j in range(i + 1, num_cities):
                neighbor = current_path.copy()
                neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
                neighbors.append(neighbor)

        best_neighbor = None
        best_neighbor_cost = float('inf')
        for neighbor in neighbors:
            neighbor_cost = evaluate_path(cities, neighbor)
            if neighbor_cost < best_neighbor_cost:
                best_neighbor = neighbor
                best_neighbor_cost = neighbor_cost

        if best_neighbor_cost < current_cost:
            current_path = best_neighbor
            current_cost = best_neighbor_cost
        else:
            break

    return current_path, current_cost

# 使用MST启发式的A*算法求解TSP问题
def solve_tsp_A_star_MST(cities, start_city):
    # 构建MST
    def build_MST(cities):
        visited = set()
        mst = []

        current_city = start_city
        visited.add(current_city)

        while len(visited) < len(cities):
            min_distance = float('inf')
            nearest_city = None

            for city in cities:
                if city != current_city and city not in visited:
                    distance = calculate_distance(current_city, city)
                    if distance < min_distance:
                        min_distance = distance
                        nearest_city = city

            mst.append((current_city, nearest_city))
            visited.add(nearest_city)
            current_city = nearest_city

        return mst

    # 计算MST的总代价
    def calculate_MST_cost(mst):
        total_cost = 0
        for edge in mst:
            total_cost += calculate_distance(edge[0], edge[1])
        return total_cost

    # 启发式函数：剩余路径的最小生成树代价
    def heuristic(city, visited):
        remaining_cities = set(cities) - visited
        remaining_mst = build_MST(remaining_cities)
        remaining_cost = calculate_MST_cost(remaining_mst)
        return remaining_cost

    # A*算法求解TSP问题
    def solve_tsp_A_star(cities, start_city):
        pq = []
        heapq.heappush(pq, (0, [start_city], set()))

        while pq:
            cost, path, visited = heapq.heappop(pq)
            current_city = path[-1]

            if len(path) == len(cities):
                return path, cost

            for city in cities:
                if city != current_city and city not in visited:
                    new_cost = cost + calculate_distance(current_city, city)
                    h = heuristic(city, visited)
                    heapq.heappush(pq, (new_cost + h, path + [city], visited | {city}))

        return None

    mst = build_MST(cities)
    mst_cost = calculate_MST_cost(mst)
    path, cost = solve_tsp_A_star(cities, start_city)
    return path, cost, mst_cost

# 测试示例
cities = generate_cities(5)
start_city = cities[0]

# 使用爬山法求解TSP问题
hill_climbing_path, hill_climbing_cost = solve_tsp_hill_climbing(cities)

# 使用MST启发式的A*算法求解TSP问题
a_star_path, a_star_cost, mst_cost = solve_tsp_A_star_MST(cities, start_city)

print("Hill Climbing Path:", ' -> '.join(cities[i].name for i in hill_climbing_path))
print("Hill Climbing Cost:", hill_climbing_cost)
print()
print("A* with MST Heuristic Path:", ' -> '.join(cities[i].name for i in a_star_path))
print("A* with MST Heuristic Cost:", a_star_cost)
print("Minimum Spanning Tree (MST) Cost:", mst_cost)