基于DataFrame求解遍历所有城市的最短闭环路径问题

嘿，你遇到的这个问题就是经典的旅行商问题（Traveling Salesman Problem, TSP）——核心就是找一条经过所有城市恰好一次、起点和终点相同的最短闭环路径。针对你的城市距离DataFrame，我给你两种实用的解决思路，适配不同的城市数量规模：

第一步：先把DataFrame转换成标准距离矩阵 #

首先我们需要把你的表格数据转换成算法能识别的距离矩阵格式，假设你的DataFrame是如下结构（我修正了可能的排版误差，确保距离矩阵的合理性）：

import pandas as pd
import numpy as np

# 你的原始数据（修正排版后）
data = {
    'From City': ['City A', 'City B', 'City C', 'City D'],
    'City A': [0, 577, 175, 2166],
    'City B': [577, 0, 1806, 2092],
    'City C': [175, 1806, 0, 653],
    'City D': [2166, 2092, 653, 0]
}
df = pd.DataFrame(data).set_index('From City')

# 转换成numpy格式的距离矩阵，提取城市名称列表
distance_matrix = df.values
cities = df.index.tolist()

方法一：暴力枚举（适合城市数量≤10的场景） #

如果你的城市数量很少（比如你这里只有4个），直接枚举所有可能的路径是最直接的方式——因为4个城市的有效闭环路径只有(4-1)! = 6种，计算量极小。我们可以用scipy的暴力优化工具来实现：

from scipy.optimize import brute

def calculate_total_distance(permutation, distance_matrix):
    # 构建闭环路径：起点固定为第一个城市（索引0），最后回到起点
    path = np.concatenate([[0], permutation, [0]])
    total = 0
    for i in range(len(path)-1):
        total += distance_matrix[int(path[i])][int(path[i+1])]
    return total

# 城市数量
n_cities = len(cities)
# 暴力枚举所有除起点外的城市排列
result = brute(calculate_total_distance,
              ranges=[tuple(range(1, n_cities))]*(n_cities-1),
              args=(distance_matrix,),
              full_output=True)

# 解析最优结果
best_permutation = result[0].astype(int)
best_path_indices = [0] + list(best_permutation) + [0]
best_total_distance = result[1]
best_city_path = [cities[i] for i in best_path_indices]

# 输出结果
print(f"最短闭环路径: {' → '.join(best_city_path)}")
print(f"总距离: {best_total_distance}")

运行这段代码后，你就能得到经过所有城市的最短闭环路径和对应的总距离。

方法二：用Google OR-Tools求解（适合中大规模场景） #

如果你的城市数量超过10个，暴力枚举的计算量会指数级增长，这时候就需要用启发式算法来高效求解。Google的OR-Tools是一个免费的开源工具，专门解决这类组合优化问题：

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

# 构建TSP问题的数据模型
def create_tsp_data(distance_matrix):
    data = {
        'distance_matrix': distance_matrix.tolist(),
        'num_vehicles': 1,  # 只需要一辆车（一条路径）
        'depot': 0  # 起点设为City A（索引0）
    }
    return data

# 解析并输出求解结果
def print_tsp_solution(manager, routing, solution, cities):
    print(f"总距离: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    city_path = []
    while not routing.IsEnd(index):
        city_index = manager.IndexToNode(index)
        city_path.append(cities[city_index])
        index = solution.Value(routing.NextVar(index))
    # 添加终点（回到起点）
    city_path.append(cities[manager.IndexToNode(index)])
    print(f"最短闭环路径: {' → '.join(city_path)}")
    return city_path

# 初始化数据模型
data = create_tsp_data(distance_matrix)

# 创建路由管理器和模型
manager = pywrapcp.RoutingIndexManager(
    len(data['distance_matrix']),
    data['num_vehicles'],
    data['depot']
)
routing = pywrapcp.RoutingModel(manager)

# 定义距离回调函数
def distance_callback(from_index, to_index):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# 设置搜索策略（用PATH_CHEAPEST_ARC快速找到可行解，再优化）
search_params = pywrapcp.DefaultRoutingSearchParameters()
search_params.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)

# 求解问题
solution = routing.SolveWithParameters(search_params)

# 输出结果
if solution:
    print_tsp_solution(manager, routing, solution, cities)

这个方法即使面对几十上百个城市也能高效找到近似最优解（甚至最优解），非常实用。

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