Skip to main content
`Ctrl`+`K`

# asadpour_atsp

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

  Returns an approximate solution to the traveling salesman problem.

  This approximate solution is one of the best known approximations for the asymmetric traveling salesman problem developed by Asadpour et al, [1]. The algorithm first solves the Held-Karp relaxation to find a lower bound for the weight of the cycle. Next, it constructs an exponential distribution of undirected spanning trees where the probability of an edge being in the tree corresponds to the weight of that edge using a maximum entropy rounding scheme. Next we sample that distribution \(2 \lceil \ln n \rceil\) times and save the minimum sampled tree once the direction of the arcs is added back to the edges. Finally, we augment then short circuit that graph to find the approximate tour for the salesman.

  Parameters:
    G nx.DiGraph

      The graph should be a complete weighted directed graph. The distance between all paris of nodes should be included and the triangle inequality should hold. That is, the direct edge between any two nodes should be the path of least cost.

    weight string, optional (default=”weight”)

      Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

    source node label (default=`None`)

      If given, return the cycle starting and ending at the given node.

  Returns:
    cycle list of nodes

      Returns the cycle (list of nodes) that a salesman can follow to minimize the total weight of the trip.

  Raises:
    NetworkXError

      If `G` is not complete or has less than two nodes, the algorithm raises an exception.

    NetworkXError

      If `source` is not `None` and is not a node in `G`, the algorithm raises an exception.

    NetworkXNotImplemented

      If `G` is an undirected graph.

  References

  [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

  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]