Eliminate nested loops

Question

I am assigned a task where I need to build a brute force algorithm. Which should find the best route through a graph containing 14400 peaks, 600 for each of the 24 hours a day. On each of the 600 peaks, you can choose between 480 peaks in the next hour.

I tried to build the algorithm, but as it is now, it is impossible to cross the graph, because I have many nested loops. I'm new to Python, is there a 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 showed only nested loops during the first 3 hours, but if at all possible, it should repeat all 24 hours.

Or am I thinking about this problem is everything wrong?

Answer 1

24 240 ( - 480). , 24**240 . , 10**57. . , , .

---

BJ Myers , . , 1. :

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

generate_paths1 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]

generate_paths2 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]

! generate_paths3 , generate_paths2. , . , generate_paths1, generate_paths2 generate_paths3 - :

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):
    ...

---

, . (LP) , .

LP :

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
    ... 

LP , :

()   ,    . ( )

moves = range(601)

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

600 , S , 0 , S . , 0 600 600 0.

6**24, , 240**24, , .

---

scipy.optimimize.linprog, - 24- - :

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))

,

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

Answer 2

.

---

.

for x in ...
    for y in ...
        for z in ...
            ...

. :

def process_xy(x, y):
    for z in ...

for x in ...
    for y in ...
        process_xy(x, y)

, :

• , (process_xy)
• , , - - .

---

, :

for x0 in a0:
    for x1 in a1:
        for x2 in a2:
             ....

import itertools

for (x0, x1, x2) in itertools.product(a0, a1, a2):
    ...

, .