Concorde TSP Solver

Angol

Főnév

Concorde TSP Solver (tsz. Concorde TSP Solvers)

(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.

🧠 1. Mi a TSP?

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.

🧩 2. Mi a Concorde?

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.

🧪 3. Támogatott funkciók

Funkció	Részletek
✅ Pontos TSP megoldás	Optimális megoldás garantált
✅ Heurisztikus módszerek	Pl. Lin-Kernighan, gyors approximáció
✅ Fájlformátum támogatás	TSPLIB, `.tsp`, `.tour`
✅ LP/ILP motor	CPLEX támogatás (opcionálisan)
✅ Programozható könyvtárként	Használható Pythonból, C-ből
✅ Támogatja a városok koordinátáit, távolságmátrixokat is

💻 4. Telepítés (Linux/Mac)

# 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.

🧮 5. Példa TSP fájl (TSPLIB formátum)

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

▶️ 6. Futtatás

./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.

📦 7. Pythonból használat (tsp-solver csomag)

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([
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
])

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.

🌍 8. Használati területek

Terület	Példa
Logisztika	Szállítási útvonal-optimalizálás
Gyártás	Gépútvonalak optimalizálása
PCB-tervezés	Forrasztópontok optimális bejárása
DNS szekvenálás	Rövid szekvenciák sorrendbe állítása
Robotika	Útvonaltervezés mozgó robotoknál

📈 9. Előnyök és hátrányok

✅ Előnyök	❌ Hátrányok
Optimalitás garantált	Nagy példákra számításigényes
Erősen optimalizált	Nehéz módosítani/értelmezni C forrásban
Bizonyításokat is ad	Nehéz beépíteni más nyelvekbe natívan

🧾 10. Összefoglalás

Jellemző	Leírás
Név	Concorde TSP Solver
Kategória	Kombinatorikus optimalizálás
Használat	TSP pontos megoldása
Nyelv	C
Platform	Linux, Mac, részlegesen Windows
Alternatívák	LKH, OR-Tools, python-tsp
Weboldal	http://www.math.uwaterloo.ca/tsp/concorde.html

További információk

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)