Algoritmo de Programación de Mejor Ajuste

Estoy escribiendo un programa de programación con un problema de programación difícil. Hay varios eventos, cada uno con varias horas de reunión. Necesito encontrar un arreglo de los tiempos de reunión tal que cada horario contenga cualquier evento dado exactamente una vez, usando uno de los múltiples tiempos 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 de ciencias de la computación relativamente básico, del que aprenderé una vez que pueda comenzar tomando clases de informática. Mientras tanto, preferiría cualquier enlace donde pudiera leer sobre esto, o incluso un nombre que pudiera buscar en Google.

Author: Betamoo, 2010-04-30
Source

4 answers

Creo que deberías usar el algoritmo genético porque:

  • Es el más adecuado para grandes instancias de problemas.
  • Produce una complejidad de tiempo reducida en el precio de la respuesta inexacta (No la mejor)
  • Puede especificar restricciones y preferencias fácilmente ajustando los castigos de aptitud física para los que no se cumplen.
  • Puede especificar el límite de tiempo para la ejecución del programa.

  • La calidad de la solución depende de cuánto tiempo tiene la intención de pasar resolviendo el programa..

    Definición de Algoritmos genéticos

    Tutorial de Algoritmos genéticos

    Proyecto de programación de clases con GA

 11
Author: Betamoo,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-05-01 12:17:50

Hay varias maneras 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 helful utilizar una biblioteca especializada que puede hacer el límite y ramificación para usted. (Google para "gecode" o "comet-online" para encontrar bibliotecas)

Si está matemáticamente inclinado, también puede usar la programación de enteros para resolver el problema. La idea básica aquí es traducir su problema en un conjunto de lineales desigualdad. (Google para "integer programming scheduling" para encontrar muchos ejemplos de la vida real y Google para "Abacus COIN-OR" para una biblioteca útil)

Mi conjetura es que la programación de restricciones es el enfoque más fácil, pero la programación de enteros es útil si desea incluir variables reales en su problema en algún momento.

 5
Author: nielsle,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-06-09 10:24:44

La descripción del problema no está del todo clara, pero si todo lo que está tratando de hacer es encontrar un programa que no tenga eventos superpuestos, entonces este es un problema sencillo bipartito de coincidencia.

Tiene dos conjuntos de nodos: eventos y tiempos. Dibuja un borde de cada evento a cada hora de reunión posible. 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 convierte un grafo bipartito en un grafo de flujo equivalente.

Un ejemplo de código que hace esto es BIM. Las bibliotecas gráficas estándar como GOBLINy NetworkX también tienen implementaciones de coincidencia bipartitas.

 3
Author: ire_and_curses,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-04-30 17:28:12

Esto suena como 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.

Hay algunos elementos visuales aquí para el problema de programación de intervalos específicamente, lo que puede hacer que el concepto sea más claro. Aquí es un buen tutorial sobre programación dinámica en general.

 2
Author: Feanor,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-04-30 17:46:51