Python案例如何用Networkx做旅行商问题

wen python案例 2026-07-16 210

本文目录导读：

安装必要的库
基础案例：完全图上的TSP
2-opt优化算法
使用贪心算法构建初始解
性能对比与分析
核心要点

我来详细讲解如何使用NetworkX库解决旅行商问题(TSP)。

安装必要的库

pip install networkx numpy matplotlib

基础案例：完全图上的TSP

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations
def create_tsp_graph(cities, distances):
    """创建TSP问题的完全图"""
    G = nx.complete_graph(len(cities))
    # 添加城市名称属性
    city_labels = {i: city for i, city in enumerate(cities)}
    nx.set_node_attributes(G, city_labels, 'name')
    # 添加边权重（距离）
    for i in range(len(cities)):
        for j in range(i+1, len(cities)):
            G[i][j]['weight'] = distances[i][j]
    return G
def brute_force_tsp(G):
    """暴力求解TSP（小规模数据用）"""
    nodes = list(G.nodes())
    if len(nodes) > 8:
        print("节点数量过多，建议使用近似算法")
        return None, float('inf')
    best_path = None
    min_distance = float('inf')
    # 固定起点为0，减少计算量
    start_node = nodes[0]
    other_nodes = nodes[1:]
    for perm in permutations(other_nodes):
        path = [start_node] + list(perm)
        distance = 0
        # 计算路径总距离
        for i in range(len(path)):
            current = path[i]
            next_node = path[(i + 1) % len(path)]
            distance += G[current][next_node]['weight']
        if distance < min_distance:
            min_distance = distance
            best_path = path
    return best_path, min_distance
def nearest_neighbor_tsp(G, start_node=0):
    """最近邻近似算法"""
    unvisited = set(G.nodes())
    current = start_node
    path = [current]
    unvisited.remove(current)
    total_distance = 0
    while unvisited:
        # 找到最近的未访问节点
        nearest = min(unvisited, key=lambda x: G[current][x]['weight'])
        total_distance += G[current][nearest]['weight']
        current = nearest
        path.append(current)
        unvisited.remove(current)
    # 返回起点
    total_distance += G[current][start_node]['weight']
    path.append(start_node)
    return path, total_distance
def visualize_tsp_path(G, path, title="TSP Solution"):
    """可视化TSP路径"""
    pos = nx.spring_layout(G, seed=42)
    plt.figure(figsize=(12, 8))
    # 绘制所有边（浅色）
    nx.draw_networkx_edges(G, pos, alpha=0.2, edge_color='gray')
    # 绘制路径边
    path_edges = [(path[i], path[i+1]) for i in range(len(path)-1)]
    nx.draw_networkx_edges(G, pos, edgelist=path_edges, 
                          edge_color='red', width=2, alpha=0.8)
    # 绘制节点
    nx.draw_networkx_nodes(G, pos, node_size=500, node_color='lightblue')
    nx.draw_networkx_labels(G, pos, labels=nx.get_node_attributes(G, 'name'))
    # 添加边权重标签
    edge_labels = nx.get_edge_attributes(G, 'weight')
    nx.draw_networkx_edge_labels(G, pos, edge_labels, font_size=8)
    plt.title(title)
    plt.axis('off')
    return plt
# 示例：中国主要城市
cities = ['北京', '上海', '广州', '深圳', '成都', '武汉']
# 城市间距离矩阵（单位：公里）
distances = [
    [0, 1215, 1888, 1947, 1542, 1051],     # 北京
    [1215, 0, 1210, 1060, 1660, 688],       # 上海
    [1888, 1210, 0, 130, 1240, 830],        # 广州
    [1947, 1060, 130, 0, 1350, 900],        # 深圳
    [1542, 1660, 1240, 1350, 0, 980],       # 成都
    [1051, 688, 830, 900, 980, 0]           # 武汉
]
# 创建图
G = create_tsp_graph(cities, distances)
# 暴力求解
print("暴力求解TSP:")
best_path, min_distance = brute_force_tsp(G)
if best_path:
    city_names = [cities[i] for i in best_path]
    print(f"最优路径: {' -> '.join(city_names)}")
    print(f"总距离: {min_distance:.1f} 公里")
# 最近邻算法
print("\n最近邻近似算法:")
path_nn, dist_nn = nearest_neighbor_tsp(G, 0)
city_names_nn = [cities[i] for i in path_nn]
print(f"路径: {' -> '.join(city_names_nn)}")
print(f"总距离: {dist_nn:.1f} 公里")
# 可视化
visualize_tsp_path(G, best_path if best_path else path_nn, 
                   "TSP最优路径 (暴力求解)")
plt.show()

2-opt优化算法

