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:

list

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.