I want to solve the TSP problem using a dynamic programming algorithm in Python.The problem is:
And the pseudo-code is:
Let A = 2-D array, indexed by subsets of {1, 2, ,3, ..., n} that contains 1 and destinations j belongs to {1, 2, 3,...n}
1. Base case:
2. if S = {0}, then A[S, 1] = 0;
3. else, A[S, 1] = Infinity.
4.for m = 2, 3, ..., n: // m = subproblem size
5. for each subset of {1, 2,...,n} of size m that contains 1:
6. for each j belongs to S and j != 1:
7. A[S, j] = the least value of A[S-{j},k]+the distance of k and j for every k belongs to S that doesn't equal to j
8.Return the least value of A[{1,2..n},j]+the distance between j and 1 for every j = 2, 3,...n.
My confusions are:
How to index a list using subset, that is how to implement line 5 in the pseudo-code efficiently.
You can encode sets as integers: i'th bit of the integer will represent the state of i'th city (i.e. do we take it in the subset or not).
For example, 3510 = 1000112 will represent cities {1, 2, 6}. Here I count from the rightmost bit, which represents city 1.
In order to index a list using such representation of a subset, you should create 2D array of length 2n:
# Assuming n is given.
A = [[0 for i in xrange(n)] for j in xrange(2 ** n)]
This comes from the fact that with n-bit integer you can represent every subset of {1, 2, ..., n} (remember, each bit corresponds to exactly one city).
This representation gives you a number of nice possibilities:
# Check whether some city (1-indexed) is inside subset.
if (1 << (i - 1)) & x:
print 'city %d is inside subset!' % i
# In particular, checking for city #1 is super-easy:
if x & 1:
print 'city 1 is inside subset!'
# Iterate over subsets with increasing cardinality:
subsets = range(1, 2 ** n)
for subset in sorted(subsets, key=lambda x: bin(x).count('1')):
print subset,
# For n=4 prints "1 2 4 8 3 5 6 9 10 12 7 11 13 14 15"
# Obtain a subset y, which is the same as x,
# except city #j (1-indexed) is removed:
y = x ^ (1 << (j - 1)) # Note that city #j must be inside x.
This is how I would implement your pseudocode (warning: no testing was done):
# INFINITY and n are defined somewhere above.
A = [[INFINITY for i in xrange(n)] for j in xrange(2 ** n)]
# Base case (I guess it should read "if S = {1}, then A[S, 1] = 0",
because otherwise S = {0} is not a valid index to A, according to line #1)
A[1][1] = 0
# Iterate over all subsets:
subsets = range(1, 2 ** n)
for subset in sorted(subsets, key=lambda x: bin(x).count('1')):
if not subset & 1:
# City #1 is not presented.
continue
for j in xrange(2, n + 1):
if not (1 << (j - 1)) & subset:
# City #j is not presented.
continue
for k in xrange(1, n + 1):
if k == j or not (1 << (k - 1)) & subset:
continue
A[subset][j] = min(A[subset][j], A[subset ^ (1 << (j - 1))][k] + get_dist(j, k))
Besides having all needed functionality to implement your pseudocode, this approach is going to be faster than with tuples\dicts.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With