Module org.jgrapht.core
Package org.jgrapht.alg.interfaces

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 Details

    • improveTour

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