Concorde TSP Solver

Concorde TSP Solver (tsz. Concorde TSP Solvers)

1. (informatika) A Concorde TSP Solver egy világszinten vezető programcsomag a Travelling Salesman Problem (TSP) megoldására. Az algoritmust és az eszközt William Cook és munkatársai fejlesztették ki, és számos rekordméretű TSP példát oldott meg optimálisan.

A Travelling Salesman Problem célja:

Megtalálni azt a legrövidebb kört, amely minden csúcsot pontosan egyszer érint, majd visszatér a kezdőpontra.

Ez egy klasszikus NP-hard probléma – nem ismerünk polinomiális idejű algoritmust az általános esetre.

Concorde TSP Solver egy:

• C nyelven írt, hatékony, optimalizált,
• kombinatorikus optimalizáló csomag,
• amely teljes TSP-instanciákra ad bizonyítottan optimális megoldást.

👉 Használ cutting plane, branch-and-bound, linear programming, és heurisztikák kombinációját.

# Letöltés és fordítás
git clone http://www.math.uwaterloo.ca/tsp/concorde.html
cd concorde
./configure
make

⚠️ A telepítés CPLEX és QSopt LP solver nélkül is működik, de lassabb lehet.

NAME: simple
TYPE: TSP
DIMENSION: 4
EDGE_WEIGHT_TYPE: EUC_2D
NODE_COORD_SECTION
1 0 0
2 0 1
3 1 0
4 1 1
EOF

./concorde -o output.tour input.tsp

Ez:

• Kiolvassa a input.tsp fájlt,
• Kiszámítja a legjobb lehetséges útvonalat,
• Az eredményt kiírja output.tour fájlba.

Ha nem akarsz nyers C-vel dolgozni, létezik Python wrapper is, pl.:

pip install python-tsp

from python_tsp.exact import solve_tsp_dynamic_programming
import numpy as np

distance_matrix = np.array([
    ,
    ,
    ,
    
])

perm, dist = solve_tsp_dynamic_programming(distance_matrix)
print("Optimális sorrend:", perm)
print("Teljes távolság:", dist)

☝️ A Python-könyvtár nem Concorde, de hasonló szemléletű megoldásokat nyújt kisebb méretre.

• Concorde TSP Solver - Szótár.net (en-hu)
• Concorde TSP Solver - Sztaki (en-hu)
• Concorde TSP Solver - Merriam–Webster
• Concorde TSP Solver - Cambridge
• Concorde TSP Solver - WordNet
• Concorde TSP Solver - Яндекс (en-ru)
• Concorde TSP Solver - Google (en-hu)
• Concorde TSP Solver - Wikidata
• Concorde TSP Solver - Wikipédia (angol)