algorithm - 优化算术表达式序列的快速算法

Question

编辑:澄清问题的描述

是否有解决以下问题的快速算法？并且，也是针对这个问题的扩展版本将自然数替换为 Z/(2^n Z)？(这个问题太复杂了，无法在一个地方添加更多问题，IMO。)

问题:

对于一组给定的自然数，如 {7, 20, 17, 100}，需要算法返回加法、乘法和幂计算的最短序列所有给定的数字。序列中的每一项都是(正确的)等式，符合以下模式:

<number> = <number> <op> <number>

其中 是一个自然数， 是{+, *, ^}之一。

在序列中， 的每个操作数应该是

• 1
• 已经出现在等号左边的数。

示例:

Input: {7, 20, 17, 100}
Output:
2 = 1 + 1
3 = 1 + 2
6 = 2 * 3
7 = 1 + 6
10 = 3 + 7
17 = 7 + 10
20 = 2 * 10
100 = 10 ^ 2

---

我用 Haskell 编写了回溯算法。它适用于像上面这样的小输入，但我真正的查询是在 [0,255] 中随机分布约 30 个数字。对于真正的查询，以下代码在我的电脑上需要 2~10 分钟。

( Actual code , very simple test )

我当前的(伪)代码:

-- generate set of sets required to compute n.
-- operater (+) on set is set union.
requiredNumbers 0 = { {} }
requiredNumbers 1 = { {} }
requiredNumbers n =
      { {j, k} | j^k == n, j >= 2, k >= 2 }
    + { {j, k} | j*k == n, j >= 2, k >= 2 }
    + { {j, k} | j+k == n, j >= 1, k >= 1 }

-- remember the smallest set of "computed" number
bestSet := {i | 1 <= i <= largeNumber}

-- backtracking algorithm
-- from: input
-- to:   accumulator of "already computed" number
closure from to =
    if (from is empty)
        if (|bestSet| > |to|)
            bestSet := to
            return
    else if (|from| + |to| >= |bestSet|)
        -- cut branch
        return
    else
        m := min(from)
        from' := deleteMin(from)
        foreach (req in (requiredNumbers m))
            closure (from' + (req - to)) (to + {m}) 

-- recoverEquation is a function converts set of number to set of equation.
-- it can be done easily.
output = recoverEquation (closure input {})

补充说明:

像这样的回答

• 没有快速算法，因为...
• 有一个启发式算法，它是...

也欢迎。现在感觉没有快速准确的算法...

我认为，答案 #1 可以用作启发式。

Answer 1

如果您从已排序输入中的最高数字开始逆向工作，检查是否/如何在其构造中使用较小的数字(以及正在引入的数字)会怎么样？

例如，虽然这可能不能保证最短的序列...

input: {7, 20, 17, 100}

(100) = (20) * 5 => 
(7) = 5 + 2      => 
(17) = 10 + (7)  =>
(20) = 10 * 2    =>
10 = 5 * 2       =>
5 = 3 + 2        =>
3 = 2 + 1        =>
2 = 1 + 1