Class Salesman

java.lang.Object

topics.backtracking.tsp.HamiltonianAll

topics.backtracking.tsp.Salesman

Direct Known Subclasses:

SalesmanPruning

public class Salesman
extends HamiltonianAll

Traveling Salesman

Extends HamiltonianAll to find the global minimum cost cycle. Unlike the base class, it stores bestCost and updates it whenever a shorter Hamiltonian cycle is discovered.

Field Summary

Fields

Modifier and Type	Field	Description
protected int	bestCost
protected final int[]	bestPath

Fields inherited from class HamiltonianAll

cost, length, log, mark, n, nsol, path, source, weights

Constructor Summary

Constructors

Constructor	Description
Salesman(int n, int source, int[][] weights)

Method Summary

Modifier and Type	Method	Description
protected void	backtrack(int current)	Core backtracking logic following the Choose-Explore-Unchoose paradigm.
int	getBestCost()
String	getBestPath()

Methods inherited from class HamiltonianAll

backtracking, getNumberSolutions

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

bestPath

protected final int[] bestPath

bestCost

protected int bestCost

Constructor Details

Salesman

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

Method Details

backtrack

protected void backtrack(int current)

Description copied from class: HamiltonianAll

Core backtracking logic following the Choose-Explore-Unchoose paradigm.

Overrides:

backtrack in class HamiltonianAll

Parameters:

current - The current node being visited.

getBestCost

public int getBestCost()

getBestPath

public String getBestPath()