python-tsp 0.3.1

安装

pip install python-tsp

例子

给定一个作为 numpy 数组的距离矩阵，很容易以最低成本计算哈密顿路径。例如，要使用动态编程方法：

import numpy as np
from python_tsp.exact import solve_tsp_dynamic_programming

distance_matrix = np.array([
    [0,  5, 4, 10],
    [5,  0, 8,  5],
    [4,  8, 0,  3],
    [10, 5, 3,  0]
])
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)

解将是[0, 1, 3, 2]，总距离为 17。注意它始终是一条闭合路径，因此在节点 2 之后我们回到 0。

要使用元启发式方法解决相同的问题：

from python_tsp.heuristics import solve_tsp_simulated_annealing

permutation, distance = solve_tsp_simulated_annealing(distance_matrix)

请记住，作为元启发式，解决方案可能因执行而异，并且不能保证最优性。但是，在较大的情况下，它可能是一种更快的选择。

如果您使用的是开放式 TSP 版本（不需要返回原点），只需将距离矩阵第一列的所有元素设置为零：

distance_matrix[:, 0] = 0
permutation, distance = solve_tsp_dynamic_programming(distance_matrix)

在这种情况下，我们得到[0, 2, 3, 1]，距离为 12。请注意，在这种情况下，距离矩阵实际上是不对称的，这里的方法也适用。

前面的示例假设您已经有一个距离矩阵。如果不是这种情况，距离模块已经准备了一些函数来计算欧几里得距离矩阵或 大圆距离。

例如，如果您有一个数组，其中每一行都有一个点的纬度和经度，

import numpy as np
from python_tsp.distances import great_circle_distance_matrix

sources = np.array([
    [ 40.73024833, -73.79440675],
    [ 41.47362495, -73.92783272],
    [ 41.26591   , -73.21026228],
    [ 41.3249908 , -73.507788  ]
])
distance_matrix = great_circle_distance_matrix(sources)

有关更多示例和可用方法列表，请参阅项目的存储库。