Held-Karp-algoritmus

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)