christofides

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

近似求解旅行商问题

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

Parameters:

G图

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

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

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

treeNetworkX图或None (默认: None)

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

Returns:

列表

G 中沿着一个3/2近似最小哈密顿环的节点列表。

References

[1]

Christofides, Nicos. “旅行商问题的新启发式算法的 最坏情况分析.” No. RR-388. Carnegie-Mellon Univ Pittsburgh Pa 管理科学研究组, 1976.