dwave_networkx.algorithms.tsp.traveling_salesperson#
- traveling_salesperson(G, sampler=None, lagrange=None, weight='weight', start=None, **sampler_args)[source]#
Returns an approximate minimum traveling salesperson route.
Defines a QUBO with ground states corresponding to the minimum routes and uses the sampler to sample from it.
A route is a cycle in the graph that reaches each node exactly once. A minimum route is a route with the smallest total edge weight.
- Parameters:
G (NetworkX graph) – The graph on which to find a minimum traveling salesperson route. This should be a complete graph with non-zero weights on every edge.
sampler – A binary quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Unconstrained Binary Optimization Problem (QUBO). A sampler is expected to have a ‘sample_qubo’ and ‘sample_ising’ method. A sampler is expected to return an iterable of samples, in order of increasing energy. If no sampler is provided, one must be provided using the set_default_sampler function.
lagrange (number, optional (default None)) – Lagrange parameter to weight constraints (visit every city once) versus objective (shortest distance route).
weight (optional (default 'weight')) – The name of the edge attribute containing the weight.
start (node, optional) – If provided, the route will begin at start.
sampler_args – Additional keyword parameters are passed to the sampler.
- Returns:
route – List of nodes in order to be visited on a route
- Return type:
Examples
>>> import dimod ... >>> G = nx.Graph() >>> G.add_weighted_edges_from({(0, 1, .1), (0, 2, .5), (0, 3, .1), (1, 2, .1), ... (1, 3, .5), (2, 3, .1)}) >>> dnx.traveling_salesperson(G, dimod.ExactSolver(), start=0) [0, 1, 2, 3]
Notes
Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.