Как сделать этот поиск первым быстрее?

Question

У меня есть алгоритм поиска, который ищет комбинации функций сложения и умножения, чтобы достичь определенного диапазона чисел из определенного диапазона чисел.Это поиск самой короткой программы, программа, которая является чем-то вроде AAMMA, где начальное число добавляется, добавляется, умножается, умножается, добавляет, где конечное число находится в диапазоне от r до s.Он должен работать для каждого числа в начальном диапазоне от p до q.

Ввод - это a и m, то, что вы добавляете и умножаете на (num + a), (num * m) для каждой функции.Что я делаю, так это пробую каждую комбинацию функций, пока не найду ту, которая работает, останавливая эту ветку, если она становится слишком большой.Если я нахожу «программу», которая работает, я пробую программу на всех других числах в начальном диапазоне.Он делает это до тех пор, пока не обнаружит ветви, которые не достигают диапазона без перехода.

Я знаю, что поиск не слишком типичен, но я не думаю, что есть возможность для дубликатов, поэтому я не включил найденный список.

Он работает для меньших диапазонов ивходные данные, такие как

Problem3("1 2 2 3 10 20")

, но для больших диапазонов, это просто навсегда, мой тестовый случай

Problem3("8 13 28 91 375383947 679472915")

, который я даже не видел завершенным.Какой мой лучший подход здесь, многопоточность (надеюсь, нет), как-то ускорить мои внутренние функции или просто отказаться от этого подхода.

def Problem3(s):
    a,m,p,q,r,s = list(map(int, s.split(" ")))

    print(str(a) + "-C-" + str(m) + " processor")
    print("Input guarenteed between " + str(p) + " and " + str(q))
    print("Output is real number between " + str(r) + " and " + str(s))

    open_set = queue.Queue()
#   curr path depth
    open_set.put([p, "", 0])

    while not open_set.empty():

        subroot = open_set.get()

        multiCurr = subroot[0] * m
        addCurr = subroot[0] + a
        depth = subroot[2] + 1

        if r <= addCurr <= s:
            truePath = True
            #If we find a working path, we need to check if it works for the other things
            path = subroot[1] + "A"
            for x in range(p, q+1):
                for op in path:
                    if op == "A":
                        x += a
                    if op == "M":
                        x *= m
                if r <= x <= s:
                    pass
                else:
                    truePath = False
                    break
            if truePath:
                print("Found " + path + " at depth " + str(depth) + " with starting number " + str(p) + ", output " + str())

        if r <= multiCurr <= s:
            truePath = True
            path = subroot[1] + "M"
            for x in range(p, q+1):
                for op in path:
                    if op == "A":
                        x += a
                    if op == "M":
                        x *= m
                if r <= x <= s:
                    pass
                else:
                    truePath = False
                    break
            if truePath:
                print("Found " + path + " at depth " + str(depth) + " with starting number " + str(p) + ", output " + str())

        if addCurr > s and multiCurr > s:
            pass
        elif multiCurr > s:
            open_set.put([addCurr, subroot[1] + "A", depth])
        elif addCurr > s:
            open_set.put([multiCurr, subroot[1] + "M", depth])
        else:
            open_set.put([multiCurr, subroot[1] + "M", depth])
            open_set.put([addCurr, subroot[1] + "A", depth])

Answer 1

Вам не нужно проверять каждое значение в последовательности range(p, q + 1).Вам нужно только проверить на p и q.Если это работает для самого низкого и самого высокого числа, это будет работать для всех значений между ними, потому что проблема была уменьшена до простого умножения и сложения.Вам действительно нужно только проверить прогресс program(q), удерживая его ниже s, пока вы не создадите самую короткую программу, которая ставит program(p) на или выше r.

Однако это не так.действительно большая проблема для поиска в первую очередь;Ваш второй пример потребует тестирования 17,6 триллионов возможных состояний;самое короткое решение длиной 44 символа, поэтому при поиске с первого вздоха будут исследованы 2 ** 44 состояния, поэтому, если быть точным, 17 592 186 044 416!Даже при использовании скомпилированного языка программирования, такого как C, потребуется много времени, чтобы найти решение с помощью такого поиска.Вместо этого вы можете просто сгенерировать строку, используя немного математики.

Вы можете рассчитать максимальное количество умножений, необходимое здесь, с помощью int(math.log(s // q, m)), это количество раз, которое вы можете умножить на m, когда начинаете с q и все еще оставаться ниже s.Вы никогда не сможете использовать больше умножений!С math.ceil(math.log(r / p, m)) вы можете найти минимальное количество умножений, которое поместит p в r или выше.Чтобы минимизировать длину программы, выберите меньшее значение из этих двух чисел.

Затем начните добавлять A сложения, перед каждым M умножением.Сделайте это, взяв i в качестве числа M символов, которые должны последовать, затем разделив r и s на m ** i.Они информируют число a дополнений к p и q, что вместе с последующими умножениями приближают его к r и s;разница с текущими значениями p и q позволяет рассчитать минимальное количество символов A, которое можно вставить здесь, чтобы не превышать диапазон [r, s].Для p, округление вверх, для q, округление вниз.

Повторите эту процедуру для каждой последующей операции M, обновляя значения p и q с результатами каждый раз:

import math

def problem3(s):
    a, m, p, q, r, s = map(int, s.split())
    p_mult = math.ceil(math.log(math.ceil(r / p), m))
    q_mult = int(math.log(s // q, m))
    mult = min(p_mult, q_mult)
    program = []
    for i in range(mult, -1, -1):
        p_additions = math.ceil((math.ceil(r / (m ** i)) - p) / a)
        q_additions = ((s // (m ** i)) - q) // a
        additions = min(p_additions, q_additions)
        program += [additions * 'A']
        if i:
            p, q = (p + (additions * a)) * m, (q + (additions * a)) * m
            program += ['M']
    return ''.join(program)

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

>>> problem3("1 2 2 3 10 20")
'AMM'
>>> problem3("8 13 28 91 375383947 679472915")
'AAAAAAMAAMAAAAAAAAAAAMAAAAAMAAAMAAAAMAAAAAAA'