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 details)
Built Distribution
File details
Details for the file toposolve-0.1.1.tar.gz
.
File metadata
- Download URL: toposolve-0.1.1.tar.gz
- Upload date:
- Size: 5.2 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/5.1.1 CPython/3.11.10
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | b23287b7bdbe5704b30f4fd447a05e41a418e3f500837634c212baa8b226e9ed |
|
MD5 | 2b074431f173201c422a97c11323295c |
|
BLAKE2b-256 | b4d8c57f67241f71ff14b20b2e5a7316e6a6eb16fb02010a5c6674f5dc5cb402 |
File details
Details for the file toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl
.
File metadata
- Download URL: toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl
- Upload date:
- Size: 61.5 kB
- Tags: CPython 3.11, macOS 13.0+ ARM64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/5.1.1 CPython/3.11.10
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b4cefea1ead3bea316422790af49f63fbc91568b8a1a26305e1e9620600ff86 |
|
MD5 | cf7728a25845e49363bb62f957b1680f |
|
BLAKE2b-256 | b115a8861bfc8b5d1d65b49d0078b365e45f857ee44a63b05097839dcc5384aa |