Je suis un cours en ligne dans lequel l'une des affectations est de mettre en œuvre un algorithme de programmation dynamique pour résoudre le problème voyageur de vendeur (TSP). Ma mise en œuvre Python fonctionne pour les petits cas (~ 5 villes), mais pour la «vraie» application de 25 villes, il semble être très lent. Je cherche des suggestions pour accélérer l'algorithme.Suggestions pour accélérer une solution de programmation dynamique pour le vendeur ambulant Probl * m?
L'algorithme est décrit dans les extraits suivants:
La solution de programmation dynamique est également décrit à http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/, où des références supplémentaires sont données.
L'énoncé du problème de l'affectation est:
J'ai mis le pseudocode en utilisant un objet pandas géants DataFrame pour le tableau A. Puisque les ensembles ne sont pas traitables et ne peuvent pas être utilisés comme indices, j'ai plutôt utilisé des tuples, en prenant soin de les trier afin de faire d'eux des représentations uniques des ensembles. Voici le code ainsi que plusieurs cas de test de taille croissante:
import functools
from itertools import combinations
import numpy as np
import pandas as pd
from cached_property import cached_property
import pytest
def powerset_list(s):
'''Return a list of tuples representing all subsets of s'''
return functools.reduce(lambda x, y: x + y, [list(combinations(s, r)) for r in range(len(s)+1)])
class Graph(object):
def __init__(self, edges):
self.edges = edges
@cached_property
def nodes(self):
_nodes = set()
for edge in self.edges:
u, v, weight = edge
_nodes.add(u)
_nodes.add(v)
return list(_nodes)
@cached_property
def W(self):
'''Matrix of edge weights'''
n = len(self.nodes)
w = np.full((n, n), np.inf)
np.fill_diagonal(w, 0)
w = pd.DataFrame(w, index=range(1, n+1), columns=range(1, n+1))
for edge in self.edges:
u, v, weight = edge
w.set_value(u, v, weight)
w.set_value(v, u, weight)
return w
def tsp(self):
'''Solve the traveling salesman problem using a dynamic programming method'''
n = len(self.nodes)
sets = [(1,) + x for x in powerset_list(range(2, n+1))]
A = pd.DataFrame(np.full((len(sets), n), np.inf), index=sets, columns=range(1, n+1))
A.set_value((1,), 1, 0)
for m in range(2, n+1):
for S in [(1,) + perm for perm in combinations(range(2, n+1), m-1)]:
for j in set(S) - set([1]):
S_min_j = tuple(sorted(set(S) - set([j])))
A.set_value(S, j, min(A.get_value(S_min_j, k) + self.W.get_value(k, j) for k in S_min_j))
return min(A.get_value(tuple(range(1, n+1)), j) + self.W.get_value(j, 1) for j in range(2, n+1))
@pytest.fixture
def edges_geeksforgeeks():
'''Edges from the example graph on http://www.geeksforgeeks.org/travelling-salesman-problem-set-1/'''
return [(1, 2, 10), (1, 3, 15), (1, 4, 20), (2, 3, 35), (2, 4, 25), (3, 4, 30)]
def test_tsp(edges_geeksforgeeks):
graph = Graph(edges_geeksforgeeks)
min_cost = graph.tsp()
assert min_cost == 80
def dist(coord1, coord2):
return np.linalg.norm(np.array(coord1) - np.array(coord2))
def edges_from_coords(filename):
with open(filename) as f:
coords = [tuple(map(float, line.split())) for line in f.read().splitlines()[1:]]
nodes = list(range(1, len(coords) + 1))
coords = dict(zip(nodes, coords))
return [(comb[0], comb[1], dist(coords[comb[0]], coords[comb[1]])) for comb in combinations(nodes, 2)]
@pytest.mark.parametrize("test_input, expected", [("Hulburd_1.txt", 10.24), ("Hulburd_2.txt", 12.36), ("Hulburd_3.txt", 14.00)])
def test_Hulburd(test_input, expected):
'''Test data supplied by Eric Hulburd on the course forum'''
edges = edges_from_coords(test_input)
graph = Graph(edges)
min_cost = graph.tsp()
assert np.around(min_cost, decimals=2) == expected
@pytest.fixture
def edges_cities():
return edges_from_coords('tsp.txt')
@pytest.mark.skip(reason="This takes too long to run")
def test_tsp_cities(edges_cities):
graph = Graph(edges_cities)
min_cost = graph.tsp()
print("The minimum cost rounded down to the nearest integer is {}".format(int(np.floor(min_cost))))
if __name__ == "__main__":
pytest.main([__file__, "-s"])
Les fichiers utilisés dans les tests sont Hulburd_1.txt, Hulburd_2.txt, Hulburd_3.txt, et le fichier principal de l'affectation réelle, tsp.txt. Le problème est que le dernier test (ignoré) impliquant tsp.txt prend trop de temps à s'exécuter.
Comment accélérer l'algorithme? Sur le forum du cours, certains disent qu'ils l'ont fait fonctionner en ~ 3 minutes en utilisant des masques de bits et de la parallélisation; une autre suggestion était de simplifier les indices du tableau plutôt que d'utiliser des tuples.
Plus adapté à https://codereview.stackexchange.com/? – SiHa
Je suppose que le code de révision est pour les programmes qui fonctionnent essentiellement, mais mon MacBook Pro avec 16 Go de RAM ne peut pas exécuter le dernier test (avec 25 villes) parce qu'il manque de mémoire. Je suppose que je dois apporter quelques améliorations fondamentales (par exemple en utilisant la mémoisation au lieu d'une approche ascendante) pour rendre ce problème traitable. –