1.用贪心法求解TSP问题。要求输出图的邻接矩阵及最短路径。py

贪心算法通常不是求解旅行商问题（Traveling Salesman Problem, TSP）的理想选择，因为TSP是一个NP-hard问题，意味着它不容易找到全局最优解。然而，有一种近似的贪心策略叫做" nearest neighbor" 或 "nearest pair" 算法，它可以找到相对较好的局部最优解。

对于简单的贪心算法，我们可以按顺序访问最近的城市，直到所有城市都遍历过一次，形成一个闭合环路。以下是使用Python实现的一个基本版本，假设输入是一组二维坐标表示的城市：

import numpy as np

# 假设 `cities` 是一个二维数组，每个元素代表一个城市的坐标
def nearest_neighbor_tsp(cities):
    # 计算每对城市之间的距离
    distances = cdist(cities, cities, 'euclidean')  # 使用欧几里得距离
    n = len(cities)

    # 初始化路径
    path = [0]
    
    for i in range(1, n):
        current_city = path[-1]
        next_city_index = np.argmin(distances[current_city])
        path.append(next_city_index)
        
    # 回到起点形成闭合路径
    path.append(0)

    return path, distances[path]

# 距离计算函数
from scipy.spatial.distance import cdist

# 示例：
cities = np.array([[0, 0], [1, 2], [3, 4], [5, 6]])
path, shortest_distances = nearest_neighbor_tsp(cities)

print("Path:", path)
print("Shortest Distances (as a matrix):")
print(shortest_distances)

请注意，这个方法得到的是一个较优的解决方案，但它并不保证是最小生成树（Minimum Spanning Tree, MST），因此也不是TSP问题的精确解。如果需要更精确的结果，可以考虑使用其他搜索算法如动态规划（如果问题是完全图）或者启发式搜索算法（如遗传算法、模拟退火等）。