Inteligencia Artificial - Algoritmo o técnica para aplicar a este problema

   
Vista:

Algoritmo o técnica para aplicar a este problema

Publicado por Juan (1 intervención) el 31/10/2011 12:12:46
Hola a todos, les realizo la pregunta porque seguro que me saben responder que técnica es la más apropiada, para que pueda buscar información sobre el tema e implementarla.

El problema se puede simplificar a lo siguiente que me suena a "problema clásico".

Como si fuera una agenda o un planificador, tendremos una serie de elementos que insertar, con un peso estimado a priori (como estimar este peso es otro tema porque también deberé predecirlo o calcularlo), con ese peso y teniendo una serie de huecos debería rellenarlos.

El problema se complicará y se debe tener en cuenta que:
1) Pueden hacer restricciones, por ejemplo si rellenas el hueco tal con esta tarea no puedes poner ciertas tareas cerca o debes penalizar que estén cerca en el tiempo.
2) El número de huecos que utilizan las tareas no es el mismo (puede requerir un hueco o varios cada tarea)
3) Seguramente no debemos dejar ningún hueco libre.
4) Puede que el usuario manualmente obligue a que ciertos huecos tengan unas determinadas tareas.
5) Podria darse el caso de tener un feedback del usuario que nos indicara el grado de satisfacción "global" sobre las asignaciones realizadas, o simplemente que lo rechazase y pidiera una asignación distinta sin indicar el motivo.


¿Que tipo de algoritmo/s sería los adecuados para que me empape sobre el tema en concreto?

Entiendo que quizás el punto 5 complique mucho lo anterior, así que una respuesta del tipo "aplicaría tal técnica para resolverlo todo salvo el punto 5 que para tener un aprendizaje/evaluación/feedback cambiaría por esta otra técnica" me sería igualmente muy útil.

Muchas gracias por vuestra atención.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Borja

Algoritmo o técnica para aplicar a este problema

Publicado por Borja (1 intervención) el 05/06/2014 22:57:55
Yo tuve que hacer un proyecto donde se asignaban horarios en un calendario semanal para X asignaturas con Y aulas disponibles. Cada aula podía ocupar ciertas horas seguidas y necesitaba un total de horas semanales, ademas habían también restricciones tipo no se puede hacer una asignatura antes que otra, o las que puedas imaginar.

Lo que nos planteas me ha parecido un típico problema de satisfacción de restricciones, igual que el que he comentado arriba y típicamente con backtracking. El nivel de optimización del backtracking lo pones tu, nosotros usamos backtracking con forward checking.

En cuanto al punto 5, nosotros también lo contemplábamos, nos bastó con dejar que el usuario pidiese otro horario con un botón y volver a correr el algoritmo pero desordenando el orden de asignación de las asignaturas. También puede hacerse generando un nueva restricción que compruebe que la solución nueva no existe en las soluciones ya generadas. Lo del aleatorio es mas rápido y raramente coinciden dos soluciones (el numero de asignaturas o slots era muy grande).
Espero que te haya sido de ayuda.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar