如何优化TSP旅行商问题2-opt算法的时间复杂度

你的原始实现实际运行复杂度为O(n³)，核心冗余开销来自两处：一是每次枚举交换对时都生成完整新路径数组，二是每次交换后从头遍历计算整条路径的总长度，城市规模稍大就会出现明显卡顿。以下是可落地的优化方案，优化后复杂度降至O(n²)，支持千级到万级城市规模的快速求解。

核心优化手段 #

• 预计算距离矩阵：提前计算所有城市两两之间的距离存为n×n矩阵，后续取距离直接O(1)访问，彻底消除重复计算范数、坐标差的开销。
• 增量计算交换收益：2-opt反转i到k段路径时，仅会改动4条边：删除原路径的(i-1,i)和(k,k+1)，新增(i-1,k)和(i,k+1)，不需要重算整条路径长度，只要计算这4条边的长度差就能判断交换是否有收益，单次交换判断开销从O(n)降到O(1)。
• 移除冗余数组拷贝：不需要每次交换都拼接生成全新的路径数组，仅在确认交换有收益时，原地反转路径中i到k的片段即可。
• 优化迭代策略：找到第一个有效收益后立刻重启内层循环枚举，避免在已经更新过的路径上做无效判断，大幅减少外层迭代轮次。
• 向量化替代原生循环：距离矩阵计算用numpy广播实现，比Python原生for循环快1~2个数量级。

优化后完整代码 #

import numpy as np
import pandas as pd
from sklearn.preprocessing import MinMaxScaler
from math import radians, cos, sin

def calc_dist_matrix(coords):
    """向量化预计算欧式距离矩阵，经纬度场景可替换为哈弗辛距离计算逻辑"""
    diff = coords[:, np.newaxis, :] - coords[np.newaxis, :, :]
    return np.sqrt(np.sum(diff ** 2, axis=-1))

def two_opt_opt(cities, improvement_threshold=1e-3):
    n = cities.shape[0]
    dist_mat = calc_dist_matrix(cities)
    # 初始化路径
    route = np.arange(n)
    # 初始路径总长度：roll移位直接对齐相邻点对
    best_distance = np.sum(dist_mat[route, np.roll(route, -1)])

    while True:
        distance_to_beat = best_distance
        has_improved = False
        
        for i in range(1, n - 2):
            i_prev = route[i-1]
            i_curr = route[i]
            old_edge_len1 = dist_mat[i_prev, i_curr]
            
            for k in range(i + 1, n):
                k_curr = route[k]
                k_next = route[(k + 1) % n]
                old_edge_len2 = dist_mat[k_curr, k_next]
                
                new_edge_len1 = dist_mat[i_prev, k_curr]
                new_edge_len2 = dist_mat[i_curr, k_next]
                # 长度差为负说明交换后路径更短
                delta = new_edge_len1 + new_edge_len2 - old_edge_len1 - old_edge_len2
                
                if delta < 0:
                    # 原地反转i到k段，无额外全数组拷贝开销
                    route[i:k+1] = route[i:k+1][::-1]
                    best_distance += delta
                    has_improved = True
                    # 首次提升策略：找到有效交换即重启枚举，速度最快
                    # 若追求更优解可注释下述两行，遍历找本轮最大收益交换再更新
                    break
            if has_improved:
                break
        
        if not has_improved:
            break
        improvement_factor = 1 - best_distance / distance_to_beat
        if improvement_factor <= improvement_threshold:
            break

    return route, best_distance

# --------------- 原有数据处理逻辑无需修改 ---------------
# 经纬度转平面投影坐标
lat = cities2['lattitude'].map(radians)
lon = cities2['longitude'].map(radians)
x = lon.map(cos)*lat.map(cos)*6371
y = lon.map(cos)*lat.map(sin)*6371

cities2["lat_radians"] = lat
cities2["lon_radians"] = lon
cities2["x"] = x
cities2["y"] = y

df = cities.copy()
scaler = MinMaxScaler(feature_range=(0, 100), copy=True)
scaled_df = scaler.fit_transform(df)
scaled_df = pd.DataFrame(scaled_df, columns=['x1', 'x2'])
scaled = np.asarray(scaled_df)

# 替换原有的two_opt调用即可
route, total_dist = two_opt_opt(scaled, 0.001)

进一步扩容优化 #

如果需要支撑万级以上城市规模的求解，可以叠加两个优化：

• 近邻截断：枚举交换对时，只给每个点匹配距离最近的20~30个邻居作为候选交换点，不需要枚举所有其他城市，复杂度可降到接近线性。
• JIT编译：用numba给核心双重循环加即时编译装饰，不需要修改逻辑就能再获得10~20倍的速度提升。

内容的提问来源于stack exchange，提问作者user13303557