traveling_salesman_problem

traveling_salesman_problem(G, weight='weight', nodes=None, cycle=True, method=None)

在中查找最短路径 G 正在连接指定的节点

在非完全图和/或推销员不需要访问所有节点的网络上，该函数允许近似解旅行商问题。

此函数分两步执行。首先，它使用中节点之间的所有对最短路径创建一个完整的图 nodes 。新图中的边权重是原始图中每对节点之间的路径长度。第二，算法(默认为： christofides 对于无定向和 asadpour_atsp 对于有向图)用来逼近这个新图上的最小哈密顿圈。可用的算法包括：

• 赫里斯托菲德

• greedy_tsp

• simulated_annealing_tsp

• threshold_accepting_tsp

• asadpour_atsp

一旦找到哈密顿圈，该函数就会进行后处理，以适应原始图形的结构。如果 cycle 是 False ，去除最大权重边以形成哈密顿路径。然后，用于该分析的新的完整图上的每条边被替换为原始图上那些节点之间的最短路径。

参数

G网络X图表

一个可能的赋权图

nodes节点集合(默认为G.Nodes)

集合(列表、集合等)要访问的节点的数量

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

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

cycle布尔值(默认值：TRUE)

指示是否应返回循环或路径。注：周期为近似最小周期。这条路径只是去掉了那个周期中最大的边。

method功能(默认：无)

一种函数，它返回所有节点上的一个圈，并在完全图上近似求解旅行商问题。然后使用返回的循环在以下位置上找到相应的解 G 。 method 应该是可调用的；接受输入 G ，以及 weight ；并返回循环中的节点列表。

提供的选项包括 christofides() ， greedy_tsp() ， simulated_annealing_tsp() 和 threshold_accepting_tsp() 。

如果 method is None ：使用 christofides() 对于无定向 G 和 threshold_accepting_tsp() 用于定向 G 。

要为这些提供的函数指定参数，请构造声明特定值的lambda函数。 method 必须有2个输入。(请参见示例)。

返回

列表

中的节点列表 G 沿着一条近似于最小路径通过的路径 nodes 。

加薪

NetworkXError

如果 G 是有向图，它必须是强连通的，否则无法生成完整版本。

实例

>>> tsp = nx.approximation.traveling_salesman_problem
>>> G = nx.cycle_graph(9)
>>> G[4][5]["weight"] = 5  # all other weights are 1
>>> tsp(G, nodes=[3, 6])
[3, 2, 1, 0, 8, 7, 6, 7, 8, 0, 1, 2, 3]
>>> path = tsp(G, cycle=False)
>>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
True

构建(Curry)您自己的函数以向方法提供参数值。

>>> SA_tsp = nx.approximation.simulated_annealing_tsp
>>> method = lambda G, wt: SA_tsp(G, "greedy", weight=wt, temp=500)
>>> path = tsp(G, cycle=False, method=method)
>>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
True