exponenciación mínima de la cadena de adición

Question

Sé que se ha demostrado que es NP-completo, y está bien. Actualmente estoy resolviéndolo con branch y bound donde establezco el límite superior inicial en el número de multiplicaciones que tomaría el algoritmo binario cuadrado/multiplicación normal, y da las respuestas correctas, pero no estoy satisfecho con la ejecución tiempo (puede tomar varios segundos para números alrededor de 200). Como es un problema NP completo, no espero nada espectacular; pero a menudo hay trucos para controlar el Tiempo Real.

¿Hay formas más rápidas de hacer esto en la práctica? Si es así, ¿Que son?

Answer 1

Esto se parece a la sección 4.6.3 "Evaluación de poderes" en Knuth Vol 2 Seminumerical Algorithms. Esto entra en detalles considerables para dar varios enfoques, que se ven mucho más rápido que las ramificaciones y los límites, pero que no proporcionan la mejor solución.

Knuth afirma en la discusión posterior al teorema F que utiliza la búsqueda de retroceso para demostrar que l (191) = 11, por lo que dudo si encontrará una respuesta de atajo para esto. Él difiere la explicación de la búsqueda de retroceso a la sección 7.2.2, que es todavía inédita, aunque hay rastros de trabajo en esto en http://www-cs-faculty.stanford.edu/~uno/programs.html.

Answer 2

Metaheuristics algoritmos escalarán mucho mejor. Incluyen Búsqueda Tabú, Los algoritmos genéticos, recocido simulado , ...

Hay un par de freebooks y libre software por ahí.