最小加链指数运算

Question

最小加链指数运算

7

我知道它已被证明是NP完全问题，这没关系。目前我正在使用分支界限法来解决它，其中我将初始上限设置为正常二进制平方/乘算法所需的乘法次数，它确实给出了正确的答案，但我对运行时间不满意（对于大约200的数字，可能需要几秒钟）。由于这是一个NP完全问题，我并不期望有什么惊人的结果；但通常有一些技巧可以在一定程度上控制实际时间。

在实践中有更快的方法吗？如果有，它们是什么？

- harold

3个回答

1

我来晚了，但在《椭圆曲线与超椭圆曲线密码手册》中，有一章“9.2 固定指数”，其中还讨论了各种加法链。

- Ecir Hana

1

元启发式算法的扩展性更好，包括禁忌搜索、遗传算法、模拟退火等。

有一些免费的书籍和软件可以找到。

- Geoffrey De Smet

1

我不确定原帖作者是否愿意放弃最佳解决方案以换取更快的速度。至少他在问题中没有明确表示。 - static_rtti

3

我并没有明确地说，但它必须是实际上的最小值，而不是某个局部最小值。所以我只是在寻找另一种针对这个问题在实际应用中表现更好的指数时间算法。 - harold

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

这似乎是Knuth Vol 2 Seminumerical Algorithms的第4.6.3节“幂运算评估”。该部分详细介绍了各种方法，这些方法看起来比分支限界法更快，但并不都提供绝对最佳解决方案。

在定理F后的讨论中，Knuth指出他使用回溯搜索证明l(191) = 11，因此我怀疑您是否会找到一个捷径来得到答案。他将回溯搜索的解释推迟到第7.2.2节，我认为该部分尚未公开发表，尽管在http://www-cs-faculty.stanford.edu/~uno/programs.html上有相关工作的痕迹。