最小的加链求幂 [英] Minimal addition-chain exponentiation

问题描述

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

I know it has been proven NP-complete, and that's ok. I'm currently solving it with branch and bound where I set the initial upper limit at the number of multiplications it would take the normal binary square/multiply algorithm, and it does give the right answers, but I'm not satisfied with the running time (it can take several seconds for numbers around 200). This being an NP-complete problem, I'm not expecting anything spectacular; but there are often tricks to get the Actual Time under control somewhat.

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

Are there faster ways to do this in practice? If so, what are they?

推荐答案

这看起来像Knuth第2卷的半数值算法中的4.6.3节评估能力。 。这在相当详尽的细节中给出了各种方法，这些方法看起来比分支定界要快得多，但是并不能提供绝对最佳的解决方案。

This looks like section 4.6.3 "Evaluation of Powers" in Knuth Vol 2 Seminumerical Algorithms. This goes into considerable detail to give various approaches, which look much quicker than branch and bound but do not all provide the absolutely best solution.

定理后的讨论中，Knuth表示。如果他使用回溯搜索来证明l（191）= 11，那么我怀疑您是否会为此找到捷径。他将回溯搜索的解释推迟到7.2.2节，尽管我在 http://www-cs-faculty.stanford.edu/~uno/programs.html 。

Knuth states in the discussion after Theorem F that he uses backtrack search to prove that l(191) = 11, so I doubt if you will find a short-cut answer for this. He defers explanation of the backtrack search to section 7.2.2, which is I think still unpublished, although there are traces of work on this at http://www-cs-faculty.stanford.edu/~uno/programs.html.

这篇关于最小的加链求幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！