本文目录导读：
我来详细讲解如何使用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])
}
核心要点
- 暴力求解：适合小规模（≤8个城市），保证最优解
- 最近邻算法：简单高效，但可能陷入局部最优
- 2-opt优化：显著改善路径质量，实用性强
- 贪心算法：利用MST构建初始解，质量较好
- 性能考虑：实际应用通常结合多种算法
这个案例展示了如何利用NetworkX构建图模型,并通过不同算法解决TSP问题。
