Find the best path amongst N random points

Question

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

python dp.py

with python 2.7.3.

I would appreciate any tips to improve the speed and the memory use of that program.

The content of dp.py is

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 [0]

    # 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[0] - A[0]) ** 2 + (B[1] - A[1]) ** 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 = [[0] 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()

Answer 1

One minor way to improve speed would be not to calculate the square root of all of the distances before comparison, but instead only return the square root of the shortest distance squared because the square root function is costly.

Answer 2

I would appreciate any tips to improve the speed and the memory use of that program.

I think the biggest issue is the algorithm. This looks like a quadratic running time:

for n in range(1, L - 1):
    for point_m in range(1, L):

But I can't help you with this.

I have only these suggestions:

• In Python 2 use xrange instead of range, because it creates an intermediary list that you just throw away after iterating over it.

• Whenever possible, use enumerate to walk over a list and get the items and their indexes. For example this

  for n in range(L):
      for m in range(n):
          A = points[n]
          B = points[m]
          distances[n * L + m] = math.sqrt((B[0] - A[0]) ** 2 + (B[1] - A[1]) ** 2)
          distances[m * L + n] = distances[n * L + m]
  

  Will become this

  for n, A in enumerate(points):
      for m in xrange(n):
          B = points[m]
          i = n * L + m
          distances[i] = math.sqrt((B[0] - A[0]) ** 2 + (B[1] - A[1]) ** 2)
          distances[m * L + n] = distances[i]