Class SalesmanPruning

java.lang.Object

topics.backtracking.tsp.HamiltonianAll

topics.backtracking.tsp.Salesman

topics.backtracking.tsp.SalesmanPruning

public class SalesmanPruning
extends Salesman

TSP Optimization with Pruning (Bounding)

This class implements Branch invalid input: '&' Bound by pruning branches that exceed the current bestCost.

*

Bounding Principle

If currentCost + edgeCost >= bestCost, we stop exploring this path. This is the crucial heuristic that makes this algorithm usable for slightly larger N.

Field Summary

Fields inherited from class Salesman

bestCost, bestPath

Fields inherited from class HamiltonianAll

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

Constructor Summary

Constructors

Constructor	Description
SalesmanPruning(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.

Methods inherited from class Salesman

getBestCost, getBestPath

Methods inherited from class HamiltonianAll

backtracking, getNumberSolutions

Methods inherited from class Object

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

Constructor Details

SalesmanPruning

public SalesmanPruning(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 Salesman

Parameters:

current - The current node being visited.