我知道它已被证明是 NP 完全的，这没关系。我目前正在用分支和界限解决它，我将初始上限设置为乘法次数，它将采用正常的二进制平方/乘法算法，它确实给出了正确的答案，但我对运行不满意时间（200 左右的数字可能需要几秒钟）。这是一个 NP 完全问题，我并不期待任何壮观的事情。但通常有一些技巧可以在一定程度上控制实际时间。
在实践中是否有更快的方法来做到这一点？如果是这样，它们是什么？
问问题
2475 次
3 回答
6
这看起来像 Knuth Vol 2 Seminumerical Algorithms 中的第 4.6.3 节“权力评估”。这非常详细地给出了各种方法，这些方法看起来比分支和绑定要快得多，但并非都提供绝对最佳的解决方案。
Knuth 在定理 F 之后的讨论中表示，他使用回溯搜索来证明 l(191) = 11，所以我怀疑你是否会找到一个捷径。他将回溯搜索的解释推迟到第 7.2.2 节，尽管在http://www-cs-faculty.stanford.edu/~uno/programs.html上有这方面的工作痕迹，但我认为该节仍未发表。
于 2011-09-07T17:44:50.050 回答
1
我迟到了，但在椭圆和超椭圆曲线密码学手册中有一章“9.2 固定指数”也讨论了各种加法链。
于 2019-05-28T13:57:20.230 回答