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

Question

编辑:澄清问题的描述

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

问题:

对于给定的一组自然数,如{ 7,20,17,100 },所需的算法返回最短的加法序列,多重和权力计算所有给定的数字.每个序列项都是(正确的)等式,符合以下模式:

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

其中<number>是一个自然数,<op>是{+,*,^}之一.

在序列中,<op>的每个操作数应该是其中之一

• 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分钟.

(实际代码, 非常简单的测试)

我目前的(伪)代码:

-- 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