NearestNeighborHeuristicTSP (JGraphT : a free Java graph library)

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 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.

Author:

Peter Harman

Constructor Summary

Constructors
Constructor	Description
`NearestNeighborHeuristicTSP()`	Constructor.
`NearestNeighborHeuristicTSP(long seed)`	Constructor
`NearestNeighborHeuristicTSP(java.util.Random rng)`	Constructor
`NearestNeighborHeuristicTSP(V first)`	Constructor

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type Method Description

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, edgeSetToTour, getSingletonTour, vertexListToTour
- Methods inherited from class java.lang.Object
  clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- 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, or null to choose at random
    
    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
- 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 undirected
    
    java.lang.IllegalArgumentException - if the graph is not complete
    
    java.lang.IllegalArgumentException - if the graph contains no vertices
    
    java.lang.IllegalArgumentException - if the specified initial vertex is not in the graph