Class HamiltonianAll

java.lang.Object
topics.backtracking.tsp.HamiltonianAll
Direct Known Subclasses:
CyclesAll, Salesman
public class HamiltonianAll extends Object

Exhaustive Search for Hamiltonian Cycles

This class implements a brute-force approach to find all simple cycles that visit every node exactly once (Hamiltonian Cycles).

*

Complexity Analysis

  • Time Complexity: O((N-1)!), where N is the number of nodes. This is due to the permutations of nodes to visit.
  • Space Complexity: O(N) for the recursion stack and the path array.
* @author vicegd

  • Field Details

    • log

      protected static final org.slf4j.Logger log

    • n

      protected final int n

    • weights

      protected final int[][] weights

    • source

      protected final int source

    • mark

      protected final boolean[] mark

    • path

      protected final int[] path

    • length

      protected int length

    • cost

      protected int cost

    • nsol

      protected int nsol

  • Constructor Details

    • HamiltonianAll

      public HamiltonianAll(int n, int source, int[][] weights)

  • Method Details

    • backtracking

      public void backtracking()

    • backtrack

      protected void backtrack(int current)
      Core backtracking logic following the Choose-Explore-Unchoose paradigm.
      Parameters:
      current - The current node being visited.

    • getNumberSolutions

      public int getNumberSolutions()