- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,
E>
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 perhaps the simplest and most straightforward TSP heuristic. The key to this algorithm is to always visit the nearest city.
The tour computed with a Nearest-Neighbor-Heuristic
can vary depending on the first
vertex visited. The first vertex for the next or for multiple subsequent tour computations (calls
of getTour(Graph)
) can be specified in the constructors
NearestNeighborHeuristicTSP(Object)
or NearestNeighborHeuristicTSP(Iterable)
.
This can be used for example to ensure that the first vertices visited are different for
subsequent calls of getTour(Graph)
. Once each specified first vertex is used, the first
vertex in subsequent tour computations is selected randomly from the graph. Alternatively
NearestNeighborHeuristicTSP(Random)
or NearestNeighborHeuristicTSP(long)
can be
used to specify a Random
used to randomly select the vertex visited first.
The implementation of this class is based on:
Nilsson, Christian. "Heuristics for the traveling salesman problem." Linkoping University 38
(2003)
The runtime complexity of this class is $O(V^2)$.
This algorithm requires that the graph is complete.
-
Field Summary
Fields -
Constructor Summary
ConstructorsModifierConstructorDescriptionConstructor.NearestNeighborHeuristicTSP
(long seed) ConstructorNearestNeighborHeuristicTSP
(Iterable<V> initialVertices) Constructorprivate
NearestNeighborHeuristicTSP
(Iterable<V> initialVertices, Random rng) ConstructorConstructorNearestNeighborHeuristicTSP
(V first) Constructor -
Method Summary
Modifier and TypeMethodDescriptionprivate int
getFirstVertexIndex
(List<V> path) Returns the start vertex of the tour about to compute.private static <V,
E> int getNearestNeighbor
(V current, V[] vertices, int start, Graph<V, E> g) Find the vertex in the range staring atfrom
that is closest to the element at index from-1.Computes a tour using the nearest neighbour heuristic.Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
-
Field Details
-
rng
-
initiaVertex
Nulled, if it has no next
-
-
Constructor Details
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP()Constructor. By default a random vertex is chosen to start. -
NearestNeighborHeuristicTSP
Constructor- Parameters:
first
- First vertex to visit- Throws:
NullPointerException
- if first is null
-
NearestNeighborHeuristicTSP
Constructor- Parameters:
initialVertices
- The Iterable of vertices visited first in subsequent tour computations (per call ofgetTour(Graph)
another vertex of the Iterable is used as first)- Throws:
NullPointerException
- if first is null
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP(long seed) Constructor- Parameters:
seed
- seed for the random number generator
-
NearestNeighborHeuristicTSP
Constructor- Parameters:
rng
- Random number generator- Throws:
NullPointerException
- if rng is null
-
NearestNeighborHeuristicTSP
Constructor- Parameters:
initialVertices
- The Iterable of vertices visited first in subsequent tour computations, or null to choose at randomrng
- Random number generator
-
-
Method Details
-
getTour
Computes a tour using the nearest neighbour heuristic.- Parameters:
graph
- the input graph- Returns:
- a tour
- Throws:
IllegalArgumentException
- if the graph is not undirectedIllegalArgumentException
- if the graph is not completeIllegalArgumentException
- if the graph contains no verticesIllegalArgumentException
- if the specified initial vertex is not in the graph
-
getFirstVertexIndex
Returns the start vertex of the tour about to compute.- Parameters:
path
- the initial path, containing all vertices in unspecified order- Returns:
- the vertex to start with
- Throws:
IllegalArgumentException
- if the specified initial vertex is not in the graph
-
getNearestNeighbor
Find the vertex in the range staring atfrom
that is closest to the element at index from-1.- Parameters:
current
- the vertex for which the nearest neighbor is searchedvertices
- the vertices of the graph. The unvisited neighbors start at indexstart
start
- the index of the first vertex to considerg
- the graph containing the vertices- Returns:
- the index of the unvisited vertex closest to the vertex at firstNeighbor-1.
-