赫里斯托菲德

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

旅行商问题的一种近似解

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

参数

G图

G should be a complete weighted undirected graph. The distance between all pairs of nodes should be included.

weight字符串，可选(默认为“权重”)

与边权重对应的边数据关键点。如果任何边不具有该属性，则权重设定为1。

tree网络X图形或无(默认：无)

G的最小生成树，或者，如果没有最小生成树，则使用 networkx.minimum_spanning_tree()

返回

列表

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

工具书类

1

克里斯托菲德，尼科斯。“旅行推销员问题新启发式的最坏情况分析。”不是的。RR-388。宾夕法尼亚州匹兹堡卡内基-梅隆大学管理科学研究小组，1976。