给定n个城市的x，y坐标，如何用python形成距离矩阵？

Question

我是一个编程新手，我想解决一个旅行推销员的问题，在给定n个不同城市的x和y坐标的情况下，如何用python求出距离矩阵？

Answer 1

我假设你的城市是放在一个平面上，而不是地球仪上，所以你可以使用纯欧氏距离。我还假设你有你的城市--例如，在python字典中输入数据，就像这样。

cities = {
    "london": (4.15, 5.89),
    "paris": (2, 4),
    "prague": (1,5),
 }

方括号里的数值是对应的坐标。

然后，你将需要定义一个函数来计算基于坐标的欧几里得距离。

def distance_between(point_a, point_b):
    return math.sqrt((point_a[0] - point_b[0])**2 + (point_a[1] - point_b[1])**2)

你还需要一个函数来根据你的输入生成距离矩阵。你将在这里使用距离计算函数。

def get_matrix(cities):
    distance_matrix = {}
    for city_a in cities:
        distance_matrix[city_a] = {}
        for city_b in cities:
            distance_matrix[city_a][city_b] = distance_between(
                    cities[city_a], cities[city_b])

return distance_matrix

现在你有了所有的东西，你可以像这样使用它。

distances = get_matrix(cities)
print(distances["london"]["london"])
print(distances["paris"]["prague"])

这个例子的输出只是两个数字

0.0
1.4142135623730951

不要忘了在这个例子中 import math 在你的.py文件的开头