Сгенерируйте уравнение с ближайшим к запрошенному значением результата, есть проблемы со скоростью

Вы можете построить все возможные деревья выражений с заданными числами и оценить их. Вам не нужно хранить их все в памяти, просто распечатайте их, когда целевой номер будет найден:

Сначала нам нужен класс для хранения выражения. Лучше сделать его неизменяемым, чтобы его значение можно было вычислить предварительно. Что-то вроде этого:

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)

Готово! С этими данными я получаю 719 различных решений всего за 21 секунду! Конечно, многие из них являются тривиальными вариациями одного и того же выражения.

Все комбинации для шести цифр, четырех операций и скобок до 5 * 9! как минимум. Поэтому я думаю, вам следует использовать какой-нибудь алгоритм ИИ. Использование генетического программирования или оптимизации, по-видимому, является путем, которым следует следовать.

В книге Программирование коллективного разума в главе 11 Развивая интеллект, вы найдете именно то, что хотите, и многое другое. В этой главе объясняется, как найти математическую функцию, сочетающую операции и числа (как вы хотите), чтобы получить результат. Вы удивитесь, насколько легко выполняется такая задача.

PD: Примеры написаны с использованием Python.

Я бы попробовал использовать 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, b в A-A1.

Мы используем вилку 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([...]), программа будет работать быстрее.

Мы можем получить 2^len(A) - 2 (A1,A-A1) в A. Мы можем использовать для этого двоичный код.

Например: 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, мы можем кэшировать их и ускорить весь процесс!

1. Быстрый полностью онлайн-алгоритм

Идея состоит в том, чтобы искать не отдельное выражение для целевого значения, а уравнение, в котором целевое значение входит в одну часть уравнения и обе части имеют почти одинаковое количество операций (2 и 3). Поскольку каждая часть уравнения относительно мала, создание всех возможных выражений для заданных входных значений не занимает много времени. После того, как обе части уравнения сгенерированы, можно просмотреть пару отсортированных массивов, содержащих значения этих выражений, и найти в них пару равных (или, по крайней мере, наиболее совпадающих) значений. После того, как будут найдены два совпадающих значения, мы можем получить соответствующие выражения и соединить их в одно выражение (другими словами, решить уравнение).

Чтобы соединить два дерева выражений вместе, мы могли бы спуститься от корня одного дерева к «целевому» листу, для каждого узла на этом пути инвертировать соответствующую операцию ('*' to '/', '/' to '*' or '/', '+' to '-', '-' to '+' or '-') и переместить «перевернутый» корневой узел в другое дерево (также как корневой узел).

Этот алгоритм быстрее и проще реализовать, когда все операции обратимы. Так что лучше использовать с делением с плавающей запятой (как в моей реализации) или с рациональным делением. Усечение целочисленного деления является наиболее сложным случаем, поскольку оно дает одинаковый результат для разных входных данных (42/25=1 и 25/25 также равно 1). С целочисленным делением с нулевым остатком этот алгоритм дает результат почти мгновенно, когда доступен точный результат, но требует некоторых модификаций для правильной работы, когда требуется приблизительный результат.

Посмотрите реализацию на Ideone.

2. Еще более быстрый подход с автономной предварительной обработкой

Как заметил @WolframH, возможных комбинаций входных чисел не так много. Только 3*3*(₄^9+4-1) = 4455, если возможны повторения. Или 3*3*(₄⁹) = 1134 без дубликатов. Это позволяет нам предварительно обрабатывать все возможные входные данные в автономном режиме, сохранять результаты в компактном виде и, когда требуется какой-то конкретный результат, быстро распаковывать одно из предварительно обработанных значений.

Программа предварительной обработки должна взять массив из 6 чисел и сгенерировать значения для всех возможных выражений. Затем он должен отбросить значения вне диапазона и найти ближайший результат для всех случаев, когда нет точного совпадения. Все это можно сделать по алгоритму, предложенному @Tim. Его код требует минимальных модификаций, чтобы сделать это. Также это самая быстрая альтернатива (пока). Поскольку предварительная обработка выполняется в автономном режиме, мы могли бы использовать что-то лучшее, чем интерпретируемый Python. Одна альтернатива — PyPy, другая — использовать какой-нибудь быстрый интерпретируемый язык. Предварительная обработка всех возможных входных данных не должна занимать более нескольких минут.

Говоря о памяти, необходимой для хранения всех предварительно обработанных значений, единственной проблемой являются результирующие выражения. При сохранении в виде строки они будут занимать до 4455*999*30 байт или 120 МБ. Но каждое выражение может быть сжато. Это может быть представлено в постфиксной нотации следующим образом: arg1 arg2 + arg3 arg4 + *. Чтобы сохранить это, нам нужно 10 бит для хранения перестановок всех аргументов, 10 бит для хранения 5 операций и 8 бит для указания того, как чередуются аргументы и операции (6 аргументов + 5 операций — 3 предопределенных позиции: первые две всегда являются аргументами). , последний всегда является операцией). 28 бит на дерево или 4 байта, то есть всего 20 Мб для всего набора данных с дубликатами или 5 Мб без них.

3. Медленный полностью онлайн-алгоритм

Есть несколько способов ускорить алгоритм в OP:

1. Наибольшего повышения скорости можно добиться, если не повторять каждую коммутативную операцию дважды и сделать дерево рекурсии менее разветвленным.
2. Возможна некоторая оптимизация путем удаления всех ветвей, где результат операции деления равен нулю.
3. Запоминание (динамическое программирование) здесь не может дать значительного прироста скорости, но может быть полезным.

После улучшения подхода 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

Дополнительные улучшения скорости возможны, если вы добавите некоторые ограничения к проблеме:

1. Если целочисленное деление возможно только тогда, когда остаток равен нулю.
2. Если все промежуточные результаты должны быть неотрицательными и/или ниже 1000.

Что ж, я не сдамся. Следуя строке всех ответов на ваш вопрос, я придумываю другой алгоритм. Этот алгоритм дает решение со средним временем 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, также старайтесь давать пользователю только новые викторины. У меня была такая же проблема в моих библейских играх. , и я использовал этот метод, чтобы ускорить процесс. Вместо 10 секунд на вопрос у меня уходит миллисекунды, так как я генерирую новый вопрос в фоновом режиме и всегда держу свой стек равным 100.

А как насчет динамического программирования, потому что вам нужны такие же результаты для расчета других вариантов?