Class SalesmanTimes

java.lang.Object

topics.backtracking.tsp.SalesmanTimes

public class SalesmanTimes
extends Object

Empirical Complexity Analysis: TSP Optimizations

This benchmark demonstrates the massive performance difference between pure Exhaustive Search (Un-pruned) and Branch invalid input: '&' Bound (Pruned) when solving the Traveling Salesman Problem.

*

Pedagogical Note on Complexity

Both algorithms mathematically share a worst-case time complexity of O(N!). However, the Pruning heuristic allows the algorithm to skip millions of branches in practice. You will see the Un-pruned version start to freeze around N=12, while the Pruned version handles it effortlessly.

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
SalesmanTimes()

Method Summary

Modifier and Type	Method	Description
static void	main(String[] args)

Methods inherited from class Object

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

Constructor Details

SalesmanTimes

public SalesmanTimes()

Method Details

main

public static void main(String[] args)