Class NearestNeighborHeuristicTSP<V,E>

java.lang.Object
org.jgrapht.alg.tour.HamiltonianCycleAlgorithmBase<V,E>
org.jgrapht.alg.tour.NearestNeighborHeuristicTSP<V,E>
Type Parameters:
V - the graph vertex type
E - 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 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 Details

    • rng

      private Random rng
    • initiaVertex

      private Iterator<V> initiaVertex
      Nulled, if it has no next
  • Constructor Details

    • 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:
      NullPointerException - if first is null
    • NearestNeighborHeuristicTSP

      public NearestNeighborHeuristicTSP(Iterable<V> initialVertices)
      Constructor
      Parameters:
      initialVertices - The Iterable of vertices visited first in subsequent tour computations (per call of getTour(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

      public NearestNeighborHeuristicTSP(Random rng)
      Constructor
      Parameters:
      rng - Random number generator
      Throws:
      NullPointerException - if rng is null
    • NearestNeighborHeuristicTSP

      private NearestNeighborHeuristicTSP(Iterable<V> initialVertices, Random rng)
      Constructor
      Parameters:
      initialVertices - The Iterable of vertices visited first in subsequent tour computations, or null to choose at random
      rng - Random number generator
  • Method Details

    • 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:
      IllegalArgumentException - if the graph is not undirected
      IllegalArgumentException - if the graph is not complete
      IllegalArgumentException - if the graph contains no vertices
      IllegalArgumentException - if the specified initial vertex is not in the graph
    • getFirstVertexIndex

      private int getFirstVertexIndex(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:
      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 at from that is closest to the element at index from-1.
      Parameters:
      current - the vertex for which the nearest neighbor is searched
      vertices - the vertices of the graph. The unvisited neighbors start at index start
      start - the index of the first vertex to consider
      g - the graph containing the vertices
      Returns:
      the index of the unvisited vertex closest to the vertex at firstNeighbor-1.