Package org.jgrapht.alg.tour

Class 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 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:
        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