Held-Karp-algoritmus

Magyar

Kiejtés

• IPA: [ ˈhɛltkɒrpɒlɡoritmuʃ]

Főnév

Held-Karp-algoritmus

1. (matematika)

Held-Karp algoritmus (Dinamikus programozás)

A Held-Karp algoritmus a dinamikus programozás segítségével hatékonyan oldja meg az utazó ügynök problémáját (TSP). 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]=\min _{j\in {\text{mask}}}\{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]

Fordítások

Tartalom

angol: Held–Karp algorithm (en)

További információk

• Held-Karp-algoritmus - Értelmező szótár (MEK)
• Held-Karp-algoritmus - Etimológiai szótár (UMIL)
• Held-Karp-algoritmus - Szótár.net (hu-hu)
• Held-Karp-algoritmus - DeepL (hu-de)
• Held-Karp-algoritmus - Яндекс (hu-ru)
• Held-Karp-algoritmus - Google (hu-en)
• Held-Karp-algoritmus - Helyesírási szótár (MTA)
• Held-Karp-algoritmus - Wikidata
• Held-Karp-algoritmus - Wikipédia (magyar)