我正在写一些问答游戏，如果玩家未能解决问题，需要计算机在测验中解决1个游戏。
鉴于数据：
生成数学表达式，其中评估与目标值相等或尽可能接近。例如，对于上面给出的数字，表达式可以是：（6 + 4）* 50 + 15 *（8-2）= 590
我的算法如下：
我想不出上面的蛮力算法的任何智能优化，这将使其加速数量级。此外，我必须优化最坏的情况，因为许多测验游戏将在服务器上同时运行。
今天为解决这个问题而编写的代码是（从项目中提取的相关内容）：
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书籍上，它可以运行几分钟，例如。我想让它在同一台机器上运行几秒钟，因为许多测验游戏实例将在服务器上同时运行。所以问题是：
您可以使用给定的数字构建所有可能的表达式树并对其进行评估。您不需要将它们全部保存在内存中，只需在找到目标号码时打印它们：
首先，我们需要一个类来保存表达式。最好将它设计为不可变的，因此它的值可以预先计算。像这样的东西：
class Expr:
'''An Expr can be built with two different calls:
-Expr(number) to build a literal expression
-Expr(a, op, b) to build a complex expression.
There a and b will be of type Expr,
and op will be one of ('+','-', '*', '/').
'''
def __init__(self, *args):
if len(args) == 1:
self.left = self.right = self.op = None
self.value = args[0]
else:
self.left = args[0]
self.right = args[2]
self.op = args[1]
if self.op == '+':
self.value = self.left.value + self.right.value
elif self.op == '-':
self.value = self.left.value - self.right.value
elif self.op == '*':
self.value = self.left.value * self.right.value
elif self.op == '/':
self.value = self.left.value // self.right.value
def __str__(self):
'''It can be done smarter not to print redundant parentheses,
but that is out of the scope of this problem.
'''
if self.op:
return "({0}{1}{2})".format(self.left, self.op, self.right)
else:
return "{0}".format(self.value)
现在我们可以编写一个递归函数，用一组给定的表达式构建所有可能的表达式树，并打印出等于我们目标值的表达式。我们将使用itertools模块，这总是很有趣。
我们可以使用itertools.combinations()或itertools.permutations()，区别在于顺序。我们的一些操作是可交换的，有些则不是，因此我们可以使用permutations()并假设我们将获得许多非常类似的解决方案。或者我们可以使用combinations()并在操作不可交换时手动重新排序值。
import itertools
OPS = ('+', '-', '*', '/')
def SearchTrees(current, target):
''' current is the current set of expressions.
target is the target number.
'''
for a,b in itertools.combinations(current, 2):
current.remove(a)
current.remove(b)
for o in OPS:
# This checks whether this operation is commutative
if o == '-' or o == '/':
conmut = ((a,b), (b,a))
else:
conmut = ((a,b),)
for aa, bb in conmut:
# You do not specify what to do with the division.
# I'm assuming that only integer divisions are allowed.
if o == '/' and (bb.value == 0 or aa.value % bb.value != 0):
continue
e = Expr(aa, o, bb)
# If a solution is found, print it
if e.value == target:
print(e.value, '=', e)
current.add(e)
# Recursive call!
SearchTrees(current, target)
# Do not forget to leave the set as it were before
current.remove(e)
# Ditto
current.add(b)
current.add(a)
然后是主要电话：
NUMBERS = [4, 8, 6, 2, 15, 50]
TARGET = 590
initial = set(map(Expr, NUMBERS))
SearchTrees(initial, TARGET)
并做了！有了这些数据，我将在21秒内获得719种不同的解决方案！当然，其中许多是同一表达的微不足道的变体。
我会尝试至少使用AST 使表达式生成部分更容易 （不需要乱用括号）。 http://en.wikipedia.org/wiki/Abstract_syntax_tree 1）生成具有N个节点的一些树 （N =您拥有的数字）。 我之前读过你们中有多少人 随着N的增长，它们的大小是严重的。 严肃地说，我的意思不仅仅是多项式，至少可以说。 2）现在开始改变操作 在非叶节点中并继续评估 结果。 但这又是回溯和过多的自由度。 这是一项计算复杂的任务。我相信如果你 像你一样问问题：“让我们在输出上生成一个数字K. 这样| K-V |是最小的“（这里V是预定义的期望结果， 即你的例子中的590），那么我猜这个问题甚至是NP完全的。 如果我的直觉对我撒谎，请有人纠正我。 所以我认为甚至生成所有可能的AST（假设只有1次操作 允许）是NP完整的，因为它们的计数不是多项式的。不要再说了 这里允许超过1次操作，而不是谈到最小差异要求 （在结果和期望的结果之间）。
24个游戏是4个数字到目标24，你的游戏是6个数字到目标x（0 <x <1000）。
那非常相似。
这是快速解决方案，获取所有结果并在我的rMBP中打印一个关于1-3s，我认为在这个游戏中一个解决方案打印是好的:)，我将在稍后解释：
def mrange(mask):
#twice faster from Evgeny Kluev
x = 0
while x != mask:
x = (x - mask) & mask
yield x
def f( i ) :
global s
if s[i] :
#get cached group
return s[i]
for x in mrange(i & (i - 1)) :
#when x & i == x
#x is a child group in group i
#i-x is also a child group in group i
fk = fork( f(x), f(i-x) )
s[i] = merge( s[i], fk )
return s[i]
def merge( s1, s2 ) :
if not s1 :
return s2
if not s2 :
return s1
for i in s2 :
#print just one way quickly
s1[i] = s2[i]
#combine all ways, slowly
# if i in s1 :
# s1[i].update(s2[i])
# else :
# s1[i] = s2[i]
return s1
def fork( s1, s2 ) :
d = {}
#fork s1 s2
for i in s1 :
for j in s2 :
if not i + j in d :
d[i + j] = getExp( s1[i], s2[j], "+" )
if not i - j in d :
d[i - j] = getExp( s1[i], s2[j], "-" )
if not j - i in d :
d[j - i] = getExp( s2[j], s1[i], "-" )
if not i * j in d :
d[i * j] = getExp( s1[i], s2[j], "*" )
if j != 0 and not i / j in d :
d[i / j] = getExp( s1[i], s2[j], "/" )
if i != 0 and not j / i in d :
d[j / i] = getExp( s2[j], s1[i], "/" )
return d
def getExp( s1, s2, op ) :
exp = {}
for i in s1 :
for j in s2 :
exp['('+i+op+j+')'] = 1
#just print one way
break
#just print one way
break
return exp
def check( s ) :
num = 0
for i in xrange(target,0,-1):
if i in s :
if i == target :
print numbers, target, "\nFind ", len(s[i]), 'ways'
for exp in s[i]:
print exp, ' = ', i
else :
print numbers, target, "\nFind nearest ", i, 'in', len(s[i]), 'ways'
for exp in s[i]:
print exp, ' = ', i
break
print '\n'
def game( numbers, target ) :
global s
s = [None]*(2**len(numbers))
for i in xrange(0,len(numbers)) :
numbers[i] = float(numbers[i])
n = len(numbers)
for i in xrange(0,n) :
s[2**i] = { numbers[i]: {str(numbers[i]):1} }
for i in xrange(1,2**n) :
#we will get the f(numbers) in s[2**n-1]
s[i] = f(i)
check(s[2**n-1])
numbers = [4, 8, 6, 2, 2, 5]
s = [None]*(2**len(numbers))
target = 590
game( numbers, target )
numbers = [1,2,3,4,5,6]
target = 590
game( numbers, target )
假设A是你的6个数字列表。
我们定义f(A)是可以通过所有A数计算的所有结果，如果我们搜索f(A)，我们将找到目标是否在其中并获得答案或最接近的答案。
我们可以将A分成两个真正的子组：A1和A-A1（A1不是空的而不等于A），它将问题从f(A)切换到f(A1)和f(A-A1)。因为我们知道f(A) = Union( a+b, a-b, b-a, a*b, a/b(b!=0), b/a(a!=0) )，A中的a，A-A1中的b。
我们使用fork f(A) = Union( fork(A1,A-A1) )代表这样的过程。我们可以删除fork()中的所有重复值，因此我们可以缩小范围并使程序更快。
所以，如果A = [1,2,3,4,5,6]，那么f(A) = fork( f([1]),f([2,3,4,5,6]) ) U ... U fork( f([1,2,3]), f([4,5,6]) ) U ... U代表联盟。
我们将看到f（[2,3,4,5,6]）= fork（f（[2,3]），f（[4,5,6]））U ...，f（[3， 4,5,6]）= fork（f（[3]），f（[4,5,6]））U ...，两者中使用的f（[4,5,6]）。
因此，如果我们可以缓存每个f（[...]），程序可以更快。
我们可以在A中得到2^len(A) - 2（A1，A-A1）。我们可以使用二进制代表它。
例如：A = [1,2,3,4,5,6]，A1 = [1,2,3]，则二元000111（7）代表A1。 A2 = [1,3,5]，二元010101（21）代表A2。 A3 = [1]，然后二进制000001（1）代表A3 ......
所以我们得到一个代表A中所有组的方法，我们可以缓存它们并使所有进程更快！
六个数字，四个操作和括号的所有组合最多为5 * 9！至少。所以我认为你应该使用一些AI算法。使用遗传编程或优化似乎是要遵循的道路。
在第11章“进化智力”一书中的Programming Collective Intelligence中，您将找到您想要的内容以及更多内容。该章解释了如何找到一个结合操作和数字（如你所愿）的数学函数来匹配结果。你会惊讶于这样的任务有多容易。
PD：这些示例是使用Python编写的。
我们的想法是不搜索目标值的单个表达式，而是搜索等式的一部分中包含目标值且两个部分具有几乎相等的操作数（2和3）的等式。由于等式的每个部分相对较小，因此不需要花费太多时间来为给定的输入值生成所有可能的表达式。在生成等式的两个部分之后，可以扫描包含这些表达式的值的一对排序的数组，并在其中找到一对相等（或至少最佳匹配）的值。找到两个匹配值后，我们可以得到相应的表达式并将它们连接成一个表达式（换句话说，求解方程式）。
为了将两个表达式树连接在一起，我们可以从一个树的根到达“目标”叶子，对于该路径上的每个节点反转相应的操作('*' to '/', '/' to '*' or '/', '+' to '-', '-' to '+' or '-')，并将“反向”根节点移动到其他树（也作为根节点）。
当所有操作都是可逆的时，该算法更快更容易实现。所以最好使用浮点除法（如我的实现）或合理除法。截断整数除法是最困难的情况，因为它为不同的输入产生相同的结果（42/25 = 1且25/25也是1）。使用零余数整数除法，当精确结果可用时，该算法几乎立即给出结果，但需要一些修改以在需要近似结果时正确工作。
正如@WolframH所注意到的，没有那么多可能的输入数字组合。如果可以重复，只有3 * 3 *（49 + 4-1）= 4455。或者3 * 3 *（49）= 1134没有重复。这允许我们离线预处理所有可能的输入，以紧凑的形式存储结果，并且当需要某些特定结果时快速解压缩一个预处理值。
预处理程序应采用6个数字的数组，并为所有可能的表达式生成值。然后它应该删除超出范围的值并找到没有完全匹配的所有情况的最接近的结果。所有这些都可以通过@Tim提出的算法来执行。他的代码需要进行少量修改才能完成。它也是最快的替代品。由于预处理是离线的，我们可以使用比解释Python更好的东西。一种选择是PyPy，另一种是使用一些快速解释的语言。预处理所有可能的输入不应超过几分钟。
谈到存储所有预处理值所需的内存，唯一的问题是结果表达式。如果以字符串形式存储，它们将占用4455 * 999 * 30字节或120Mb。但每个表达式都可以压缩。它可以用后缀表示法表示，如：arg1 arg2 + arg3 arg4 + *。为了存储这个，我们需要10位来存储所有参数的排列，10位来存储5个操作，8位来指定参数和操作是如何交错的（6个参数+5个操作 - 3个预定位置：前两个总是参数，最后一个总是运作）。每棵树28位或4字节，这意味着对于具有重复项的整个数据集仅为20Mb，或者在没有它们的情况下为5Mb。
有一些方法可以加速OP中的算法：
在通过这些想法增强OP的方法后，实现了大约30倍的加速：
from itertools import combinations
numbers = [4, 8, 6, 2, 15, 50]
target = best_value = 590
best_item = None
subsets = {}
def get_best(value, item):
global best_value, target, best_item
if value >= 0 and abs(target - value) < best_value:
best_value = abs(target - value)
best_item = item
return value, item
def compare_one(value, op, left, right):
item = ('(' + left + op + right + ')')
return get_best(value, item)
def apply_one(left, right):
yield compare_one(left[0] + right[0], '+', left[1], right[1])
yield compare_one(left[0] * right[0], '*', left[1], right[1])
yield compare_one(left[0] - right[0], '-', left[1], right[1])
yield compare_one(right[0] - left[0], '-', right[1], left[1])
if right[0] != 0 and left[0] >= right[0]:
yield compare_one(left[0] / right[0], '/', left[1], right[1])
if left[0] != 0 and right[0] >= left[0]:
yield compare_one(right[0] / left[0], '/', right[1], left[1])
def memorize(seq):
fs = frozenset(seq)
if fs in subsets:
for x in subsets[fs].items():
yield x
else:
subsets[fs] = {}
for value, item in try_all(seq):
subsets[fs][value] = item
yield value, item
def apply_all(left, right):
for l in memorize(left):
for r in memorize(right):
for x in apply_one(l, r):
yield x;
def try_all(seq):
if len(seq) == 1:
yield get_best(numbers[seq[0]], str(numbers[seq[0]]))
for length in range(1, len(seq)):
for x in combinations(seq[1:], length):
for value, item in apply_all(list(x), list(set(seq) - set(x))):
yield value, item
for x, y in try_all([0, 1, 2, 3, 4, 5]): pass
print best_item
如果您为问题添加一些约束，则可以提高速度：
好吧，我不会放弃。按照你问题的所有答案的一行，我想出了另一种算法。该算法为解决方案提供了3毫秒的时间平均值。
#! -*- coding: utf-8 -*-
import copy
numbers = [4, 8, 6, 2, 15, 50]
target = 590
operations = {
'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: y == 0 and 1e30 or x / y # Handle zero division
}
def chain_op(target, numbers, result=None, expression=""):
if len(numbers) == 0:
return (expression, result)
else:
for choosen_number in numbers:
remaining_numbers = copy.copy(numbers)
remaining_numbers.remove(choosen_number)
if result is None:
return chain_op(target, remaining_numbers, choosen_number, str(choosen_number))
else:
incomming_results = []
for key, op in operations.items():
new_result = op(result, choosen_number)
new_expression = "%s%s%d" % (expression, key, choosen_number)
incomming_results.append(chain_op(target, remaining_numbers, new_result, new_expression))
diff = 1e30
selected = None
for exp_result in incomming_results:
exp, res = exp_result
if abs(res - target) < diff:
diff = abs(res - target)
selected = exp_result
if diff == 0:
break
return selected
if __name__ == '__main__':
print chain_op(target, numbers)
错误：此算法不包含含有括号的解法。它总是击中目标或最接近的结果，我的坏。还是很快。它可以适用于支持括号而无需太多工作。
实际上，你可以做两件事来加快毫秒的时间。
您正在尝试通过生成数字和目标数量来查找给定测验的解决方案。相反，您可以生成解决方案并删除操作。你可以构建一些聪明的东西，它将生成几个测验并选择最有趣的一个，在这种情况下你怎么放松尽可能接近的选项。
另一种方法是预先计算。解决100个测试，在应用程序中使用它们作为内置函数，并在运行中生成新的测试，尝试将测验堆栈保持在100，同时尝试仅向用户提供新的测试。我在bible games遇到了同样的问题，我用这种方法加快了速度。而不是10秒的问题，我需要几毫秒，因为我在后台生成新问题，并始终保持我的堆栈为100。
动态编程怎么样，因为你需要相同的结果来计算其他选项？