Claim
In this post, I am using the same notation as in the video below and the wiki page (https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm)
Our problem is given a matrix costs in which costs[i][j] is the traveling cost going from node i to node j, we are asked to return the minimum cost for traveling from node 0 and visit every other node exactly once and return back to node 0.
We use g(x, S) to denote the minimum cost for a travel which starts from node x, visits every node in S exactly once and returns to node 0. The detailed DP process can be illustrated in the following example.
Let’s say we have a 5×5 costs matrix, which means we have 5 node.
In the first round, we calculate:
g(1, ∅) = costs(1,0) # minimum cost of travel from node 1 and ends at node 0 without visiting any other node g(2, ∅) = costs(2,0) g(3, ∅) = costs(3,0) g(4, ∅) = costs(4,0)
In the second round, we calculate:
# minimum cost of travel from node 1 and ends at node 0 with visiting only one other node
g(1, {2}) = costs(1,2) + g(2, ∅)
g(1, {3}) = costs(1,3) + g(3, ∅)
g(1, {4}) = costs(1,4) + g(4, ∅)
# minimum cost of travel from node 2 and ends at node 0 with visiting only one other node
...
In the third round, we calculate:
# minimum cost of travel from node 1 and ends at node 0 with visiting two other nodes
g(1, {2,3}) = min(costs(1,2)+g(2,{3}), costs(1,3)+g(3,{2})) # either you choose to go from 1 to 2 first, or go from 1 to 3 first
g(1, {3,4}) = min(costs(1,3)+g(3,{4}), costs(1,4)+g(4,{3}))
g(1, {2,4}) = min(costs(1,2)+g(2,{4}), costs(1,4)+g(4,{2}))
# minimum cost of travel from node 2 and ends at node 0 with visiting two other nodes
...
In the fourth round, we calculate:
# minimum cost of travel from node 1 and ends at node 0 with visiting three other nodes
# either you choose to go from 1 to 2 first, or go from 1 to 3 first or go from 1 to 4 first
g(1, {2,3,4}) = min(costs(1,2)+g(2,{3,4}), costs(1,3)+g(3,{2,4}), costs(1,4)+g(4,{2,3}))
# minimum cost of travel from node 2 and ends at node 0 with visiting three other nodes
...
After the four rounds above, we can calculate our ultimate goal, g(0, {1,2,3,4}):
g(0, {1, 2,3,4}) = min(costs(0,1)+g(1,{2,3,4}),
costs(0,2)+g(2,{1,3,4}),
costs(0,3)+g(3,{1,2,4}),
costs(0,4)+g(4,{1,2,3}))
Now here it is an implementation in Python:
from itertools import *
class Solution:
def shortest(self, costs):
'''
costs: List[List[n]]
'''
def to_str(l):
return '-'.join([str(ll) for ll in l])
# nodes excluding the starting node
nodes = set([i for i,v in enumerate(costs) if i])
g = {}
for x in xrange(1, len(costs)):
g[x] = {}
g[x][''] = costs[x][0]
for k in xrange(1, len(costs)-1):
for x in xrange(1, len(costs)):
for c in combinations(node-set([x]), k):
g[x][to_str(c)] = min([costs[x][e] + g[e][to_str(c-set([e]))] for e in c])
return min([costs[0][e] +g[e][to_str(nodes-set([e]))] for e in nodes])
In the code `g` is a dictionary. Its value its another dictionary. For example, if we want to refer to g(1, {2,3,4}), we can access it by `g[1][‘2-3-4’]`.
Let’s analyze the time complexity and the space complexity for this DP algorithm.
- Space complexity: before calculating g(0, {1,2,3,4}), we need to store:
g(1, {∅}), g(1, {2}), g(1,{3}), g(1,{4}), g(1,{2,3}), g(1, {2,4}), g(1, {3,4}), g(1, {2,3,4})
g(2, {∅}), g(2, {1}), g(2,{3}), g(2,{4}), g(2,{1,2}), g(2, {1,3}), g(2, {3,4}), g(2, {1,3,4})
...
Therefore, for each row here, we need to store g(.) values of number $latex \sum\limits_{k=1}^{n-2} C_{n-1}^k = O(2^n) $ (n is total number of nodes: 0, 1, .., n-1). We have n-1 rows here. So in total space complexity is $latex O(n2^n)$.
- Time complexity: we know we have $latex O(n2^n)$ g(.) values to store. We get each of these values by taking min function over O(n) possible candidates(See Python code line 20). Therefore, the total time complexity is $latex O(n^2 2^n)$.