Минимальное сложение-возведение в степень

Question

Я знаю, что он был доказан NP-полным, и это нормально. В настоящее время я решаю это с помощью ответвления и границы, где я устанавливаю начальный верхний предел на количество умножений, которое потребовалось бы обычному алгоритму двоичного квадрата / умножения, и оно дает правильные ответы, но я не удовлетворен работой время (это может занять несколько секунд для чисел около 200). Это проблема NP-полная, я не ожидаю ничего впечатляющего; но часто есть хитрости, чтобы хоть немного контролировать фактическое время.

Есть ли более быстрые способы сделать это на практике? Если да, то что они?

Answer 1

Это похоже на раздел 4.6.3 «Оценка полномочий» в полунатурных алгоритмах Knuth Vol 2. В нем подробно рассматриваются различные подходы, которые выглядят намного быстрее, чем ветвление и связывание, но не все обеспечивают абсолютно лучшее решение.

Кнут утверждает в обсуждении после теоремы F, что он использует поиск в обратном направлении, чтобы доказать, что l (191) = 11, поэтому я сомневаюсь, что вы найдете краткий ответ для этого. Он отложил объяснение поиска в обратном направлении в разделе 7.2.2, который, я думаю, все еще не опубликован, хотя есть следы работы над этим в http://www -cs-faculty.stanford.edu / ~ uno / Programs.html .

Answer 2

Я опаздываю на вечеринку, но в Справочнике по криптографии с эллиптическими и гиперэллиптическими кривыми есть глава "9.2 Фиксированный показатель", в которой также обсуждаются цепочки сложений различных видов.

Answer 3

Метаэвристика алгоритмы будут масштабироваться намного лучше.Они включают Табу поиск , Генетические алгоритмы , Имитация отжига , ...

Есть пара бесплатно книги и бесплатное программное обеспечение там.