utazó ügynök problémája

• IPA:

utazó ügynök problémája

1. (matematika, számításelmélet, gráfelmélet)

Az utazó ügynök problémája (TSP) egy klasszikus kombinatorikai optimalizálási probléma. Egy adott ${\displaystyle n}$ számú városból és a közöttük lévő távolságokból álló gráf esetén az a cél, hogy megtaláljuk az ügynök számára a legrövidebb utat, amely minden várost pontosan egyszer érint, majd visszatér a kiindulási városba.

1. Brute Force (Teljes keresés):

  * Az összes lehetséges útvonal generálása (${\displaystyle (n-1)!}$ permutáció).
  * Időbonyolultság: ${\displaystyle O(n!)}$.

1. Dinamikus programozás (Held-Karp algoritmus):

  * Csökkenti a redundáns számításokat.
  * Időbonyolultság: ${\displaystyle O(n^{2}\cdot 2^{n})}$.

1. Heurisztikus algoritmusok:

  * Például Nearest Neighbor, Simulated Annealing, Genetic Algorithm.
  * Nem garantálják az optimális megoldást, de gyorsak.

1. Ág és korlát (Branch and Bound):

  * Fa alapú keresés, amely kizárja a rossz útvonalakat.
  * Általában jobb, mint brute force, de még mindig nem hatékony nagy ${\displaystyle n}$-re.

A Held-Karp algoritmus a dinamikus programozás segítségével hatékonyabban oldja meg a problémát. Egy állapotfüggvényt definiálunk: ${\displaystyle dp={\text{A legkisebb költség, ha az }}i{\text{-edik városban vagyunk, és a mask által meghatározott városokat már meglátogattuk.}}}$

${\displaystyle dp=\min _{j\in {\text{mask}}}\{dp+{\text{cost}}(j,i)\}}$

import itertools

def held_karp(graph):
    """
    Held-Karp dinamikus programozás algoritmus az Utazó Ügynök Problémára.
    Args:
        graph: Két dimenziós lista, ahol graph a i és j város közötti távolság.
    Returns:
        cost: Az optimális út költsége.
        path: Az optimális út városainak sorrendje.
    """
    n = len(graph)

    # Tároló a dinamikus programozás értékeinek
    dp = {}
    
    # Alapállapot: csak egy városból indulunk
    for i in range(1, n):
        dp = (graph, 0)  # (költség, előző város)

    # Dinamikus programozás
    for subset_size in range(2, n):
        for subset in itertools.combinations(range(1, n), subset_size):
            bits = 0
            for bit in subset:
                bits |= 1 << bit
            for j in subset:
                prev_bits = bits & ~(1 << j)
                res = 
                for k in subset:
                    if k == j:
                        continue
                    res.append((dp + graph, k))
                dp = min(res)

    # Befejezés: visszatérés a kiinduló városba
    bits = (2**n - 1) - 1
    res = 
    for k in range(1, n):
        res.append((dp + graph, k))
    opt, parent = min(res)

    # Út rekonstruálása
    path = 
    bits = (2**n - 1) - 1
    for _ in range(n - 1):
        path.append(parent)
        new_bits = bits & ~(1 << parent)
        _, parent = dp
        bits = new_bits

    path.append(0)
    path.reverse()
    
    return opt, path

# Példa gráf (távolságok mátrix formában)
graph = [
    ,
    ,
    ,
    
]

# Megoldás
cost, path = held_karp(graph)

print("Minimális költség:", cost)
print("Optimális út:", path)

Gráf:

• Városok: A, B, C, D
• Távolságok:

A-B: 10, A-C: 15, A-D: 20
B-C: 35, B-D: 25
C-D: 30

Kimenet:

Minimális költség: 80
Optimális út: 

Ha az optimális megoldás túl költséges (például nagyobb gráfok esetén), a Nearest Neighbor egy gyors heurisztikus alternatíva:

def nearest_neighbor(graph):
    n = len(graph)
    visited =  * n
    path = 
    visited = True
    total_cost = 0

    current = 0
    for _ in range(n - 1):
        next_city = None
        min_cost = float('inf')
        for j in range(n):
            if not visited and graph < min_cost:
                next_city = j
                min_cost = graph
        path.append(next_city)
        visited = True
        total_cost += min_cost
        current = next_city

    # Visszatérés a kiinduló városba
    total_cost += graph
    path.append(0)

    return total_cost, path

# Példa használata
cost, path = nearest_neighbor(graph)

print("Heurisztikus költség:", cost)
print("Út:", path)

• A Held-Karp algoritmus optimális megoldást nyújt ${\displaystyle O(n^{2}\cdot 2^{n})}$ időbonyolultsággal, amely kisebb méretű problémák esetén megfelelő.
• A Nearest Neighbor gyors és egyszerű heurisztika, nagyobb gráfok esetén használható, de nem garantálja az optimális megoldást.
• Nagyobb méretű gráfok esetén érdemes metaheurisztikákat alkalmazni (pl. genetikus algoritmus, szimulált lehűlés).

• angol: travelling salesman problem (en)
• orosz: задача коммивояжёра (ru) (zadača kommivojažóra)

• utazó ügynök problémája - Értelmező szótár (MEK)
• utazó ügynök problémája - Etimológiai szótár (UMIL)
• utazó ügynök problémája - Szótár.net (hu-hu)
• utazó ügynök problémája - DeepL (hu-de)
• utazó ügynök problémája - Яндекс (hu-ru)
• utazó ügynök problémája - Google (hu-en)
• utazó ügynök problémája - Helyesírási szótár (MTA)
• utazó ügynök problémája - Wikidata
• utazó ügynök problémája - Wikipédia (magyar)