Su problema parece ser uno de esos problemas completos de NP, significa un problema de mochila.
Problema de hacer cambios
Eso fue lo primero que pensé cuando lo vi y descubrí que estaba en Wikipedia. Entonces, ¿cómo se resuelve eso?
- Procesadores de señal digital (DSP): cuando alguien escribe un archivo en una tarjeta SD usando un bus spi, ¿cómo sabe dónde debería estar el comienzo de un nuevo archivo?
- ¿Cuál es el mejor y más fácil algoritmo de búsqueda?
- ¿Qué es lo más importante para las empresas de software: código abierto, proyectos extracurriculares o habilidades algorítmicas (habilidades de programación competitiva)?
- ¿Cuáles son los mejores recursos para aprender R? Tratando de construir mi propio algoritmo de predicción basado en datos anteriores que tengo en archivos csv y que solía ser un desarrollador de Ruby hace un par de años
- ¿Qué algoritmo se usa para la transmisión de video?
Hay dos formas de resolver eso. El problema con esto es que se ejecuta con una necesidad exponencial de tiempo de ejecución o una necesidad exponencial de memoria. En pequeñas cantidades de piezas se puede resolver por fuerza bruta, pruebe todos los casos. Después de eso solo tienes heurística.
La heurística le dará una solución, pero no se garantiza que sea la mejor. Por lo general, hay varias formas de escalar colinas para hacer eso. O simplemente comienzas con las monedas grandes y subes la colina probando las más pequeñas. Esa sería una forma simple de reducir el problema suponiendo que es la mejor manera de acercarse a la solución y luego ver qué tan lejos llega.
Puede hacerlo con un algoritmo de búsqueda A * modificado, por ejemplo. Hay algunos otros, pero ese sería mi primer intento, supongo.
Pero por lo general, adoptará un enfoque de Monte Carlo como un algoritmo evolutivo. Puede usar la Biblioteca de Utilidad de Algoritmo Genético para eso en C para soluciones reales o el DEAP (software) en Python para crear prototipos de su problema.
Ese sería el enfoque más fácil, supongo.
El problema con los algoritmos evolutivos es que es uno que siempre está funcionando, pero con frecuencia no es el más eficiente. Encontrar una buena heurística es el elemento clave de su problema, si desea optimizarlo. Aún así, el algoritmo evolutivo encontrará una buena solución en muy poco tiempo.
Y si quieres llegar a una solución más rápida, prueba el A *. Su heurística será la estimación de cuán buena es la solución que encontró. Para A * siempre tiene que estimar si su próximo paso lo ha acercado a su meta o no. Y ese es el punto de sus conjeturas, de sus heurísticas.
Funcionará más rápido, supongo. Los algoritmos evolutivos son geniales, a menudo son un poco vagos, lo que significa que las personas no pensaron el problema lo suficiente. Es Monte Carlo y simplemente arrojas el algoritmo a todo lo que se te presenta y esperas una respuesta mágica. Pero esa no será la forma más eficiente.
