Skip to content

Instantly share code, notes, and snippets.

@vyraun
Forked from mlalevic/dynamic_tsp.py
Created October 12, 2016 16:12

Revisions

  1. @mlalevic mlalevic revised this gist Sep 9, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion dynamic_tsp.py
    Original 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 [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 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
  2. @mlalevic mlalevic revised this gist Aug 13, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion dynamic_tsp.py
    Original 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)]) #key=itemgetter(0))
    res = min([(A[d][0] + all_distances[0][d[1]], A[d][1]) for d in iter(A)])
    return res[1]
  3. @mlalevic mlalevic created this gist Aug 13, 2013.
    14 changes: 14 additions & 0 deletions dynamic_tsp.py
    Original 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]