smart-tsp-oracle

Core Components:

• Multi-Start Greedy + 2-opt — Generates high-quality initial solution
• Branch and Bound — Exact search with mathematical optimality guarantee
• MST Lower Bounds — Minimum Spanning Tree for efficient pruning
• Adaptive Thresholding — Dynamic search space reduction

Mathematical Foundation:

The algorithm uses Minimum Spanning Tree (MST) calculations to compute exact lower bounds, ensuring mathematical proof of optimality for the found solutions.

Position-Candidate-Hypothesis (PCH) Paradigm: doi.org/10.5281/zenodo.17614888 — A New Research Direction for NP-Complete Problems

For those interested in the theoretical foundations:

• Smart TSP Solver — Python library featuring advanced heuristics for solving large TSP instances
• Exact TSP Solver — Dual-mode TSP solver in Go: exact Branch & Bound with proven optimality, plus heuristic threshold search with reference gap.
• Smart TSP Benchmark — Professional algorithm testing infrastructure
• Spatial Optimization: Computational geometry approaches for large-scale problems
• Heuristic Analysis: Comparative study of modern TSP approaches

# Install requirements
pip install numpy numba

# Run with 20 points
python main.py -n 20 --seed 42

# Run with custom parameters
python main.py -n 15 --seed 12345

Command Line Options:

python main.py -n 20 --seed 123321411

==================================================
TSP SOLVER (ORACLE v2) - 20 POINTS
SEED: 123321411
==================================================

Coordinates of points:
   Dot 0: (716.02, 797.47)
   Dot 1: (336.04, 587.85)
   Dot 2: (620.65, 170.96)
   Dot 3: (0.77, 335.69)
   Dot 4: (275.75, 747.51)
   Dot 5: (823.69, 50.79)
   Dot 6: (533.09, 748.58)
   Dot 7: (135.94, 668.09)
   Dot 8: (890.62, 294.76)
   Dot 9: (583.21, 863.07)
   Dot 10: (463.36, 816.27)
   Dot 11: (592.15, 238.06)
   Dot 12: (680.65, 113.63)
   Dot 13: (404.13, 996.27)
   Dot 14: (14.42, 824.82)
   Dot 15: (87.71, 239.60)
   Dot 16: (443.56, 190.80)
   Dot 17: (724.89, 425.34)
   Dot 18: (929.70, 824.26)
   Dot 19: (726.95, 159.40)
1. Launching the multi-start greedy algorithm...
   Multi-start greedy + 2-opt: length = 4676.81
   We start the search from 4209.13 (90.0%)
Checked: 287 paths | Speed: 574/sec | Time: 00:00:00✓ found: 4176.83 (00:00:00)
   Threshold: 3884.45 (83.1%)... ✗ cut off (00:00:00)
   The optimum has been found: 4176.83

RESULTS:
==================================================
Number of points: 20
Seed: 123321411
Total possible paths: so many
Checked paths: 298
Execution time: 1.01 seconds
Speed: 295 paths/sec
Greedy + 2-opt: 4676.805998
Optimal length: 4176.825110
Improvement: 499.980888 (10.691%)

Greedy way: [3, 15, 16, 11, 2, 12, 19, 5, 8, 17, 1, 4, 7, 14, 13, 10, 6, 9, 0, 18]
The optimal path: [0, 17, 8, 5, 19, 12, 2, 11, 16, 15, 3, 14, 7, 1, 4, 13, 10, 6, 9, 18]

The results are saved in tsp_result_n20_seed123321411.txt

• Optimal for: 3-25 points (exact solutions)
• Time complexity: O(n! * 2ⁿ) in worst case
• Space complexity: O(n²) for distance matrix
• Features: Progress tracking, result export, reproducible runs

Requirements:

• Python 3.8+
• numpy
• numba

Implementation Highlights:

• Numba-accelerated distance matrix computation
• Union-Find data structure for MST calculations
• Adaptive thresholding for efficient pruning
• Comprehensive result logging and export

By using this software, you agree to the full disclaimer terms.

Software provided "AS IS" without warranty. You assume all risks.

Full legal disclaimer: See DISCLAIMER.md

License: BSD 3-Clause License

Note: Performance results shown are for clustered/random distributions. Results may vary based on spatial characteristics. Always evaluate algorithms on your specific problem domains.