python - 在 python 中为 2OPT 生成所有邻居

Question

我正在尝试针对无向旅行商问题实现 2opt 优化算法。对于给定的城市:

cities = [[ 72.06557466,   5.73765812],
   [ 94.50272578,  68.95162393],
   [ 58.53952609,  15.12518299],
   [ 94.64599891,  34.65906808],
   [ 62.42311036,  45.8430048 ],
   [ 24.73697454,   4.4159545 ],
   [ 15.71071819,  81.27575127],
   [ 65.65743227,  54.90239983],
   [  5.07828178,  47.34845887],
   [ 88.98592652,  48.14959719]]

我对一般算法的理解是，从随机游开始(在本例中为 10 个节点):

solution = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我需要为此解决方案生成所有 2opt 邻居(通过删除两条边并引入两条新边)。然后，计算每个此类相邻解决方案的成本。

def total_length( nodes, solution ):
    objective = distance( solution[-1], solution[0])
    for index in range(0, len(solution)-1):
        objective += distance(solution[index], solution[index+1])
    return objective

其中距离函数是两点之间的欧式距离。

然后选择最好的(成本最低的)。例如，这个邻近的旅游:

new_solution = [6, 8, 7, 9, 0, 1, 2, 3, 4, 5]

对于给定的解决方案，在 Python 中迭代所有相邻游览(避免冗余)的简单方法是什么？

Answer 1

您不需要遍历所有游览(我不确定您所说的“相邻游览”是什么意思)；您需要遍历现有游览中的所有边对。由于您已将游览存储为一系列节点，因此您只需要遍历节点，例如:

for i in range(0, len(solution)-3):
    for j in range(i+2, len(solution)-1):
        # evaluate 2-opt on edge (solution[i],solution[i+1]) and 
        # edge (solution[j],solution[j+1])

请注意，两条边不能共享一个节点，这就是 j 循环从 i+2 开始的原因。另请注意，当 j = =len(解)-1.