traveling_salesman_problem#

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

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

此函数允许在非完全图和/或不需要访问所有节点的网络中近似解决旅行商问题。

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

  • christofides

  • greedy_tsp

  • simulated_annealing_tsp

  • threshold_accepting_tsp

  • asadpour_atsp

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

Parameters:
GNetworkX 图

一个可能有权重的图

nodes节点集合（默认=G.nodes）

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

weight字符串，可选（默认=”weight”）

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

cycle布尔值（默认: True）

指示是否应返回一个循环，还是一个路径。注意：该循环是近似的最小循环。路径只是移除该循环中的最大边。

method函数（默认: None）

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

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

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

**kwargs字典

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

Returns:
列表

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

Raises:
NetworkXError

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

Examples

>>> tsp = nx.approximation.traveling_salesman_problem
>>> G = nx.cycle_graph(9)
>>> G[4][5]["weight"] = 5  # 所有其他权重为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
On this page