Interface HamiltonianCycleImprovementAlgorithm<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Known Implementing Classes:
    TwoOptHeuristicTSP

    public interface HamiltonianCycleImprovementAlgorithm<V,​E>
    An algorithm improving the result of solving the Hamiltonian cycle problem.

    A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). An improvement algorithm could be one that optimises the cycle for lower cost, or that updates the cycle to match changes in the graph.

    Author:
    Alexandru Valeanu, Peter Harman
    • Method Detail

      • improveTour

        GraphPath<V,​E> improveTour​(GraphPath<V,​E> tour)
        Improves a tour.
        Parameters:
        tour - the current tour
        Returns:
        the tour improved