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

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 问题： Generate all neighbors for 2OPT in python

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

原文由 rrz0 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

首先， 邻接矩阵通常是 (0, 1)-matrix 。您在此处拥有的内容被称为 _成本_、 重量 或 _距离矩阵_。

现在回答你的问题。

成本函数可以很简单：

 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))

原文由 NPE 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

2-opt 删除两条边并创建两条新边（假设成本矩阵是对称的），因此成本函数可以简化为仅考虑变化的边。对于大型阵列，这比枚举整个路线要快得多。

 import numpy as np

def cost_change(cost_mat, n1, n2, n3, n4):
    return cost_mat[n1][n3] + cost_mat[n2][n4] - cost_mat[n1][n2] - cost_mat[n3][n4]

def two_opt(route, cost_mat):
    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
                if cost_change(cost_mat, best[i - 1], best[i], best[j - 1], best[j]) < 0:
                    best[i:j] = best[j - 1:i - 1:-1]
                    improved = True
        route = best
    return best

if __name__ == '__main__':
    nodes = 1000
    init_route = list(range(nodes))
    print(init_route)
    cost_mat = np.random.randint(100, size=(nodes, nodes))
    cost_mat += cost_mat.T
    np.fill_diagonal(cost_mat, 0)
    cost_mat = list(cost_mat)
    best_route = two_opt(init_route, cost_mat)
    print(best_route)

原文由 Fradge 发布，翻译遵循 CC BY-SA 4.0 许可协议