Skip to main content

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


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)

Uploaded Source

Built Distribution

toposolve-0.1.1-cp311-cp311-macosx_13_0_arm64.whl (61.5 kB view hashes)

Uploaded CPython 3.11 macOS 13.0+ ARM64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page