我正在写一些问答游戏，如果玩家未能解决问题，我需要计算机来解决问答中的 1 个游戏。
给定数据：
- 要使用的 6 个数字的列表，例如 4、8、6、2、15、50。
- 目标值，其中 0 < 值 < 1000，例如 590。
- 可用的操作是除法、加法、乘法和除法。
- 可以使用括号。
生成评估等于或尽可能接近目标值的数学表达式。例如，对于上面给出的数字，表达式可以是：(6 + 4) * 50 + 15 * (8 - 2) = 590
我的算法如下：
- 从上面的（1）生成给定数字的所有子集的所有排列
- 对于每个排列，生成所有括号和运算符组合
- 在算法运行时跟踪最接近的值
我想不出对上述蛮力算法的任何智能优化，这将加速它的数量级。另外我必须针对最坏的情况进行优化，因为许多问答游戏将在服务器上同时运行。
今天为解决这个问题而编写的代码是（从项目中提取的相关内容）：
from operator import add, sub, mul, div
import itertools
ops = ['+', '-', '/', '*']
op_map = {'+': add, '-': sub, '/': div, '*': mul}
# iterate over 1 permutation and generates parentheses and operator combinations
def iter_combinations(seq):
if len(seq) == 1:
yield seq[0], str(seq[0])
else:
for i in range(len(seq)):
left, right = seq[:i], seq[i:] # split input list at i`th place
# generate cartesian product
for l, l_str in iter_combinations(left):
for r, r_str in iter_combinations(right):
for op in ops:
if op_map[op] is div and r == 0: # cant divide by zero
continue
else:
yield op_map[op](float(l), r), \
('(' + l_str + op + r_str + ')')
numbers = [4, 8, 6, 2, 15, 50]
target = best_value = 590
best_item = None
for i in range(len(numbers)):
for current in itertools.permutations(numbers, i+1): # generate perms
for value, item in iter_combinations(list(current)):
if value < 0:
continue
if abs(target - value) < best_value:
best_value = abs(target - value)
best_item = item
print best_item
它打印：((((4*6)+50)*8)-2)。用不同的值对其进行了一些测试，它似乎工作正常。我还有一个功能可以删除不必要的括号，但它与问题无关，所以没有发布。
问题在于，由于所有这些排列、组合和评估，这运行非常缓慢。在我的 mac book air 上，它运行了几分钟，例如 1 个。我想让它在几秒钟内运行在同一台机器上，因为许多问答游戏实例将同时在服务器上运行。所以问题是：
- 我可以以某种方式（按数量级）加速当前算法吗？
- 我是否缺少针对此问题的其他一些运行速度更快的算法？