A fast C++ implementation of the Held-Karp algorithm for solving TSP
Project description
toposolve
A fast C++ implementation of the Held-Karp algorithm for solving the Traveling Salesman Problem (TSP) for ring-reduce tours, with Python bindings.
We solve a specific variant of TSP where the dist(i, j)
is calculated as min(max(dist(i, k), dist(k, j)) for k in range(n))
.
Installation
pip install toposolve
Usage
from toposolve import TSPSolver
# Create distance matrix
distances = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
# Create solver instance
solver = TSPSolver()
# Solve TSP
min_distance, path = solver.solve_tsp(distances)
print(f"Minimum distance: {min_distance}")
print(f"Optimal path: {path}")
Requirements
- Python 3.6+
- C++ compiler supporting C++17
- CMake 3.18+
Building from source
git clone https://github.com/Jackmin801/toposolve
cd toposolve
pip install .
Running tests
pip install pytest
pytest tests/
License
MIT License
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
toposolve-0.1.1.tar.gz
(5.2 kB
view hashes)
Built Distribution
Close
Hashes for toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b4cefea1ead3bea316422790af49f63fbc91568b8a1a26305e1e9620600ff86 |
|
MD5 | cf7728a25845e49363bb62f957b1680f |
|
BLAKE2b-256 | b115a8861bfc8b5d1d65b49d0078b365e45f857ee44a63b05097839dcc5384aa |