La cadena de adición más corta para llegar a $100$

Question

Un cadena de adición para un número entero $n$ es cualquier lista finita de enteros donde la primera entrada es 1 y la última es $n$ y donde cada entrada es la suma de dos entradas (posiblemente no consecutivas) que aparecen antes en la lista.

Estaba leyendo este y encontró la cadena de adición más corta para muchos números. Sin embargo, me preguntaba si había un método de búsqueda más elegante, no exhaustivo, para encontrar la cadena de adición más corta para el número $100$ ? Si se me pidiera encontrar la cadena de adición más corta para $100$ ¿hay alguna forma de hacerlo manualmente sin enumerar todas las posibilidades?

Answer 1

Por lo que he leído, no conocemos una forma rápida de encontrar la cadena de adición más corta para un determinado $n$ . En resumen, el problema es que es difícil saber si estás progresando: si tienes parte de una lista de adición, ¿se puede saber si está cerca de ser la lista de adición más corta posible para $n$ ?

Si pudiéramos saber si una lista parcial está cerca de ser la lista más corta para $n$ La búsqueda de los productos de la Unión Europea, que es normalmente exhaustiva, es más eficaz. Por ejemplo, se podría esperar encontrar la lista de suma más corta para $n$ adivinando dos factores $a+b=n$ encontrar las listas más cortas para $a$ y $b$ y luego unir esas listas. Eso agilizaría la búsqueda (es un ejemplo de la propiedad de subestructura óptima; algunos problemas eficientemente resolubles tienen esta propiedad). Pero, por desgracia, las listas de adición no funcionan así, y en general no hemos encontrado cualquier manera de medir si nuestra solución parcial está cerca de ser la óptima.

En cambio, lo que tenemos actualmente son algoritmos aproximados relativamente rápidos para encontrar soluciones que puede estar cerca de la longitud más corta.