如何在一秒内计算任意 n <= 600 的最短加法链? [英] How can you compute a shortest addition chain for an arbitrary n &lt;= 600 within one second?

问题描述

您如何计算 最短加法链 (sac)一秒内任​​意 n <= 600?

How can you compute a shortest addition chain (sac) for an arbitrary n <= 600 within one second?

这是本月 codility 的编程竞赛.

This is the programming competition on codility for this month.

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

Addition chains are numerically very important, since they are the most economical way to compute x^n (by consecutive multiplications).

Knuth 的 计算机编程艺术，第 2 卷，半数值算法 很好地介绍了加法链和一些有趣的属性，但我没有找到任何能够满足严格性能要求的东西.

Knuth's Art of Computer Programming, Volume 2, Seminumerical Algorithms has a nice introduction to addition chains and some interesting properties, but I didn't find anything that enabled me to fulfill the strict performance requirements.

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

Firstly, I constructed a (highly branching) tree (with the start 1-> 2 -> ( 3 -> ..., 4 -> ...)) such that for each node n, the path from the root to n is a sac for n. But for values >400, the runtime is about the same as for making a coffee.

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

Then I used that program to find some useful properties for reducing the search space. With that, I'm able to build all solutions up to 600 while making a coffee. But for n, I need to compute all solutions up to n. Unfortunately, codility measures the class initialization's runtime, too...

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

Since the problem is probably NP-hard, I ended up hard-coding a lookup table. But since codility asked to construct the sac, I don't know if they had a lookup table in mind, so I feel dirty and like a cheater. Hence this question.

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

推荐答案

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

I have just got my Golden Certificate for this problem. I will not provide a full solution because the problem is still available on the site.I will instead give you some hints:

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

祝你好运.

这篇关于如何在一秒内计算任意 n <= 600 的最短加法链?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！