编辑：澄清问题描述
是否存在解决以下问题的快速算法？
而对于将自然数替换为Z/(2^n Z)的扩展版本，是否也是如此？（在我看来，这个问题过于复杂，无法在同一个地方添加更多的问题。）
问题：
对于给定的自然数集合，例如{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可以用作一种启发式方法。