我接到了一项任务,我必须构建一个蛮力算法。它必须通过包含 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 小时内迭代。
还是我对这个问题的看法全错了?
最佳答案
在 24 个阶段中的每个阶段,至少有 240 种可能性(而且通常是
多达 480 个)。所以至少有 24**240
可能的路径。这比
10**57
路径。您无法通过蛮力解决此问题。这
问题可以解决,但是,使用 linear programming
methods .
作为BJ Myers suggested ,您可以使用递归来生成所有可能的路径。 假设你有一个 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
的功能几乎与
生成路径2
。当然有更好的方法。我们可以写一个递归
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):
...
虽然能够生成所有路径很棒,但路径实在是太多了。 如果我们将问题识别为 linear programming (LP) problem ,我们可以做得更好。
您的问题可以表示为这样的 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
关于python - 消除嵌套循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35530802/