如何使这个广度优先搜索更快？

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个状态，准确地说是17592186044416！即使使用像C这样的编译编程语言，也需要很长很长时间才能找到使用这种搜索的解决方案。相反，您可以使用一点数学来生成字符串。你知道吗

您可以用int(math.log(s // q, m))计算此处所需的最大乘法次数，即当从q开始，并且仍然保持在s以下时，可以用m乘法的次数。你不能再使用乘法了！使用math.ceil(math.log(r / p, m))可以找到将p置于r或以上的最小乘法数。要最小化程序长度，请从这两个数字中选取较低的值。你知道吗

然后，在每次M乘法之前，开始拟合A加法。为此，将i作为要跟随的M字符数，然后将r和s除以m ** i。这些函数告诉对p和q的数字a的加法，加上随后的乘法，使它最接近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'