给定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 文件的开头

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

Given the x,y co-ordinates of n cities how to form the distance matrix using python?

python

euclidean-distance