asadpour_atsp

asadpour_atsp(G, weight='weight', seed=None, source=None)

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

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

Parameters:

Gnx.DiGraph

图应为一个完整的加权有向图。所有节点对之间的距离应包括在内，并且应满足三角不等式。也就是说，任意两个节点之间的直接边应为成本最低的路径。

weightstring, 可选 (默认=”weight”)

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

seedinteger, random_state, 或 None (默认)

随机数生成状态的指示符。 参见 Randomness。

source节点标签 (默认=`None`)

如果给定，返回从给定节点开始和结束的循环。

Returns:

cycle节点列表

返回销售员可以遵循以最小化旅行总权重的循环（节点列表）。

Raises:

NetworkXError

如果`G`不完整或节点数少于两个，算法会引发异常。

NetworkXError

如果`source`不是`None`且不是`G`中的节点，算法会引发异常。

NetworkXNotImplemented

如果`G`是无向图。

References

[1]

A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan, 和 A. Saberi, 非对称旅行商问题的o(log n/log log n)近似算法, 运筹学, 65 (2017), pp. 1043–1061

Examples

>>> 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]