我正在写一些问答游戏,如果玩家未能解决问题,需要计算机在测验中解决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书籍上,它可以运行几分钟,例如.我想让它在同一台机器上运行几秒钟,因为许多测验游戏实例将在服务器上同时运行.所以问题是:
我可以以某种方式(按数量级)加速当前算法吗?
我是否遗漏了其他算法来解决这个问题,这个算法会运行得更快?
rodrigo.. 12
您可以使用给定的数字构建所有可能的表达式树并对其进行规避.您不需要将它们全部保存在内存中,只需在找到目标号码时打印它们:
首先,我们需要一个类来保存表达式.最好将它设计为不可变的,因此它的值可以预先计算.像这样的东西:
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种不同的解决方案!当然,其中许多是同一表达的微不足道的变体.