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

Question

如何计算 shortest addition chain (sac)一秒内任​​意 n <= 600？

注意事项

这是 codility 上的编程竞赛这个月。

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

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

我尝试过的(剧透警告)

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

然后我用那个程序找到 some useful properties for reducing the search space 。有了它，我可以在煮咖啡的同时构建多达 600 个解决方案。但是对于 n，我需要计算直到 n 的所有解决方案。不幸的是，codility 也衡量类初始化的运行时间......

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

更新

如果您认为硬编码的完整查找表是可行的方法，您能否说明为什么您认为完整计算/部分计算的解决方案/启发式方法行不通？

Answer 1

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

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

祝你好运。