如何用Python实现旅行商问题模拟退火中的邻解生成？

核心实现思路 #

要生成符合要求的邻解，关键是随机选取两个索引i和j（满足j > i+1），并反转列表中i到j区间的元素。借助Python的列表切片和random模块可以轻松实现该逻辑。

代码实现 #

方法一：简洁的索引校验逻辑

import random

def generate_neighbor(route):
    route_length = len(route)
    # 随机选两个不同索引，排序后确保间隔大于1
    while True:
        i, j = sorted(random.sample(range(route_length), 2))
        if j - i > 1:
            break
    # 反转i到j的子序列，生成新路线
    new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]
    return new_route

方法二：直接生成符合条件的索引

import random

def generate_neighbor(route):
    route_length = len(route)
    # 先选i，再从i+2到末尾范围选j，天然满足j > i+1
    i = random.randint(0, route_length - 3)
    j = random.randint(i + 2, route_length - 1)
    # 反转子序列生成新路线
    new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]
    return new_route

代码说明 #

• 两种方法都能避免生成无意义的邻解（比如反转相邻元素或单个元素），严格遵循j > i+1的规则。
• 切片操作route[i:j+1][::-1]：先通过route[i:j+1]取出i到j的元素（Python切片为左闭右开，因此用j+1包含j位置），再通过[::-1]反转该子序列。
• 函数返回新列表，不会修改原路线，适配模拟退火算法中保留原解的需求。

测试示例 #

initial_route = ['A', 'B', 'C', 'D', 'E', 'F']
neighbor_route = generate_neighbor(initial_route)
print(neighbor_route)  # 可能输出: ['A', 'B', 'F', 'E', 'D', 'C']（对应i=1, j=5的情况）

内容的提问来源于stack exchange，提问作者João Oliveira