asadpour_atsp#

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

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

该近似解是由Asadour等人开发的非对称旅行推销员问题的最著名的近似之一， [1]. 该算法首先求解Hold-Karp松弛，以求出循环重量的下界。接下来，它构造了无向生成树的指数分布，其中边在树中的概率对应于使用最大熵舍入方案的边的权重。接下来，我们将对该分布进行采样 \(2 \lceil \ln n \rceil\) 一旦圆弧的方向被添加回边缘，对最小采样树进行计时并保存。最后，我们扩大然后缩短该图，以找到推销员的近似巡回路线。

参数

Gnx.DiGraph: 该图应该是一个完全的加权有向图。所有节点之间的距离应该包括在内，并且三角不等式应该成立。也就是说，任意两个节点之间的直边应该是代价最小的路径。
weight字符串，可选(默认为“权重”): 与边权重对应的边数据关键点。如果任何边不具有该属性，则权重设定为1。
seed整数、随机状态或无（默认）: 随机数生成状态的指示器。见 Randomness .
source节点标签(默认为`无`): 如果给定，则返回在给定节点开始和结束的周期。

返回

cycle节点列表: 返回销售人员可以遵循的周期(节点列表)，以最大限度地减少行程的总重量。

加薪

NetworkXError: 如果 G 不完整或少于两个节点，则该算法将引发异常。
NetworkXError: 如果‘Source`不是 None 并且不是中的节点 G 时，该算法会引发异常。
NetworkXNotImplemented: 如果 G 是一个无向图。

工具书类

1: A·A·阿萨普尔、M·X·戈曼斯、A·马德里、S·O·加兰和A·萨贝里，非对称旅行商问题的o(logn/logn)-近似算法，运筹学，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]