#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/bitmask-dp/tsp-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/bitmask-dp/tsp-implementation

Repovive

TSP - Implementation - Bitmask DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

TSP - Implementation

O(n² × 2^n)

Here's the full solution:

function tsp(cost, n)
    INF := large number
    dp := 2D (two-dimensional) array [2^n][n], filled with INF
    dp[1][0] := 0
    // start at city 0
    for mask := 1 to 2^n - 1
        for last := 0 to n - 1
            if dp[mask][last] = INF then
                continue
            if (mask >> last) & 1 = 0 then
                continue
            for next := 0 to n - 1
                if (mask >> next) & 1 = 1 then
                    continue
                newMask := mask | (1 << next)
                dp[newMask][next] := min(dp[newMask][next], dp[mask][last] + cost[last][next])
    ans := INF
    for last := 0 to n - 1
        ans := min(ans, dp[2^n - 1][last] + cost[last][0])
    return ans if ans < INF else "IMPOSSIBLE"

Time: $O(n^2 \cdot 2^n)$ . Space: $O(n \cdot 2^n)$ . For $n = 20$ , this runs in a few seconds.

Time: $O(n^2 \cdot 2^n)$ . Space: $O(n \cdot 2^n)$ .