dynamic programming pseudocode for Travelling Salesman

Question

hi all. this is a dynamic programming pseudocode for TSP (Travelling Salesman Problem). i understood its optimal substructure but i can't figure out what the code in red brackets do.

i am not asking anyone to write the actual code, i just need explanation on what is happening so i can write my own.... thanks:)

here is a link for the pseudocode, i couln't uploaded over here. http://www.imagechicken.com/viewpic.php?p=1266328410025325200&x=jpg

Answer 1

Here is some less mathematical pseudo-code. I don't know if this will explain what's happening, but it may help you read it. This isn't a functional algorithm (lots of := all over), so I'm going to use Python pseudo-code.

# I have no idea where 'i' comes from. It's not defined anywhere
for k in range(2,n):
    C[set(i,k), k] = d(1,k)
shortest_path = VERY_LARGE_NUMBER
# I have to assume that n is the number of nodes in the graph G
# other things that are not defined:
# d_i,j -- I will assume it's the distance from i to j in G
for subset_size in range(3,n):
    for index_subset in subsets_of_size(subset_size, range(1,n)):
        for k in index_subset:
            C[S,k] = argmin(lambda m: C[S-k,m] + d(G,m,k), S - k)
            shortest_path = argmin(lambda k: C[set(range(1,n)),k] + d(G,1,k), range(2,n))
return shortest_path

# also needed....
def d(G, i, j):
    return G[i][j]
def subsets_of_size(n, s): # returns a list of sets
    # complicated code goes here
    pass
def argmin(f, l):
    best = l[0]
    bestVal = f(best)
    for x in l[1:]:
        newVal = f(x)
        if newVal < bestVal:
            best = x
            bestVal = newVal
    return best

Some notes:

1. The source algorithm is not complete. At least, its formatting is weird in the inner loop, and it rebinds k in the second argmin. So the whole thing is probably wrong; I've not tried to run this code.
2. arguments to range should probably all be increased by 1 since Python counts from 0, not 1. (and in general counting from 1 is a bad idea).
3. I assume that G is a dictionary of type { from : { to : length } }. In other words, an adjacency list representation.
4. I inferred that C is a dictionary of type { (set(int),int) : int }. I could be wrong.
5. I use a set as keys to C. In real Python, you must convert to a frozen_set first. The conversion is just busywork so I left it out.
6. I can't remember the set operators in Python. I seem to remember it uses | and & instead of + and -.
7. I didn't write subsets_of_size. It's fairly complicated.