10

编辑：澄清问题的描述

是否有解决以下问题的快速算法？ 而且，也适用于将自然数替换为 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 可以用作启发式方法。

4

2 回答 2

2

我建议将其转换为某种图最短路径算法。

  • 对于每个数字，您计算（并存储）最短的操作路径。从技术上讲，一步就足够了：对于每个数字，您可以存储运算和两个操作数（左右，因为幂运算不可交换），以及权重（“节点”）
  • 最初您注册1的权重为零
  • 每次注册一个新数字时，您都必须使用该数字（所有加法、乘法、幂）和所有已注册的数字生成所有计算。（“边缘”）
    • 计算过滤器：如果计算结果已经注册，您不应该存储它，因为有更简单的方法可以获取该数字
    • 只存储 1 个可交换操作 (1+2=2+1)
    • 预过滤电源操作，因为这甚至可能导致溢出
  • 您必须将此列表排序到最短的总和路径（边缘的权重）。权重=（操作数1的权重）+（操作数2的权重）+（1，也就是操作的权重）
    • 您可以排除所有大于我们必须找到的最大数字的结果数字（例如，如果我们已经找到 100，则可以排除任何大于 20 的数字） - 这可以进行改进，以便您也可以检查操作的成员.
  • 如果您达到了目标数字之一，那么您找到了计算目标数字之一的最短方法，您必须重新生成：
    • 重新计算目标数的最大值
    • 返回当前找到的数字的路径，将它们的权重设置为 0（它们将从现在开始，因为它们的成本已经支付）
    • 重新计算生成列表中操作的权重，因为源操作数权重可能已更改（这会导致最后重新排序） - 在这里您可以排除任一操作数大于新最大值的操作数
  • 如果所有数字都命中，则搜索结束

您可以为每个目标编号使用“反向链接”（操作、左操作数和右操作数）构建表达式。

重点是我们始终关注目标函数，即操作的总数必须尽可能少。为了得到这个，我们总是计算到某个数字的最短路径，然后将该数字（以及路上的所有其他数字）视为给定的数字，然后将我们的搜索扩展到剩余的目标。

从理论上讲，该算法只处理（注册）每个数字一次。应用适当的过滤器会削减不必要的分支，因此不会计算两次（队列中元素的权重除外）

于 2013-04-23T12:48:30.733 回答
2

如果您从排序输入中的最高数字向后工作，检查是否/如何在其构造中使用较小的数字（以及正在引入的数字）怎么办？

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

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
于 2013-04-22T15:35:52.123 回答