Utazó ügynök problémája

1. Sablon:Label

Utazó ügynök problémája (Travelling Salesman Problem, TSP)

Definíció

Az utazó ügynök problémája (TSP) egy klasszikus kombinatorikai optimalizálási probléma. Egy adott $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.

Megoldási stratégiák

1. Brute Force (Teljes keresés):

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

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

  * Csökkenti a redundáns számításokat.
  * Időbonyolultság: $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 $n$-re.

Held-Karp algoritmus (Dinamikus programozás)

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: $dp[mask][i]=\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.}$

Rekurzív reláció

$dp[mask][i]=\underset{j\in \text{mask}}{\min }\{dp[mask\setminus \{i\}][j]+\text{cost}(j,i)\}$

Python Implementáció

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[i][j] 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[(1 << i, i)] = (graph[0][i], 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[(prev_bits, k)][0] + graph[k][j], k))
                dp[(bits, j)] = 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[(bits, k)][0] + graph[k][0], 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, parent)]
        bits = new_bits

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

# Példa gráf (távolságok mátrix formában)
graph = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]

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

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

Példa Kimenet

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: [0, 1, 3, 2, 0]

Heurisztikus megközelítés: Nearest Neighbor algoritmus

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 = [False] * n
    path = [0]
    visited[0] = 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[j] and graph[current][j] < min_cost:
                next_city = j
                min_cost = graph[current][j]
        path.append(next_city)
        visited[next_city] = True
        total_cost += min_cost
        current = next_city

    # Visszatérés a kiinduló városba
    total_cost += graph[current][0]
    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)

Összegzés

• A Held-Karp algoritmus optimális megoldást nyújt $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).

Sablon:-ford-

• Sablon:En: Sablon:T
• Sablon:Ru: Sablon:T