def two_opt_improvement(G, path):
    """2-opt局部搜索优化"""
    improved = True
    best_path = path.copy()
    # 去掉最后一个节点（回到起点的重复）
    if best_path[0] == best_path[-1]:
        best_path = best_path[:-1]
    n = len(best_path)
    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                # 计算当前路径距离
                current_distance = (
                    G[best_path[i-1]][best_path[i]]['weight'] +
                    G[best_path[j-1]][best_path[j]]['weight']
                )
                # 计算交换后的距离
                new_distance = (
                    G[best_path[i-1]][best_path[j-1]]['weight'] +
                    G[best_path[i]][best_path[j]]['weight']
                )
                if new_distance < current_distance:
                    # 交换路径段
                    best_path = best_path[:i] + best_path[i:j][::-1] + best_path[j:]
                    improved = True
        # 如果优化了，重置循环
        if improved:
            continue
    # 添加回到起点的节点
    best_path.append(best_path[0])
    return best_path
def calculate_total_distance(G, path):
    """计算路径总距离"""
    total = 0
    for i in range(len(path)-1):
        total += G[path[i]][path[i+1]]['weight']
    return total
# 使用2-opt优化
print("\n使用2-opt优化的最近邻算法:")
initial_path, _ = nearest_neighbor_tsp(G, 0)
improved_path = two_opt_improvement(G, initial_path)
improved_distance = calculate_total_distance(G, improved_path)
city_names_opt = [cities[i] for i in improved_path]
print(f"初始路径: {' -> '.join([cities[i] for i in initial_path])}")
print(f"初始距离: {calculate_total_distance(G, initial_path):.1f} 公里")
print(f"优化后路径: {' -> '.join(city_names_opt)}")
print(f"优化后距离: {improved_distance:.1f} 公里")
print(f"优化比例: {(1 - improved_distance/calculate_total_distance(G, initial_path))*100:.1f}%")
# 可视化优化后的路径
visualize_tsp_path(G, improved_path, "TSP优化后路径 (2-opt)")
plt.show()

使用贪心算法构建初始解

def greedy_initial_solution(G):
    """贪心算法构建初始解"""
    n = len(G.nodes())
    edges = []
    # 获取所有边并按权重排序
    for u, v, data in G.edges(data=True):
        edges.append((data['weight'], u, v))
    edges.sort()  # 按权重升序排序
    # Kruskal算法构建最小生成树
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    def union(x, y):
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
            return True
        return False
    mst_edges = []
    for weight, u, v in edges:
        if union(u, v):
            mst_edges.append((u, v, weight))
    # 从MST构建路径（深度优先遍历）
    mst_graph = nx.Graph()
    mst_graph.add_edges_from([(u, v, {'weight': w}) for u, v, w in mst_edges])
    # 使用DFS生成路径
    path = list(nx.dfs_preorder_nodes(mst_graph, source=0))
    path.append(path[0])  # 回到起点
    return path
# 使用贪心算法
print("\n贪心算法构建初始解:")
greedy_path = greedy_initial_solution(G)
greedy_distance = calculate_total_distance(G, greedy_path)
city_names_greedy = [cities[i] for i in greedy_path]
print(f"路径: {' -> '.join(city_names_greedy)}")
print(f"总距离: {greedy_distance:.1f} 公里")
# 对贪心解进行2-opt优化
improved_greedy_path = two_opt_improvement(G, greedy_path)
improved_greedy_distance = calculate_total_distance(G, improved_greedy_path)
city_names_improved = [cities[i] for i in improved_greedy_path]
print(f"\n优化后路径: {' -> '.join(city_names_improved)}")
print(f"优化后距离: {improved_greedy_distance:.1f} 公里")
print(f"优化比例: {(1 - improved_greedy_distance/greedy_distance)*100:.1f}%")

性能对比与分析

import time
def benchmark_tsp_methods(G):
    """对比不同TSP方法的性能"""
    methods = {
        '暴力求解': brute_force_tsp,
        '最近邻算法': lambda g: nearest_neighbor_tsp(g, 0),
        '贪心+MST': greedy_initial_solution,
        '最近邻+2opt': lambda g: two_opt_improvement(g, nearest_neighbor_tsp(g, 0)[0])
    }
    results = []
    for name, method in methods.items():
        start_time = time.time()
        try:
            if name == '暴力求解':
                path, distance = method(G)
            elif name == '贪心+MST':
                path = method(G)
                distance = calculate_total_distance(G, path)
            else:
                path, distance = method(G)
            elapsed_time = time.time() - start_time
            results.append({
                '方法': name,
                '路径长度': distance,
                '执行时间': elapsed_time
            })
            print(f"{name}: 距离={distance:.1f}km, 时间={elapsed_time:.4f}s")
        except Exception as e:
            print(f"{name}: 执行失败 - {str(e)}")
    return results
# 执行性能对比
print("\n性能对比:")
if len(cities) <= 8:
    results = benchmark_tsp_methods(G)
else:
    print("城市数量过多，跳过暴力求解")
    methods = {
        '最近邻算法': lambda g: nearest_neighbor_tsp(g, 0),
        '贪心+MST': greedy_initial_solution,
        '最近邻+2opt': lambda g: two_opt_improvement(g, nearest_neighbor_tsp(g, 0)[0])
    }