gpt4 book ai didi

algorithm - 最小加法链求幂

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:36:46 28 4
gpt4 key购买 nike

我知道它已被证明是 NP 完全的,没关系。我目前正在用分支定界法解决它,我将初始上限设置为正常二进制平方/乘法算法所采用的乘法次数,它确实给出了正确的答案,但我对运行不满意时间(200 左右的数字可能需要几秒钟)。这是一个 NP 完全问题,我不期待任何壮观的事情;但是通常有一些技巧可以在某种程度上控制实际时间。

在实践中有没有更快的方法来做到这一点?如果有,它们是什么?

最佳答案

这看起来像 Knuth 第 2 卷半数值算法中的第 4.6.3 节“权力的评估”。这涉及相当多的细节以提供各种方法,这些方法看起来比分支定界法快得多,但并非都提供绝对最佳的解决方案。

Knuth 在定理 F 后的讨论中说他使用回溯搜索来证明 l(191) = 11,所以我怀疑你是否会为此找到捷径答案。他将对回溯搜索的解释推迟到第 7.2.2 节,我认为该节尚未发表,尽管在 http://www-cs-faculty.stanford.edu/~uno/programs.html 上有这方面的工作痕迹。 .

关于algorithm - 最小加法链求幂,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7330752/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com