- java.lang.Object
-
- org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
-
- org.jgrapht.alg.tour.NearestNeighborHeuristicTSP<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
HamiltonianCycleAlgorithm<V,E>
public class NearestNeighborHeuristicTSP<V,E> extends HamiltonianCycleAlgorithmBase<V,E>
The nearest neighbour heuristic 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 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 ofgetTour(Graph)
) can be specified in the constructorsNearestNeighborHeuristicTSP(Object)
orNearestNeighborHeuristicTSP(Iterable)
. This can be used for example to ensure that the first vertices visited are different for subsequent calls ofgetTour(Graph)
. Once each specified first vertex is used, the first vertex in subsequent tour computations is selected randomly from the graph. AlternativelyNearestNeighborHeuristicTSP(Random)
orNearestNeighborHeuristicTSP(long)
can be used to specify aRandom
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 Modifier and Type Field Description private java.util.Iterator<V>
initiaVertex
Nulled, if it has no nextprivate java.util.Random
rng
-
Constructor Summary
Constructors Modifier Constructor Description NearestNeighborHeuristicTSP()
Constructor.NearestNeighborHeuristicTSP(long seed)
ConstructorNearestNeighborHeuristicTSP(java.lang.Iterable<V> initialVertices)
Constructorprivate
NearestNeighborHeuristicTSP(java.lang.Iterable<V> initialVertices, java.util.Random rng)
ConstructorNearestNeighborHeuristicTSP(java.util.Random rng)
ConstructorNearestNeighborHeuristicTSP(V first)
Constructor
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private int
getFirstVertexIndex(java.util.List<V> path)
Returns the start vertex of the tour about to compute.private static <V,E>
intgetNearestNeighbor(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.GraphPath<V,E>
getTour(Graph<V,E> graph)
Computes a tour using the nearest neighbour heuristic.-
Methods inherited from class org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase
checkGraph, closedVertexListToTour, edgeSetToTour, getSingletonTour, requireNotEmpty, vertexListToTour
-
-
-
-
Field Detail
-
rng
private java.util.Random rng
-
initiaVertex
private java.util.Iterator<V> initiaVertex
Nulled, if it has no next
-
-
Constructor Detail
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP()
Constructor. By default a random vertex is chosen to start.
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP(V first)
Constructor- Parameters:
first
- First vertex to visit- Throws:
java.lang.NullPointerException
- if first is null
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP(java.lang.Iterable<V> initialVertices)
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:
java.lang.NullPointerException
- if first is null
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP(long seed)
Constructor- Parameters:
seed
- seed for the random number generator
-
NearestNeighborHeuristicTSP
public NearestNeighborHeuristicTSP(java.util.Random rng)
Constructor- Parameters:
rng
- Random number generator- Throws:
java.lang.NullPointerException
- if rng is null
-
NearestNeighborHeuristicTSP
private NearestNeighborHeuristicTSP(java.lang.Iterable<V> initialVertices, java.util.Random rng)
Constructor- Parameters:
initialVertices
- The Iterable of vertices visited first in subsequent tour computations, or null to choose at randomrng
- Random number generator
-
-
Method Detail
-
getTour
public GraphPath<V,E> getTour(Graph<V,E> graph)
Computes a tour using the nearest neighbour heuristic.- Parameters:
graph
- the input graph- Returns:
- a tour
- Throws:
java.lang.IllegalArgumentException
- if the graph is not undirectedjava.lang.IllegalArgumentException
- if the graph is not completejava.lang.IllegalArgumentException
- if the graph contains no verticesjava.lang.IllegalArgumentException
- if the specified initial vertex is not in the graph
-
getFirstVertexIndex
private int getFirstVertexIndex(java.util.List<V> path)
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:
java.lang.IllegalArgumentException
- if the specified initial vertex is not in the graph
-
getNearestNeighbor
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.- 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.
-
-