Revisions
-
mlalevic revised this gist
Sep 9, 2013 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -6,7 +6,7 @@ def solve_tsp_dynamic(points): cnt = len(points) for m in range(2, cnt): B = {} for S in [frozenset(C) | {0} for C in itertools.combinations(range(1, cnt), m)]: for j in S - {0}: B[(S, j)] = min( [(A[(S-{j},k)][0] + all_distances[k][j], A[(S-{j},k)][1] + [j]) for k in S if k != 0 and k!=j]) #this will use 0th index of tuple for ordering, the same as if key=itemgetter(0) used A = B -
mlalevic revised this gist
Aug 13, 2013 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -10,5 +10,5 @@ def solve_tsp_dynamic(points): for j in S - {0}: B[(S, j)] = min( [(A[(S-{j},k)][0] + all_distances[k][j], A[(S-{j},k)][1] + [j]) for k in S if k != 0 and k!=j]) #this will use 0th index of tuple for ordering, the same as if key=itemgetter(0) used A = B res = min([(A[d][0] + all_distances[0][d[1]], A[d][1]) for d in iter(A)]) return res[1] -
mlalevic created this gist
Aug 13, 2013 .There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,14 @@ def solve_tsp_dynamic(points): #calc all lengths all_distances = [[length(x,y) for y in points] for x in points] #initial value - just distance from 0 to every other point + keep the track of edges A = {(frozenset([0, idx+1]), idx+1): (dist, [0,idx+1]) for idx,dist in enumerate(all_distances[0][1:])} cnt = len(points) for m in range(2, cnt): B = {} for S in [c[0] | {n} for c in iter(A) for n in range(1,cnt) if n not in c[0]]:#Cartesian product so we get all combinations of sets for j in S - {0}: B[(S, j)] = min( [(A[(S-{j},k)][0] + all_distances[k][j], A[(S-{j},k)][1] + [j]) for k in S if k != 0 and k!=j]) #this will use 0th index of tuple for ordering, the same as if key=itemgetter(0) used A = B res = min([(A[d][0] + all_distances[0][d[1]], A[d][1]) for d in iter(A)]) #key=itemgetter(0)) return res[1]