For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points. I wanted to use a dynamic programming approach as N will be limited to a maximum of 15 points.
The following program works for me running
with python 2.7.3.
I would appreciate any tips to improve the speed and the memory use of that program.
The content of
import random import math # Container for the points points =  # Generate N random points def create_random_points(size): global points for n in range(size): x = random.uniform(0, 500) y = random.uniform(0, 500) points.append([x, y]) # Find the path through those points def order_points(): global points # How many points do we have? L = len(points) # No points at all if L < 1: return  # A single point if L == 1: return  # Calculate all the different distances distances = [0 for n in range(L * L)] for n in range(L): for m in range(n): A = points[n] B = points[m] distances[n * L + m] = math.sqrt((B - A) ** 2 + (B - A) ** 2) distances[m * L + n] = distances[n * L + m] # Calculate the best path: dynamic programming # Initialise the distance and path variables sum_path = [0 for n in range(L - 1)] path = [ for n in range(L - 1)] # Calculate the first iteration for point_m in range(1, L): sum_path[point_m - 1] += distances[point_m] path[point_m - 1].append(point_m) # Calculate the following iterations for n in range(1, L - 1): for point_m in range(1, L): dist = -1 prev = -1 for point_n in range(1, L): if point_n == point_m: continue if point_n in path[point_m - 1]: continue d = distances[point_m * L + point_n] if dist == -1 or dist < d: dist = d prev = point_n sum_path[point_m - 1] += dist path[point_m - 1].append(prev) # Calculate the last iteration for point_m in range(1, L): sum_path[point_m - 1] += distances[point_m] path[point_m - 1].append(0) best_score = min(sum_path) for point_m in range(1, L): if sum_path[point_m - 1] == best_score: best_path = path[point_m - 1] return best_path create_random_points(5) print 'We have the following points:' print points print '' print 'And the best path is:' print order_points()