6

如何在一秒内计算任意 n <= 600的最短加法链（sac） ？

笔记

这是本月的codility编程竞赛。

加法链在数值上非常重要，因为它们是计算 x^n 的最经济的方法（通过连续乘法）。

Knuth's Art of Computer Programming, Volume 2, Seminumerical Algorithms很好地介绍了加法链和一些有趣的属性，但我没有找到任何东西可以满足严格的性能要求。

我尝试过的（剧透警报）

首先，我构建了一个（高度分支的）树（开始 1-> 2 -> ( 3 -> ..., 4 -> ...)），这样对于每个节点 n，从根到 n 的路径是 n 的一个囊。但是对于 >400 的值，运行时间与制作咖啡的时间大致相同。

然后我用那个程序找到了一些有用的属性来减少搜索空间。有了它，我可以在制作咖啡的同时构建多达 600 个的所有解决方案。但是对于 n，我需要计算直到 n 的所有解决方案。不幸的是，codility 也测量了类初始化的运行时间......

由于问题可能是 NP-hard，我最终硬编码了一个查找表。但是既然codility要求构建sac，我不知道他们是否有一个查找表，所以我觉得很脏，像个骗子。因此这个问题。

更新

如果您认为硬编码的完整查找表是可行的方法，您能否给出一个论据，为什么您认为完整计算/部分计算的解决方案/启发式方法不起作用？

4

2 回答 2

4

我刚刚获得了解决这个问题的黄金证书。我不会提供完整的解决方案，因为该问题仍然可以在网站上找到。我将给您一些提示：

  1. 您可以考虑进行深度优先搜索。
  2. 每个 n < 12509 存在一个最小星链
  3. 您需要知道如何修剪您的搜索空间。
  4. 您需要一个良好的下限来确定您正在寻找的链的长度。
  5. 请记住，您只需要一种解决方案，而不是全部。

祝你好运。

于 2012-04-21T13:10:52.807 回答
1

加法链在数值上非常重要，因为它们是计算 x^n 的最经济的方法（通过连续乘法）。

这不是真的。它们并不总是计算 x^n 的最经济的方法。格雷厄姆等。都 证明了：

如果为加法链中的每个步骤分配的成本等于该步骤中数字的乘积，则显示“二进制”加法链以最小化成本。

当我们计算 x^n (mod m) 时，情况会发生巨大变化，这是一种常见的情况，例如在密码学中。

现在，回答你的问题。除了用答案对表格进行硬编码之外，您还可以尝试使用 Brauer 链。

Brauer 链（又名星链）是一个加法链，其中每个新元素由前一个元素和某个元素（可能相同）的总和形成。布劳尔链是 n < 12509 的囊。引用丹尼尔。J.伯恩斯坦：

Brauer 算法通常被称为“从左到右的 2^k-ary 方法”，或者简称为“2^k-ary 方法”。它非常受欢迎。易于实施；为 n 构建链是检查 n 的位的简单问题。它不需要太多的存储空间。

顺便提一句。有人知道 Brauer 链计算的一个不错的 C/C++ 实现吗？我正在部分地使用二进制和布劳尔链对这两种情况进行取幂时间的比较：x^n 和 x^n (mod m)。

于 2013-04-06T21:09:13.933 回答