Dynamic Programming algorithm for the Travelling Salesman problem

tsp-dynamic-programming.py

import itertools
from sklearn.metrics.pairwise import euclidean_distances

def tsp(points):
    distances = euclidean_distances(points)
    
    A = {(frozenset([0, j+1]), j+1): dist for j, dist in enumerate(distances[0][1:])}
    A[frozenset([0]), 0] = 0
    
    n = len(points)
    for m in range(2, n):
        A_current = {}
        for S in [frozenset(comb) | {0} for comb in itertools.combinations(range(1, n), m)]:
            for j in S - {0}:
                A_current[S, j] = min([A[S-{j}, k] + distances[k, j] for k in S if k != 0 and k!= j])
                
        # save on space by only holding the most recent set of results
        # which is all that is needed for the recurrence
        A = A_current
        
    min_tour = min([A[frozenset(range(n)), j] + distances[j, 0]] for j in range(1, n))
    
    return min_tour