旅行商问题#

traveling_salesman_problem(G, weight='weight', nodes=None, cycle=True, method=None, **kwargs)[源码]#

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

此函数提供对非完全图网络和/或旅行商无需访问所有节点的网络上的旅行商问题的近似解。

此函数分两步执行。首先，它使用 nodes 中节点之间的所有对最短路径创建一个完全图。新图中的边权重是原始图中每对节点之间路径的长度。其次，使用一种算法（对于无向图默认为 christofides，对于有向图默认为 asadpour_atsp）来近似此新图上的最小哈密顿回路。可用算法包括

  • christofides

  • greedy_tsp

  • simulated_annealing_tsp

  • threshold_accepting_tsp

  • asadpour_atsp

找到哈密顿回路后，此函数进行后处理以适应原始图的结构。如果 cycle 为 False，则移除权重最大的边以形成哈密顿路径。然后，分析中使用的这个新的完全图上的每条边都被原始图上这些节点之间的最短路径替换。如果输入图 G 包含权重不符合三角不等式的边，例如当 G 不是完全图时（即不存在的边的长度是无穷大），则返回的路径可能包含一些重复节点（起始节点除外）。

参数：
GNetworkX 图

一个可能带权重的图

nodes节点集合 (默认=G.nodes)

要访问的节点的集合（列表、集合等）

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

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

cyclebool (默认: True)

指示应返回回路还是路径。注意：回路是近似的最小回路。路径只是移除该回路中权重最大的边。

method函数 (默认: None)

一个函数，它返回包含所有节点的回路并近似解决完全图上的旅行商问题。返回的回路随后用于在 G 上找到相应的解。method 应该是可调用的；接受输入 G 和 weight；并返回沿着回路的节点列表。

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

如果 method is None：对于无向图 G 使用 christofides()，对于有向图 G 使用 asadpour_atsp()。

**kwargsdict

要传递给传入的 method 函数的其他关键字参数。

返回值：
列表

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

虽然不再强制要求，您仍然可以构建（柯里化）自己的函数来为方法提供参数值。

>>> SA_tsp = nx.approximation.simulated_annealing_tsp
>>> method = lambda G, weight: SA_tsp(G, "greedy", weight=weight, 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

否则，将其他关键字参数直接传递给 tsp 函数。

>>> path = tsp(
...     G,
...     cycle=False,
...     method=nx.approximation.simulated_annealing_tsp,
...     init_cycle="greedy",
...     temp=500,
... )
>>> path in ([4, 3, 2, 1, 0, 8, 7, 6, 5], [5, 6, 7, 8, 0, 1, 2, 3, 4])
True
在本页