asadpour_atsp#

asadpour_atsp(G, weight='weight', seed=None, source=None)[源代码]#

返回旅行商问题的近似解。

这个近似解是 Asadpour 等人开发的非对称旅行商问题最好的已知近似解之一，见 [1]。该算法首先求解 Held-Karp 松弛问题，以找到环权重的一个下界。接下来，它使用最大熵舍入方案构建无向生成树的指数分布，其中边在树中的概率对应于该边的权重。接下来，我们对该分布采样 \(2 \lceil \ln n \rceil\) 次，并在将弧的方向添加回边后保存最小的采样树。最后，我们增强然后短路该图，以找到旅行商的近似路径。

参数:

Gnx.DiGraph: 图应为完整的有权有向图。所有节点对之间的距离应包含在内，并且应满足三角不等式。也就是说，任意两个节点之间的直接边应为成本最低的路径。
weight字符串，可选 (默认为“weight”): 对应边权重的边数据键。如果任何边没有此属性，则权重设为 1。
seed整数，random_state 或 None (默认): 随机数生成状态的指示器。参见随机性。
source节点标签 (默认为 `None`): 如果给定，返回从给定节点开始和结束的环。

返回:

cycle节点列表: 返回旅行商为最小化旅行总权重可以遵循的环（节点列表）。

引发:

NetworkXError: 如果 G 不完整或节点少于两个，则算法引发异常。
NetworkXError: 如果 source 不是 None 且不是 G 中的节点，则算法引发异常。
NetworkXNotImplemented: 如果 G 是无向图。

参考文献

[1]

A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan, and A. Saberi, An o(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem, Operations research, 65 (2017), pp. 1043–1061

示例

>>> import networkx as nx
>>> import networkx.algorithms.approximation as approx
>>> G = nx.complete_graph(3, create_using=nx.DiGraph)
>>> nx.set_edge_attributes(
...     G,
...     {(0, 1): 2, (1, 2): 2, (2, 0): 2, (0, 2): 1, (2, 1): 1, (1, 0): 1},
...     "weight",
... )
>>> tour = approx.asadpour_atsp(G, source=0)
>>> tour
[0, 2, 1, 0]