algorithm - steady - Algoritmo de programación de mejor ajuste
knapsack problem genetic algorithm python (4)
Estoy escribiendo un programa de programación con un problema de programación difícil. Hay varios eventos, cada uno con múltiples horarios de reunión. Necesito encontrar un arreglo de los horarios de reunión de modo que cada horario contenga cualquier evento dado exactamente una vez, usando uno de los múltiples horarios de reunión de cada evento.
Obviamente podría usar la fuerza bruta, pero rara vez es la mejor solución. Supongo que este es un problema informático relativamente básico, que aprenderé una vez que pueda comenzar a tomar clases de informática. Mientras tanto, preferiría cualquier enlace donde pueda leer sobre esto, o incluso un nombre que pueda buscar en Google.
Creo que deberías usar un algoritmo genético porque:
- Es el más adecuado para casos de grandes problemas.
- Se reduce la complejidad del tiempo en el precio de la respuesta incorrecta (No es el mejor)
- Puede especificar restricciones y preferencias fácilmente ajustando los castigos de aptitud para los que no se cumplen.
- Puede especificar un límite de tiempo para la ejecución del programa.
La calidad de la solución depende de cuánto tiempo piense gastar resolviendo el programa.
Definición de Algoritmos Genéticos
Hay varias formas de hacer esto
Un enfoque es hacer programación de restricciones. Es un caso especial de la programación dinámica sugerida por feanor. Es útil usar una biblioteca especializada que pueda hacer los límites y las ramificaciones por usted. (Google para "gecode" o "comet-online" para encontrar bibliotecas)
Si tiene inclinaciones matemáticas, también puede usar la programación entera para resolver el problema. La idea básica aquí es traducir su problema a un conjunto de desigualdades lineales. (Google para "programación de programación entera" para encontrar muchos ejemplos de la vida real y google para "Abacus COIN-OR" para una biblioteca útil)
Supongo que la programación de restricciones es el enfoque más fácil, pero la programación entera es útil si desea incluir variables reales en su problema en algún momento.
La descripción de su problema no está del todo clara, pero si todo lo que está tratando de hacer es encontrar un calendario que no tenga eventos superpuestos, entonces este es un problema simple de emparejamiento bipartito .
Tienes dos conjuntos de nodos: eventos y tiempos. Dibuja un borde de cada evento para cada posible tiempo de reunión. A continuación, puede construir eficientemente la coincidencia (el mayor conjunto posible de bordes entre los nodos) utilizando rutas aumentadas . Esto funciona porque siempre puedes convertir un gráfico bipartito en un gráfico de flujo equivalente.
Un ejemplo de código que hace esto es BIM . Las bibliotecas gráficas estándar como NetworkX y NetworkX también tienen implementaciones de coincidencia bipartita.
Parece que esto podría ser un buen candidato para una solución de programación dinámica , específicamente algo similar al problema de programación de intervalos .
Aquí hay algunas imágenes para el problema de programación de intervalos, que pueden aclarar el concepto. Here hay un buen tutorial sobre programación dinámica en general.