用 Python 解决旅行商问题的 2-opt 算法

Question

我在 Python 中找不到 2-opt 算法的任何完整实现，因此我尝试将缺失的部分添加到此处找到的代码中，我将在下面介绍。

def two_opt(route):
     best = route
     improved = True
     while improved:
          improved = False
          for i in range(1, len(route)-2):
               for j in range(i+1, len(route)):
                    if j-i == 1: continue # changes nothing, skip then
                    new_route = route[:]
                    new_route[i:j] = route[j-1:i-1:-1] # this is the 2woptSwap
                    if cost(new_route) < cost(best):  # what should cost be?
                         best = new_route
                         improved = True
          route = best
     return best

为了完成这段代码，我编写了一个小程序，从文本文件中提取长/纬度坐标，并用每个点的成本填充邻接矩阵。可以在Code Review上找到完整的代码，包括输入坐标和邻接矩阵的样本。

因为我不知道什么cost功能是从上面的代码，我的想法是制定出所有从一个点到另一个点的费用，并放置在邻接矩阵：adj_matrix。这表示每个点与其他点的距离。

我尝试将我的成本/邻接矩阵传递给函数来使用它，但是我无法计算给定邻接矩阵的成本。

def main():
    # code to read from file
    # code to append co-ordinates to points and calculate the haversine distance between each point
    route = random.sample(range(10), 10)
    best = two_opt(route, adj_matrix)  # passing my adjacency matrix
    print(best)

ValueError：包含多个元素的数组的真值不明确。使用 a.any() 或 a.all()

另一个 Python 2-opt 问题：在 python 中为 2OPT 生成所有邻居

关于如何从邻接矩阵中找到正确成本的任何建议将不胜感激。

Answer 1

首先，邻接矩阵通常是 (0, 1) 矩阵。这里有不同的称为成本、权重或距离矩阵。

现在回答你的问题。

成本函数可以简单如下：

def cost(cost_mat, route):
   return cost_mat[np.roll(route, 1), route].sum()

在这里，np.roll()将路线“旋转”一个位置，以便于使用它来route索引成本矩阵。只需sum()将各个路段的成本相加即可计算路线的总成本。

（如果在某个时候您决定查看非对称 TSP，则需要确保行/列顺序与cost_mat构造方式相匹配；对于欧几里得 TSP，这并不重要，因为成本矩阵是对称的。）

使用示例：

cost_mat = np.array([
   [0, 1, 2, 3],
   [1, 0, 4, 5],
   [2, 4, 0, 7],
   [3, 5, 7, 0],
])

route = np.array([2, 1, 3, 0])

print(cost(cost_mat, route))