har*_*old 7 algorithm np-complete exponentiation
我知道它已被证明是NP完全的,那没关系.我正在用分支和边界解决它,我将初始上限设置为正常二进制平方/乘法算法的乘法次数,并且它确实给出了正确的答案,但我对运行不满意时间(200左右的数字可能需要几秒钟).这是一个NP完全问题,我不期待任何壮观的事情; 但通常有一些技巧可以让实际时间得到控制.
在实践中有更快的方法吗？如果是这样,他们是什么？
这看起来像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上有相关工作的痕迹.
| 归档时间： |
|
| 查看次数： |
1946 次 |
| 最近记录： |