christofides

christofides(G, weight='weight', tree=None)

近似求解旅行商问题

使用 Christofides [1] 算法，计算完全无向图上旅行商问题的 3/2 近似解。

参数:

G图

G 应该是一个完全加权无向图。应包含所有节点对之间的距离。

weight字符串, 可选 (默认值=”weight”)

对应于边权重的边数据键。如果任何边没有此属性，则权重设为 1。

treeNetworkX 图 或 None (默认值: None)

G 的最小生成树。如果为 None，则使用 networkx.minimum_spanning_tree() 计算最小生成树。

返回值:

列表

沿 G 中节点的列表，形成一个近似度为 3/2 的最小哈密顿圈。

参考文献

[1]

Christofides, Nicos. “Worst-case analysis of a new heuristic for the travelling salesman problem.” No. RR-388. Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976.