TSP问题贪心法代码实现

旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，涉及一个旅行商访问一系列城市并返回起点，寻求最短路径。贪心算法是一种启发式解法，它并不保证总是得到全局最优解，但可以提供相对接近的答案。

下面是一个简单的Python贪心算法实现，假设我们已经有一个按距离排序的城市列表：

def tsp_greedy(cities):
    # 初始化，选择第一个城市作为起始点
    tour = [0]
    current_city = cities[0]

    for city in cities[1:]:
        # 贪心策略：每次添加下一个最近的城市
        next_city = min((city, distance(current_city, city)) for city in cities if city not in tour)
        tour.append(next_city[0])
        current_city = next_city[0]

    # 回到起点完成旅程，并计算总距离
    tour.append(tour[0])  # 添加起点
    total_distance = sum(distance(city1, city2) for city1, city2 in zip(tour, tour[1:]))

    return tour, total_distance

# 假设distance函数用于计算两个城市之间的欧氏距离或其他合适的度量
def distance(city1, city2):
    # 这里只是一个示例，实际应替换为计算两点间距离的实际代码
    x1, y1 = city1
    x2, y2 = city2
    return ((x2 - x1)**2 + (y2 - y1)**2) ** 0.5

# 使用示例
cities = [(0, 0), (1, 4), (3, 7), (6, 2)]
tour, total_distance = tsp_greedy(cities)
print("Tour:", tour)
print("Total Distance:", total_distance)