Traveling Salesman DP (Held–Karp Bitmask) — TSP bitmask DP

TSP — dp[mask][i]; Held–Karp.

உண்மை உலகில் இது ஏன் முக்கியம்?

ட்ரோன்; PCB.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

முழு mask.

Pythonில் முயற்சி செய்வோம்

def tsp_small(dist: list[list[int]]) -> int:
    n = len(dist)
    FULL = (1 << n) - 1
    dp = [[10**18] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask & (1 << u)) or dp[mask][u] >= 10**17:
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                nm = mask | (1 << v)
                dp[nm][v] = min(dp[nm][v], dp[mask][u] + dist[u][v])
    return min(dp[FULL][j] + dist[j][0] for j in range(1, n))


print(tsp_small([[0, 2, 9], [1, 0, 6], [15, 7, 0]]))

அடிக்கடி நேரும் தவறுகள்

• float.
• தொடக்க சமச்சீர்.

முக்கியச் சுருக்கக் குறிப்புகள்

• முழு mask சோதனை.