asadpour_atsp(G, weight='weight', seed=None, source=None)
This approximate solution is one of the best known approximations for the asymmetric traveling salesman problem developed by Asadpour et al, . 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.
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.
Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.
Indicator of random number generation state. See Randomness<randomness>
.
If given, return the cycle starting and ending at the given node.
If G is not complete or has less than two nodes, the algorithm raises an exception.
If 'source` is not :None:None:`None` and is not a node in G, the algorithm raises an exception.
If G is an undirected graph.
Returns the cycle (list of nodes) that a salesman can follow to minimize the total weight of the trip.
Returns an approximate solution to the traveling salesman problem.
>>> import networkx as nxSee :
... 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]
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them