Class RandomTourTSP<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    HamiltonianCycleAlgorithm<V,​E>

    public class RandomTourTSP<V,​E>
    extends HamiltonianCycleAlgorithmBase<V,​E>
    Generate a random tour.

    This class generates a random Hamiltonian Cycle. This is a simple unoptimised solution to the Travelling Salesman Problem, or more usefully is a starting point for optimising a tour using TwoOptHeuristicTSP.

    Author:
    Peter Harman, Dimitrios Michail
    • Constructor Detail

      • RandomTourTSP

        public RandomTourTSP()
        Construct with default random number generator
      • RandomTourTSP

        public RandomTourTSP​(java.util.Random rng)
        Construct with specified random number generator
        Parameters:
        rng - The random number generator
    • Method Detail

      • getTour

        public GraphPath<V,​E> getTour​(Graph<V,​E> graph)
        Computes a tour using the greedy 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