Tsp¶
- class Tsp(graph)[source]¶
Bases:
GraphOptimizationApplication
Optimization application for the “traveling salesman problem” [1] based on a NetworkX graph.
References
[1]: “Travelling salesman problem”, https://en.wikipedia.org/wiki/Travelling_salesman_problem
- Parameters:
graph (nx.Graph | np.ndarray | list) – A graph representing a problem. It can be specified directly as a NetworkX graph, or as an array or list format suitable to build out a NetworkX graph.
Attributes
- graph¶
Getter of the graph
- Returns:
A graph for a problem
Methods
- static create_random_instance(n, low=0, high=100, seed=None)[source]¶
Create a random instance of the traveling salesman problem
- draw(result=None, pos=None)¶
Draw a graph with the result. When the result is None, draw an original graph without colors.
- Parameters:
result (OptimizationResult | np.ndarray | None) – The calculated result for the problem
- interpret(result)[source]¶
Interpret a result as a list of node indices
- Parameters:
result (OptimizationResult | np.ndarray) – The calculated result of the problem
- Returns:
A list of nodes whose indices correspond to its order in a prospective cycle.
- Return type:
- static parse_tsplib_format(filename)[source]¶
Read a graph in TSPLIB format from file and return a Tsp instance.
Only the EUC_2D edge weight format is supported.
- Parameters:
filename (str) – the name of the file.
- Raises:
QiskitOptimizationError – If the type is not “TSP”
QiskitOptimizationError – If the edge weight type is not “EUC_2D”
- Returns:
A Tsp instance data.
- Return type:
- static sample_most_likely(state_vector)¶
Compute the most likely binary string from state vector.
- Parameters:
state_vector (QuasiDistribution | Statevector | np.ndarray | dict) – state vector or counts or quasi-probabilities.
- Returns:
binary string as numpy.ndarray of ints.
- Raises:
ValueError – if state_vector is not QuasiDistribution, Statevector, np.ndarray, or dict.
- Return type:
np.ndarray