java.lang.Object
org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
org.jgrapht.alg.tour.HeldKarpTSP<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,
E>
A dynamic programming algorithm for the TSP problem.
The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?".
This is an implementation of the Held-Karp algorithm which returns a optimal, minimum-cost Hamiltonian tour. The implementation requires the input graph to contain at least one vertex. The running time is $O(2^{|V|} \times |V|^2)$ and it takes $O(2^{|V|} \times |V|)$ extra memory.
See wikipedia for more details about TSP.
See wikipedia for more details about the dynamic programming algorithm.
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate double[][]
private static void
fill
(double[][] array, double value) Computes a minimum-cost Hamiltonian tour.private double
memo
(int previousNode, int state, double[][] c, double[][] w) reconstructTour
(List<V> indexList, double[][] w, double[][] c) Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
-
Constructor Details
-
HeldKarpTSP
public HeldKarpTSP()
-
-
Method Details
-
memo
private double memo(int previousNode, int state, double[][] c, double[][] w) -
getTour
Computes a minimum-cost Hamiltonian tour.- Parameters:
graph
- the input graph- Returns:
- a minimum-cost tour if one exists, null otherwise
- Throws:
IllegalArgumentException
- if the graph contains no verticesIllegalArgumentException
- if the graph contains more than 31 vertices
-
computeMinimumWeights
-
fill
private static void fill(double[][] array, double value) -
reconstructTour
-