消除嵌套循环

Question

我接到了一项任务，我必须构建一个蛮力算法。它必须通过包含 14400 个顶点的图形找到最佳路线，一天 24 小时中的每个小时 600 个。在 600 个顶点中的每一个，都可以在下一个小时的 480 个顶点之间进行选择。

我曾尝试构建一个算法，但现在无法遍历该图，因为我最终得到了很多嵌套循环。我是 Python 的新手，有什么改进算法的方法吗？

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

我只展示了前 3 小时的嵌套循环，但如果可能的话，它必须在所有 24 小时内迭代。

还是我对这个问题的看法全错了？

Answer 1

您可以使用以下组合。

考虑将循环体变成函数。

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

不过，这主要在嵌套范围不依赖于外部范围时有用。

Answer 2

在这 24 个阶段中的每个阶段，至少有 240 种可能性（而且通常是多达 480 个）。所以至少有 24**240 种可能的路径。这比 10**57 路径。您无法通过蛮力解决此问题。这但是，使用线性规划可以解决问题方法.

与一样，您可以使用递归来生成所有可能的路径。假设您有一个 generator function 生成了所有长度为 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_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 问题的解的一个属性是：

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)

因此，您可以将 moves = range(601) 替换为

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

因为最优解倾向于在S为正时使用600来最大化价格，在S为负时使用0来最小化损失。中间的其他值是最佳解决方案从 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

消除嵌套循环

Eliminating nested loops

python

algorithm

graph-theory