Eliminating nested loops

Question

I have been given an assignment where I have to build a brute-force algorithm. Which has to find the optimal route through a graph containing 14400 vertices, 600 for each of the 24 hours in a day. At each of the 600 vertices it is possible to choose between 480 vertices for the next hour.

I have tried to build an algorithm, but the way it is now it isn't possible to traverse the graph, because I end up with a lot of nested loops. I am new to Python, Is there any way to improve the algorithm?

Path = [0] * 2
S = [12, 9, 20];
K = 10
S[:] = [x - K for x in S]

for x in range(0,600):     #1.hour              
Path[0]= x
for y in range(-240,240):    # 2.hour
    hour2 = x+y
    if 0 <= hour2 <= 600:
         Path[1] = hour2             
         for y in range(-240,240):   # 3.hour
             hour3 = hour2 + y
             if 0 <= hour3 <= 600:
                 Path[2]= hour3
                 price = sum([a*b for a,b in zip(Path,S)])
                 if maxprice < price:
                     maxprice = price
                     Optimalpath = list(Path)
print Optimalpath
print maxprice

I have only shown the nested loops for the first 3 hours but if at all possible it has to iterate for all of the 24 hours.

Or am I thinking of this problem all wrong?

unutbu · Accepted Answer

At each of the 24 stages, there are at least 240 possibilities (and often as many as 480). So there are at least 24**240 possible paths. That's more than 10**57 paths. There is no way you can solve this problem by brute force. The problem can be solved, however, using linear programming methods.

As BJ Myers suggested, you could use recursion to generate all possible paths. Suppose you had a generator function that generated all possible paths of length 1. That's easy:

def generate_paths1():
    for i in range(600):
        yield [i]

You could use generate_paths1 to generate all possible paths of length 2:

def generate_paths2():
    for path in generate_paths1():
        current = path[-1]
        low = max(current-240, 0)
        high = min(current+240, 600)
        for i in range(low, high):
            yield path+[i]

and you could use generate_paths2 to generate all paths of length 3:

def generate_paths3():
    for path in generate_paths2():
        current = path[-1]
        low = max(current-240, 0)
        high = min(current+240, 600)
        for i in range(low, high):
            yield path+[i]

But wait! generate_paths3 is practically the same function as generate_paths2. Surely there is a better way. We can write one recursive function that can do everything generate_paths1, generate_paths2, and generate_paths3 can -- and more:

def generate_paths(N):
    # moves = range(0, 601, 120)   # see below for why this is an improvement
    moves = range(601)
    if N == 1:
        for i in moves:
            yield [i]
    else:
        for path in generate_paths(N-1):
            current = path[-1]
            low = max(current-240, 0)
            high = min(current+240, 600)
            for i in [i for i in moves if low <= i <= high]:
                yield path+[i]

N = 3
for path in generate_paths(N):
    ...

While being able to generate all the paths is wonderful, the are just too many paths. If we recognize the problem as a linear programming (LP) problem, we can do better.

Your problem can be expressed as an LP problem like this:

Maximize price = sum([a*b for a, b in zip(S, path)])
Subject to:

    x[1] - x[0] <= 240
    x[0] - x[1] <= 240
    x[2] - x[1] <= 240
    x[1] - x[2] <= 240
    ...

One of the properties of the solution to a LP problem is that:

if a feasible solution exists and if the (linear) objective function is bounded, then the optimum value is always attained on the boundary of the optimal level-set. (my emphasis)

therefore, you could replace moves = range(601) with

    moves = range(0, 601, 120)
    # [0, 120, 240, 360, 480, 600]

because the optimal solution will tend to use 600 to maximize the price when S is positive and use 0 to minimize the loss when S is negative. The other values in between are the maximum hops the optimal solution would need to move from 0 to 600 or from 600 down to 0.

This reduces the number of paths to 6**24 which is much much smaller than 240**24, bust still too large to admit a brute-force solution.

Using scipy.optimimize.linprog you could solve for optimal paths -- even for the full 24-stage problem -- like this:

import numpy as np
import scipy.optimize as optimize

"""
Minimize: np.dot(S, x)
Subject to: np.dot(A, x) <= b
"""
N = 24
K = 10
S = np.random.randint(-K//2, +K//2, size=N)
A = np.zeros((2*(N-1), N), dtype=int)
for i in range(N-1):
    A[2*i, i:i+2] = (1, -1)
    A[2*i+1, i:i+2] = (-1, 1)
b = np.array([240]*A.shape[0])
bounds = [(0, 600)]*N
result = optimize.linprog(c=-S, A_ub=A, b_ub=b, bounds=bounds)

optimal_path = result.x
max_price = np.dot(S, optimal_path)
print('''S: {}
optimal_path: {}
price: {}'''.format(S, optimal_path, max_price))

which yields results like

S: [ 0  1  3  4 -5 -1  0 -3 -4  0  3  2 -5  1 -4 -1 -3  2  0 -2  0  4 -2  2]
optimal_path: [ 360.  600.  600.  360.  120.    0.    0.    0.    0.  240.  480.  240.
    0.  240.    0.    0.    0.  240.    0.  120.  360.  600.  360.  600.]
price: 8520.0

Eliminating nested loops

Answers (2)

Related Questions