travelling salesman problem

Angol

Főnév

travelling salesman problem (tsz. travelling salesman problems)

(informatika) utazó ügynök problémája

Az utazó ügynök problémája (angolul: Travelling Salesman Problem, röviden TSP) a kombinatorikus optimalizálás egyik legismertebb problémája.

Feladat:

Adott egy sor város és az ezek közötti távolság (vagy költség). Egy ügynöknek (vagy futárnak) el kell látogatnia minden városba pontosan egyszer, majd vissza kell térnie a kiindulási városba. A cél, hogy a megtett összköltség (pl. távolság, idő, pénz) minimális legyen.

2. Példával

Képzeld el, hogy egy ügynök Budapestről indul, és szeretne Debrecenbe, Szegedre, Pécsre, Győrbe ellátogatni, majd visszatérni Budapestre úgy, hogy az összút a lehető legrövidebb legyen.

3. Formális definíció

Legyen:

${\textstyle G=(V,E)}$ : irányított vagy irányítatlan gráf városokkal (csúcsok) és utak (élek) közöttük
${\textstyle w:E\rightarrow \mathbb {R} ^{+}}$ : súlyfüggvény (pl. távolság vagy költség)
A cél: megtalálni egy Hamilton-kört (azaz minden csúcs egyszer szerepel), amelyben az élösszeg minimális

4. Miért fontos ez a probléma?

📦 Logisztika – szállítási és útvonaltervezés (futárok, drónok, teherautók)
🧠 Mesterséges intelligencia – keresési stratégiák
🧬 Bioinformatika – gének közötti minimális szerkezeti átrendezés
🤖 Robotika – útoptimalizálás autonóm egységeknek
🧮 Kombinatorikus tesztelés – minimális tesztkészlet generálás

5. A probléma nehézsége

A TSP NP-nehéz, ami azt jelenti, hogy:
- Nincs ismert polinomiális idejű algoritmus, amely minden esetben optimális megoldást ad
- A lehetőségek száma n! (n faktoriális), azaz exponenciálisan nő a városok számával

Példa:

10 város → 10! = 3 628 800 lehetséges útvonal
20 város → 20! = kb. 2,4 × 10¹⁸ útvonal 🤯

6. Megoldási módszerek

✅ Brute-force (teljes keresés)

Minden lehetséges útvonal kipróbálása
Garantáltan optimális
Csak nagyon kis méretű problémákra

✅ Dinamikus programozás – Held-Karp algoritmus

TSP speciális DP-verziója
Időkomplexitás: ${\textstyle O(n^{2}\cdot 2^{n})}$
Jó közepes méretre (n < 25)

✅ Heurisztikák (gyors, de nem garantáltan optimális)

Módszer	Leírás
Legközelebbi szomszéd	Minden lépésben a legközelebbi még meg nem látogatott városba megy
Inverziók csökkentése	Két él felcserélése, ha javít az úton
Gráf szétvágása	Élek cseréje ciklus csökkentéséhez

✅ Metaheurisztikák (távoli keresés, optimalizálás)

Genetikus algoritmusok
Szimulált hűtés (Simulated Annealing)
Tabu keresés
Hangyaszabású algoritmus (Ant Colony Optimization)

7. Held-Karp algoritmus – dinamikus programozás

Későbbi városokhoz vezető utak rekurzívan építhetők fel:

Legyen:

${\textstyle C(S,j)}$ : minimális út, ami az ${\textstyle S}$ városokból indulva az ${\textstyle j}$ -edik városnál végződik

Rekurzió:

$C(S,j)=\min _{i\in S,i\neq j}[C(S-\{j\},i)+w(i,j)]$

Induló állapot:

$C(\{0\},0)=0\quad ({\text{0 a kezdő város}})$

8. Példa: 4 város

Távolságmátrix:
      A  B  C  D
    -----------
A |  0  1  3  6
B |  1  0  2  5
C |  3  2  0  4
D |  6  5  4  0

Brute-force kipróbálás:

A–B–C–D–A = 1+2+4+6 = 13
A–C–B–D–A = 3+2+5+6 = 16
A–B–D–C–A = 1+5+4+3 = 13 → Optimális költség: 13

9. Python példa – egyszerű greedy algoritmus

def tsp_greedy(matrix):
    n = len(matrix)
    visited = [False]*n
    path = [0]
    visited[0] = True
    total = 0
    current = 0

    for _ in range(n - 1):
        next_city = min([(matrix[current][j], j) for j in range(n) if not visited[j]])
        total += next_city[0]
        current = next_city[1]
        visited[current] = True
        path.append(current)

    total += matrix[current][0]  # visszatérés
    path.append(0)
    return total, path

matrix = [
    [0, 1, 3, 6],
    [1, 0, 2, 5],
    [3, 2, 0, 4],
    [6, 5, 4, 0]
]

cost, route = tsp_greedy(matrix)
print("Útvonal:", route)
print("Költség:", cost)

10. TSP típusváltozatok

Típus	Leírás
Aszimmetrikus TSP (ATSP)	Egyes utak visszafelé más költségűek
Több ügynök (mTSP)	Több utazó, együttes optimalizálás
Kapacitáskorlátos TSP (CVRP)	Szállítmányozásnál: súly, kapacitás
TSP időablakokkal (TSP-TW)	Időben korlátozott látogatások
Stochasztikus TSP	Költségek bizonytalanságot tartalmaznak

11. Miért nehéz, de izgalmas a TSP?

Mert egyszerűen fogalmazható meg, de nehéz pontosan megoldani
Kiváló tanulópélda optimalizálásra
Motiválja a heurisztikus, evolúciós és AI módszerek fejlesztését
Még kis városszám esetén is komplex struktúrák jönnek létre

12. Összefoglalás

A TSP az egyik legfontosabb kombinatorikus optimalizálási probléma, amely:

Városokat, pontokat köt össze a legrövidebb (vagy legolcsóbb) úton
NP-nehéz – pontos megoldás csak kis méretekre reális
Sokféle módszerrel jó közelítéseket lehet találni
Számos valós alkalmazási területen kulcsszerepet játszik

További információk

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