生成具有最接近请求的结果值的等式,具有速度问题

Question

我正在写一些问答游戏,如果玩家未能解决问题,需要计算机在测验中解决1个游戏.

鉴于数据:

1. 要使用的6个号码的列表,例如4,8,6,2,15,50.
2. 目标值,其中0 <值<1000,例如590.
3. 可用的操作是除法,加法,乘法和除法.
4. 可以使用括号.

生成数学表达式,其中评估与目标值相等或尽可能接近.例如,对于上面给出的数字,表达式可以是:(6 + 4)*50 + 15*(8-2)= 590

我的算法如下:

1. 从上面的(1)生成给定数字的所有子集的所有排列
2. 对于每个排列,生成所有括号和运算符组合
3. 算法运行时跟踪最接近的值

我想不出上面的蛮力算法的任何智能优化,这将使其加速数量级.此外,我必须优化最坏的情况,因为许多测验游戏将在服务器上同时运行.

今天为解决这个问题而编写的代码是(从项目中提取的相关内容):

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书籍上,它可以运行几分钟,例如.我想让它在同一台机器上运行几秒钟,因为许多测验游戏实例将在服务器上同时运行.所以问题是:

1. 我可以以某种方式(按数量级)加速当前算法吗？
2. 我是否遗漏了其他算法来解决这个问题,这个算法会运行得更快？

Answer 1

您可以使用给定的数字构建所有可能的表达式树并对其进行规避.您不需要将它们全部保存在内存中,只需在找到目标号码时打印它们:

首先,我们需要一个类来保存表达式.最好将它设计为不可变的,因此它的值可以预先计算.像这样的东西:

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种不同的解决方案!当然,其中许多是同一表达的微不足道的变体.