Ver la versión completa : Reto para programadores by Archer
Muy buenas, pues veréis tengo un reto para ver si alguien da con la clave de este problema que tengo... os explico:
Yo trabajo en una fabrica en el departamento de fabricación, somos 6 personas en este departamento y hay 3 maquinas, asi que en cada maquina tienen que haber 2 personas...
Para no estar todos los dias las mismas parejas y en la misma maquina se va cambiando de maquina y de pareja, hasta la fecha (10 años) nadie a dado con un horario que cumpla todas las reglas necesarias... Alguien se atreve a intentarlo? ya os digo que amano es imposible hacerlo por eso lo pogo en programación... os dejo aquí el problema:
************************************************** ****************************************
- Somos 6 personas llamadas ( A, V, D, I, C, M ) las cuales tienen que coincidir todas con todas.
- Hay 3 maquinas a las cuales cada semana va una de las parejas a cada makina. las maquinas se llaman ( 11, 12 y 13 )
Parejas que salen:
AV AI AD AC AM VI VD VC VM ID IC MI DC DM CM
Reglas:
Ninguna persona puede estar en mas de una maquina la misma semana.
Ninguna pareja se puede repetir 2 semanas seguidas
Ninguna persona puede estar 2 semanas seguidas en la misma maquina
Ninguna pareja puede estar mas de 1 semana en una misma maquina
************************************************** ********************************************
Un saludo y suerte!!! quien sera el ganador?
Para el que lo consiga estaría dispuesto a enviarle un cable EXT a USB como el que le hice a joanvr (puedes subir una foto joanvr?)
The_Punisher
28/01/2008, 23:54
Juraria que a si a ojo hay sucesos incompatibles, con lo cual nunca conseguiras la solucion que buscas, espero estar equivocado.
Saludos ;)
Esto en Prolog se resuelve en 10 minutillos ya que está pensado para resolver este tipo de problemas, pero el caso es que no aprendí a usarlo en su asignatura correspondiente.
¿Se puede usar heurística? Voy a probar con un algoritmo genético.
Puck2099
29/01/2008, 00:18
Bueno, pues yo creo que lo he resuelto a mano aprovechando un descansillo de estudiar arquitectura de computadores :P
11 12 13
-- -- --
AV DI CM
IM VC AD
DV AI CM
AC VM DI
IV DC AM
DM AV CI
VI CM AD
DC AI VM
IM DV AC
CV AM DI
IM DC AV
AD VM CI
CV AI DM
AM DV CI
VI AC DM
EDITO: Vaya, acabo de darme cuenta de que no es cíclico... bueno, pues que lo intente alguien con un algoritmo de IA que tengo que seguir estudiando :(
¿Se puede usar heurística? Voy a probar con un algoritmo genético.
friki :D
Esto no se estudia en alguna asignatura relacionada con planificacion de proyectos?
Aiken
Antes de ponerme a hacer un algoritmo genético... he lanzado una búsqueda aleatoria sobre 10 millones de posibilidades y no ha encontrado ninguna que cumpla todos los requisitos; por lo que empiezo a dudar si existe la solución.
La mejor que me ha encontrado ha sido la siguiente:
11 12 13
-- -- --
MV IA DC
CI VD MA
AV MC ID
MI AD VC
AC VI DM
Donde si tenemos en cuenta que sería cíclico, la persona D tendría que repetir la maquina 13 en la primera y la última semana.
Mañana probaré con el genético y aumentando el número de semanas del ciclo.
< - >
friki :D
Esto no se estudia en alguna asignatura relacionada con planificacion de proyectos?
Aiken
Se estudia en optativas frikis impartidas por profesores frikis :). En mi caso la asignatura era "Teoría de juegos y simulación".
pepe_faruk
29/01/2008, 06:29
11 12 13
== == ==
AV DI CM
DM CV IA
CA IM DV
IV DC MA
DA MV CI
CM DI VA
DA VM IC
VC IA DM
IM DV AC
DC AM VI
VA DI MC *
DC MA IV
MV IC DA
IA DM CV
DV CA MI
MC DI AV
DV AC IM
AM IV DC
IC DA VM
DM VC AI
AV DI CM <- Vuelta a empezar
Las madrugadas de trabajo dejan mucho tiempo para pensar :D
<->
* Esta combinación is igual a la primera pero si se repitiera el ciclo desde esta habría trabajadores que apenas tocarían en una máquina (p.e. "A" estaría 4 semanas en "11" otras 4 en "13" pero sólo 2 en "12"). La forma final es más homogénea en el reparto aunque el ciclo es más largo.
Espero que te sirva de ayuda
romeroca
29/01/2008, 12:25
Interesante.
Esto me recuerda a los problemas de una asignatura que tuve "Teoría de autómatas y lenguajes formales" donde se estudian problemas de este estilo (calculabilidad y posibles soluciones).
Me ha picado a ver si le puedo echar un vistazo.
QUE CABR... ERES :D
anibarro
29/01/2008, 12:38
Espero que no hayan estado los 10 años intentandolo, porque si no les veo adorando una foto de pepe_faruk xD
DMusta1ne
29/01/2008, 14:04
Esto demuestra el dicho de que si le das un problema a 10 programadores, te darán 10 soluciones distintas y a su vez válidas xDDD
11 12 13
== == ==
AV DI CM
DM CV IA
CA IM DV
IV DC MA
DA MV CI
CM DI VA
DA VM IC
VC IA DM
IM DV AC
DC AM VI
VA DI MC *
DC MA IV
MV IC DA
IA DM CV
DV CA MI
MC DI AV
DV AC IM
AM IV DC
IC DA VM
DM VC AI
AV DI CM <- Vuelta a empezar
Creo que no hemos entendido de igual manera el siguiente requisito:
"Ninguna pareja puede estar mas de 1 semana en una misma maquina"
anibarro
29/01/2008, 18:47
Creo que no hemos entendido de igual manera el siguiente requisito:
"Ninguna pareja puede estar mas de 1 semana en una misma maquina"
Se supone que se refiere a "mas de una semana seguida", si no necesitarias infinitas parejas distintas para que una pareja nunca repitiese en la misma maquina :S Si haces un ciclo, por webs va a tener q repetir una pareja la misma maquina
WiterN esta en lo cierto, no se puede repetir la misma pareja en una maquina, en principio hay 15 posibiliddes distintas para cada maquina... el problema es ordenarlas para que todas coincidan...
Yo estoy probando con las posibles permutaciones... me puesto a guardar todas las combinaciones posibles sin repetirse y me he quedado sin Disco duro... 500gb he echo el calculo y para guardar todas las combinaciones para 15 elemento eran unos 1200Gb asi que tengo que buscar otro metodo que no las guarde jejejej :S
exactamente para un conjunto de 15 elementos sale un total de 1307674368000 ( unos 130000 millones :S)combinaciones diferentes sin repetirse ningun elemento dentro del conjunto, simplemente cambiando el orden.
Creeis que con esa cantidad de posibilidades no hay ninguna que encaje ?
:S
< - >
Se supone que se refiere a "mas de una semana seguida", si no necesitarias infinitas parejas distintas para que una pareja nunca repitiese en la misma maquina :S Si haces un ciclo, por webs va a tener q repetir una pareja la misma maquina
Exactamente tiene que ser un ciclo de 15 semanas ya que hay 15 parejas distintas... y esas 15 parejas tienen que pasar solo 1 vez por cada maquina en 1 ciclo :D
< - >
Bueno, pues yo creo que lo he resuelto a mano aprovechando un descansillo de estudiar arquitectura de computadores :P
11 12 13
-- -- --
AV DI CM
IM VC AD
DV AI CM
AC VM DI
IV DC AM
DM AV CI
VI CM AD
DC AI VM
IM DV AC
CV AM DI
IM DC AV
AD VM CI
CV AI DM
AM DV CI
VI AC DM
EDITO: Vaya, acabo de darme cuenta de que no es cíclico... bueno, pues que lo intente alguien con un algoritmo de IA que tengo que seguir estudiando :(
Creo que no cumple las reglas :S
Puck2099
29/01/2008, 22:31
Creo que no cumple las reglas :S
La única que no cumple es que no se pueda concatenar la última con la primera, ¿no?
Es que no entiendo ninguna regla que incumpla de las marcadas en negrita...
EDITO: Vale, ya lo entiendo, pero creo que es imposible encontrar lo que buscas...
La única que no cumple es que no se pueda concatenar la última con la primera, ¿no?
Es que no entiendo ninguna regla que incumpla de las marcadas en negrita...
EDITO: Vale, ya lo entiendo, pero creo que es imposible encontrar lo que buscas...
También creiamos imposible llegar a la luna... xD
Puck2099
29/01/2008, 23:24
También creiamos imposible llegar a la luna... xD
Bueno, pero eso todo el mundo sabe que fue un montaje ;)
Entonces, por lo que entiendo, el ciclo tiene que ser de 15 semanas sí o sí. Aunque es tarde a ver si me da tiempo a echar a correr el genético. Hasta ahora los he utilizado con problemas que eran resolubles por otros métodos. Tengo ganas de verlo funcionar con un problema de verdad. Sólo espero que el problema al final tenga alguna solución. :rolleyes:
¿Por cierto, nunca cogéis vacaciones? ;)
Si exactamente tiene que pasar un ciclo de 15 semanas y esas 15 parejas solo una vez por maquina, primero deberíamos comprobar si esta regla: Ninguna persona puede estar 2 semanas seguidas en la misma maquina se cumple para una maquina. Si se cumpliese (lo dudo profundamente) se podría resolver el gran enigma. Si no se cumple no cal que os estéis matando las neuronas.
Un saludo.
Si exactamente tiene que pasar un ciclo de 15 semanas y esas 15 parejas solo una vez por maquina, primero deberíamos comprobar si esta regla: Ninguna persona puede estar 2 semanas seguidas en la misma maquina se cumple para una maquina. Si se cumpliese (lo dudo profundamente) se podría resolver el gran enigma. Si no se cumple no cal que os estéis matando las neuronas.
Un saludo.
Si que se cumple para una maquina y es bastante facil...
Maquina 11: AV ID CM VI AD VC AM VD AC VM IC DM AI DC MI
Y como esta combinacion deben haber cientos que cumplan esa regla. :)
Vamos chicos que nos vamos acercando!!!
Pues dejado toda la noche al genético buscando la solución y no he conseguido nada suficientemente aproximado. Intentaré optimizarlo un poco, pero ya estoy empezando a pensar en cómo encontrar la demostración de que el problema no tiene solución.
Para el que le interese el tema de los AG, os dejo el código fuente y los binarios. Para ejecutarlo simplemente usad el "run.bat" (renombrarlo a .sh y dadle permisos de ejecución para Linux). Tendréis que tener "java" en el PATH.
Es código está un poco guarro y bastante poco documentado, fruto de una improvisación en dos ratos. Intentaré optimizarlo y ordenarlo un poco.
EDITO: ¿¿No tengo permiso para adjuntar archivos?? Al menos el el modo "Editar Mensaje".
Si le doy a mensaje nuevo entonces ya sí.
Por cierto, se supone que el problema se resuelve cuando la puntuación llega a cero. Si después de las 5000 generaciones no se ha alcanzado, se muestra el que menos puntuación alcanzó en todo el momento.
Bueno yo e pensado una manera para hacerlo a ver que sale, esta noche la programare a ver... se trata de hacer una makina fija que cumpla todas las reglas para una makina, es decir que ninguna persona este dos semanas seguidas y que ninguna pareja este mas de una vez en esa makina, a partir de ahi que el programa genere las 130000 millones de permutaciones para la segunda makina y la tercera se rellena con la unica opcion que le queda osea la unica pareja que quede libre, y cada vez que se genere una permutacion que compruebe las reglas a ver si hay alguna que las cumple :) lo mismo se tira una semana para comprobarlo xD
A ver si hay suerte :)
Estopero
30/01/2008, 17:11
con backtracking y un procesador muy potente seguro que algun dia se llega a una solucion xDDDDD
con backtracking y un procesador muy potente seguro que algun dia se llega a una solucion xDDDDD
Prolog. Rápido, fácil, cómodo, y no chupa mucho procesador para el BT.
Prolog. Rápido, fácil, cómodo, y no chupa mucho procesador para el BT.
Mucho que dices, hazlo tú.
Archer, tengo un programa en prolog que hace eso mismo, pero no me acaba de cuadrar, no me queda un horario bonito. Aclara bien las condiciones que has puesto. Por ejemplo, este horario porque podria estar mal? En teoria cumple todas las condiciones que he entendido.
?- turnos(40).
m1: (a,d) m2: (c,n) m3: (v,i)
m1: (v,c) m2: (a,i) m3: (d,n)
m1: (a,n) m2: (v,d) m3: (i,c)
m1: (v,i) m2: (a,c) m3: (d,n)
m1: (a,n) m2: (i,d) m3: (v,c)
m1: (v,i) m2: (c,n) m3: (a,d)
m1: (a,c) m2: (v,d) m3: (i,n)
m1: (v,i) m2: (a,n) m3: (d,c)
m1: (a,c) m2: (i,d) m3: (v,n)
m1: (v,d) m2: (a,n) m3: (i,c)
m1: (a,c) m2: (v,i) m3: (d,n)
m1: (v,d) m2: (c,n) m3: (a,i)
m1: (a,n) m2: (v,i) m3: (d,c)
m1: (v,d) m2: (a,c) m3: (i,n)
m1: (i,c) m2: (v,n) m3: (a,d)
m1: (a,n) m2: (d,c) m3: (v,i)
m1: (v,d) m2: (a,i) m3: (c,n)
m1: (a,c) m2: (v,n) m3: (i,d)
m1: (v,i) m2: (a,d) m3: (c,n)
m1: (a,c) m2: (i,n) m3: (v,d)
m1: (v,i) m2: (d,c) m3: (a,n)
m1: (d,n) m2: (a,v) m3: (i,c)
m1: (v,c) m2: (i,d) m3: (a,n)
m1: (i,n) m2: (a,v) m3: (d,c)
m1: (a,c) m2: (d,n) m3: (v,i)
m1: (v,d) m2: (i,c) m3: (a,n)
m1: (i,n) m2: (a,d) m3: (v,c)
m1: (d,c) m2: (v,i) m3: (a,n)
m1: (v,n) m2: (a,d) m3: (i,c)
m1: (i,d) m2: (v,c) m3: (a,n)
m1: (v,n) m2: (a,i) m3: (d,c)
m1: (i,d) m2: (c,n) m3: (a,v)
m1: (v,c) m2: (a,d) m3: (i,n)
m1: (a,n) m2: (i,c) m3: (v,d)
m1: (v,i) m2: (d,n) m3: (a,c)
m1: (a,n) m2: (v,c) m3: (i,d)
m1: (v,d) m2: (i,n) m3: (a,c)
m1: (i,c) m2: (a,v) m3: (d,n)
m1: (v,n) m2: (i,d) m3: (a,c)
m1: (i,c) m2: (a,n) m3: (v,d)
DONE
Yes
?-
EDIT: Si soy el ganador, dimelo que publico codigo :p
< - >
He añadido una nueva condición: No se puede repetir la misma pareja en una maquina NUNCA. He intentado sacar 15 turnos seguidos, pero PROLOG ha probado todas las combinaciones posibles de maquinas y personas y es insatisfactible. El máximo número de turnos que me da resultados son con 13 turnos. Aqui unos ejemplos:
m1: (d,c) m2: (a,v) m3: (i,m)
m1: (v,m) m2: (i,d) m3: (a,c)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (i,c) m2: (v,d) m3: (a,m)
m1: (d,m) m2: (a,i) m3: (v,c)
m1: (a,c) m2: (v,m) m3: (i,d)
m1: (i,m) m2: (d,c) m3: (a,v)
m1: (v,d) m2: (a,m) m3: (i,c)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (i,d) m2: (a,c) m3: (v,m)
m1: (v,c) m2: (d,m) m3: (a,i)
m1: (a,m) m2: (i,c) m3: (v,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (d,c) m2: (a,i) m3: (v,m)
m1: (i,m) m2: (v,d) m3: (a,c)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (v,c) m2: (i,d) m3: (a,m)
m1: (d,m) m2: (a,v) m3: (i,c)
m1: (a,c) m2: (i,m) m3: (v,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (a,m) m2: (v,c) m3: (i,d)
m1: (i,c) m2: (d,m) m3: (a,v)
m1: (v,d) m2: (a,c) m3: (i,m)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (i,d) m2: (a,m) m3: (v,c)
m1: (v,m) m2: (d,c) m3: (a,i)
m1: (d,c) m2: (a,i) m3: (v,m)
m1: (i,m) m2: (v,d) m3: (a,c)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (v,c) m2: (i,d) m3: (a,m)
m1: (d,m) m2: (a,v) m3: (i,c)
m1: (a,c) m2: (i,m) m3: (v,d)
m1: (v,m) m2: (d,c) m3: (a,i)
m1: (i,d) m2: (a,m) m3: (v,c)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (v,d) m2: (a,c) m3: (i,m)
m1: (i,c) m2: (d,m) m3: (a,v)
m1: (a,m) m2: (v,c) m3: (i,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (d,m) m2: (a,v) m3: (i,c)
m1: (v,c) m2: (i,d) m3: (a,m)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (i,m) m2: (v,d) m3: (a,c)
m1: (d,c) m2: (a,i) m3: (v,m)
m1: (a,m) m2: (v,c) m3: (i,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (a,c) m2: (i,m) m3: (v,d)
m1: (v,m) m2: (d,c) m3: (a,i)
m1: (i,d) m2: (a,m) m3: (v,c)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (v,d) m2: (a,c) m3: (i,m)
m1: (i,c) m2: (d,m) m3: (a,v)
Mucho que dices, hazlo tú.
Archer, tengo un programa en prolog que hace eso mismo, pero no me acaba de cuadrar, no me queda un horario bonito. Aclara bien las condiciones que has puesto. Por ejemplo, este horario porque podria estar mal? En teoria cumple todas las condiciones que he entendido.
?- turnos(40).
m1: (a,d) m2: (c,n) m3: (v,i)
m1: (v,c) m2: (a,i) m3: (d,n)
m1: (a,n) m2: (v,d) m3: (i,c)
m1: (v,i) m2: (a,c) m3: (d,n)
m1: (a,n) m2: (i,d) m3: (v,c)
m1: (v,i) m2: (c,n) m3: (a,d)
m1: (a,c) m2: (v,d) m3: (i,n)
m1: (v,i) m2: (a,n) m3: (d,c)
m1: (a,c) m2: (i,d) m3: (v,n)
m1: (v,d) m2: (a,n) m3: (i,c)
m1: (a,c) m2: (v,i) m3: (d,n)
m1: (v,d) m2: (c,n) m3: (a,i)
m1: (a,n) m2: (v,i) m3: (d,c)
m1: (v,d) m2: (a,c) m3: (i,n)
m1: (i,c) m2: (v,n) m3: (a,d)
m1: (a,n) m2: (d,c) m3: (v,i)
m1: (v,d) m2: (a,i) m3: (c,n)
m1: (a,c) m2: (v,n) m3: (i,d)
m1: (v,i) m2: (a,d) m3: (c,n)
m1: (a,c) m2: (i,n) m3: (v,d)
m1: (v,i) m2: (d,c) m3: (a,n)
m1: (d,n) m2: (a,v) m3: (i,c)
m1: (v,c) m2: (i,d) m3: (a,n)
m1: (i,n) m2: (a,v) m3: (d,c)
m1: (a,c) m2: (d,n) m3: (v,i)
m1: (v,d) m2: (i,c) m3: (a,n)
m1: (i,n) m2: (a,d) m3: (v,c)
m1: (d,c) m2: (v,i) m3: (a,n)
m1: (v,n) m2: (a,d) m3: (i,c)
m1: (i,d) m2: (v,c) m3: (a,n)
m1: (v,n) m2: (a,i) m3: (d,c)
m1: (i,d) m2: (c,n) m3: (a,v)
m1: (v,c) m2: (a,d) m3: (i,n)
m1: (a,n) m2: (i,c) m3: (v,d)
m1: (v,i) m2: (d,n) m3: (a,c)
m1: (a,n) m2: (v,c) m3: (i,d)
m1: (v,d) m2: (i,n) m3: (a,c)
m1: (i,c) m2: (a,v) m3: (d,n)
m1: (v,n) m2: (i,d) m3: (a,c)
m1: (i,c) m2: (a,n) m3: (v,d)
DONE
Yes
?-
EDIT: Si soy el ganador, dimelo que publico codigo :p
< - >
He añadido una nueva condición: No se puede repetir la misma pareja en una maquina NUNCA. He intentado sacar 15 turnos seguidos, pero PROLOG ha probado todas las combinaciones posibles de maquinas y personas y es insatisfactible. El máximo número de turnos que me da resultados son con 13 turnos. Aqui unos ejemplos:
m1: (d,c) m2: (a,v) m3: (i,m)
m1: (v,m) m2: (i,d) m3: (a,c)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (i,c) m2: (v,d) m3: (a,m)
m1: (d,m) m2: (a,i) m3: (v,c)
m1: (a,c) m2: (v,m) m3: (i,d)
m1: (i,m) m2: (d,c) m3: (a,v)
m1: (v,d) m2: (a,m) m3: (i,c)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (i,d) m2: (a,c) m3: (v,m)
m1: (v,c) m2: (d,m) m3: (a,i)
m1: (a,m) m2: (i,c) m3: (v,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (d,c) m2: (a,i) m3: (v,m)
m1: (i,m) m2: (v,d) m3: (a,c)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (v,c) m2: (i,d) m3: (a,m)
m1: (d,m) m2: (a,v) m3: (i,c)
m1: (a,c) m2: (i,m) m3: (v,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (a,m) m2: (v,c) m3: (i,d)
m1: (i,c) m2: (d,m) m3: (a,v)
m1: (v,d) m2: (a,c) m3: (i,m)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (i,d) m2: (a,m) m3: (v,c)
m1: (v,m) m2: (d,c) m3: (a,i)
m1: (d,c) m2: (a,i) m3: (v,m)
m1: (i,m) m2: (v,d) m3: (a,c)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (v,c) m2: (i,d) m3: (a,m)
m1: (d,m) m2: (a,v) m3: (i,c)
m1: (a,c) m2: (i,m) m3: (v,d)
m1: (v,m) m2: (d,c) m3: (a,i)
m1: (i,d) m2: (a,m) m3: (v,c)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (v,d) m2: (a,c) m3: (i,m)
m1: (i,c) m2: (d,m) m3: (a,v)
m1: (a,m) m2: (v,c) m3: (i,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (d,m) m2: (a,v) m3: (i,c)
m1: (v,c) m2: (i,d) m3: (a,m)
m1: (a,d) m2: (c,m) m3: (v,i)
m1: (i,m) m2: (v,d) m3: (a,c)
m1: (d,c) m2: (a,i) m3: (v,m)
m1: (a,m) m2: (v,c) m3: (i,d)
m1: (v,i) m2: (a,d) m3: (c,m)
m1: (a,c) m2: (i,m) m3: (v,d)
m1: (v,m) m2: (d,c) m3: (a,i)
m1: (i,d) m2: (a,m) m3: (v,c)
m1: (c,m) m2: (v,i) m3: (a,d)
m1: (v,d) m2: (a,c) m3: (i,m)
m1: (i,c) m2: (d,m) m3: (a,v)
Pero con 13 turnos no se cumple que todos esten con todos en todas las maquinas.... otra opcion seria hacer un turno de 30 semanas paro cada pareja tendria que estar 2 veces en una misma maquina, y a ver si asi pudiese cuadrar...
Mucho que dices, hazlo tú.Te juro que si supiera lo hacía, pero como no se solo puedo dar la idea >.<
Pero con 13 turnos no se cumple que todos esten con todos en todas las maquinas.... otra opcion seria hacer un turno de 30 semanas paro cada pareja tendria que estar 2 veces en una misma maquina, y a ver si asi pudiese cuadrar...
Bueno, lo primero que pides es imposible. PROLOG ha probado todas las combinaciones dice que nanai del paraguai. Y lo segundo no lo acabo de entender.
Si te sirve alguna modificación del PROLOG que he hecho, dimelo, explicamelo bien e intentaré ajustarlo.
Bueno, lo primero que pides es imposible. PROLOG ha probado todas las combinaciones dice que nanai del paraguai. Y lo segundo no lo acabo de entender.
Si te sirve alguna modificación del PROLOG que he hecho, dimelo, explicamelo bien e intentaré ajustarlo.
Me cuesta creer que haya probado todas las combinaciones en tan poco tiempo.... la verdad, contando que para una sola maquina ya hay 130 mil millones de posibles situaciones para las 3 makinas hay mas :S como puede prolog mirarlas todas tan rapidamente?
Me cuesta creer que haya probado todas las combinaciones en tan poco tiempo.... la verdad, contando que para una sola maquina ya hay 130 mil millones de posibles situaciones para las 3 makinas hay mas :S como puede prolog mirarlas todas tan rapidamente?
Mira (by juanís):
- Con 6 personas, hay 15 parejas posibles. Elegimos una pareja al azar para la maquina 1, y sacamos esas dos personas del monton de 6, que son 4.
- Ahora para la maquina 2 tenemos solo 4 personas disponibles. De 4 personas sacamos 6 parejas posibles, de las cuales elegimos una y quedan 2 personas mas.
- Y ya namás nos quedan 2 personas para la maquina 3 que solo pueden hacer 1 pareja.
Asi pues: 15 combinaciones posibles * 6 combinaciones posibles * 1 combinación posible = 90 combinaciones posibles de parejas para un turno de máquinas.
He ido probando permutaciones de subgrupos de N elementos (en mi caso solo funciona hasta 12) y mirar si cumplian las condiciones tal cual iba llenando la lista de permutaciones, asi que se salta muchos casos incorrectos.
En cualquier caso, publico mi codigo prolog.
turnos(N):- gen_turnos(P,N), nl, write('11 12 13'), nl, write_lista(P), fail.
turnos(_):- write('DONE').
write_lista([]).
write_lista([X|P]):-write_turno(X), nl, write_lista(P).
write_turno([A,B,C]):-write_pareja(A), write_pareja(B), write_pareja(C).
write_pareja([X|[Y]]):- write(X), write(Y), write(' ').
gen_turnos([X|L], N):- turno(X), gen_turnos([X],L,M), N is M + 1.
gen_turnos(_,[],0).
gen_turnos([A|Z],[X|L],N):-turno(X), not(anteriores(X,Z)), check(A,X), gen_turnos([X,A|Z],L,M), N is M + 1.
check([A,B,C],[D,E,F]):-
not(A = D), not(A = E), not(A = F),
not(B = D), not(B = E), not(B = F),
not(C = D), not(C = E), not(C = F),
not(mismo_turno(A,D)),not(mismo_turno(B,E)),not(mi smo_turno(C,F)).
mismo_turno([X,_],[X,_]).
mismo_turno([X,_],[_,X]).
mismo_turno([_,X],[X,_]).
mismo_turno([_,X],[_,X]).
anteriores(X,[Y|_]):-repite_maquina(X,Y).
anteriores(X,[_|L]):-anteriores(X,L).
repite_maquina([X,_,_],[X,_,_]).
repite_maquina([_,X,_],[_,X,_]).
repite_maquina([_,_,X],[_,_,X]).
turno([[a, d], [c, m], [v, i]]).
turno([[a, c], [v, i], [d, m]]).
turno([[a, c], [v, d], [i, m]]).
turno([[a, c], [v, m], [i, d]]).
turno([[a, c], [i, d], [v, m]]).
turno([[a, c], [i, m], [v, d]]).
turno([[a, c], [d, m], [v, i]]).
turno([[a, m], [v, i], [d, c]]).
turno([[a, m], [v, d], [i, c]]).
turno([[a, m], [v, c], [i, d]]).
turno([[a, m], [i, d], [v, c]]).
turno([[a, m], [i, c], [v, d]]).
turno([[a, m], [d, c], [v, i]]).
turno([[v, i], [a, d], [c, m]]).
turno([[v, i], [a, c], [d, m]]).
turno([[v, i], [a, m], [d, c]]).
turno([[v, i], [d, c], [a, m]]).
turno([[v, i], [d, m], [a, c]]).
turno([[v, i], [c, m], [a, d]]).
turno([[v, d], [a, i], [c, m]]).
turno([[v, d], [a, c], [i, m]]).
turno([[v, d], [a, m], [i, c]]).
turno([[v, d], [i, c], [a, m]]).
turno([[v, d], [i, m], [a, c]]).
turno([[v, d], [c, m], [a, i]]).
turno([[v, c], [a, i], [d, m]]).
turno([[v, c], [a, d], [i, m]]).
turno([[v, c], [a, m], [i, d]]).
turno([[v, c], [i, d], [a, m]]).
turno([[v, c], [i, m], [a, d]]).
turno([[v, c], [d, m], [a, i]]).
turno([[v, m], [a, i], [d, c]]).
turno([[v, m], [a, d], [i, c]]).
turno([[v, m], [a, c], [i, d]]).
turno([[v, m], [i, d], [a, c]]).
turno([[v, m], [i, c], [a, d]]).
turno([[v, m], [d, c], [a, i]]).
turno([[i, d], [a, v], [c, m]]).
turno([[i, d], [a, c], [v, m]]).
turno([[i, d], [a, m], [v, c]]).
turno([[i, d], [v, c], [a, m]]).
turno([[i, d], [v, m], [a, c]]).
turno([[i, d], [c, m], [a, v]]).
turno([[i, c], [a, v], [d, m]]).
turno([[i, c], [a, d], [v, m]]).
turno([[i, c], [a, m], [v, d]]).
turno([[i, c], [v, d], [a, m]]).
turno([[i, c], [v, m], [a, d]]).
turno([[i, c], [d, m], [a, v]]).
turno([[i, m], [a, v], [d, c]]).
turno([[i, m], [a, d], [v, c]]).
turno([[i, m], [a, c], [v, d]]).
turno([[i, m], [v, d], [a, c]]).
turno([[i, m], [v, c], [a, d]]).
turno([[i, m], [d, c], [a, v]]).
turno([[d, c], [a, v], [i, m]]).
turno([[d, c], [a, i], [v, m]]).
turno([[d, c], [a, m], [v, i]]).
turno([[d, c], [v, i], [a, m]]).
turno([[d, c], [v, m], [a, i]]).
turno([[d, c], [i, m], [a, v]]).
turno([[d, m], [a, v], [i, c]]).
turno([[d, m], [a, i], [v, c]]).
turno([[d, m], [a, c], [v, i]]).
turno([[d, m], [v, i], [a, c]]).
turno([[d, m], [v, c], [a, i]]).
turno([[d, m], [i, c], [a, v]]).
turno([[c, m], [a, v], [i, d]]).
turno([[c, m], [a, i], [v, d]]).
turno([[c, m], [a, d], [v, i]]).
turno([[c, m], [v, i], [a, d]]).
turno([[c, m], [v, d], [a, i]]).
turno([[c, m], [i, d], [a, v]]).
Licenciado BSD.
Por mucho que le miro, no veo nada que este mal. Fíjate, sí que tienes razón, hay un montón de posibilidades, pero muchas de ellas son evidentes de que no cumplen la condición. Un ejemplo es que teniendo 90 combinaciones de un turno, si tuviéramos que obtener 15 turnos con repeticiones y sin ningún tipo de condición, el numero de soluciones posibles es 90^15 = 205.891.132.094.649.000.000.000.000.000.
Sin embargo, cuando busco una permutación posible me salto muchísimas de estas comprobaciones porque por ejemplo en mi lista de N turnos, nunca añadiré un turno que este ya incluido, eso baja las posibilidades a 45.368.052.279.250.266.684.518.400 permutaciones (demostrado por un colega que ha aprobado combinatoria, xD), si luego, de estas he de sacar las que en el anterior turno tienen los mismos trabajando en las mismas maquinas, o con las mismas parejas, etc, etc, etc, las iteraciones que hacen solo se reducen y se reducen. Creo que mi codigo de PROLOG hace unos pocos millones de vueltas. Para un micro que va a 1GHZ cosas asi se las pule en pocos minutos.
EDIT: Otra cosa que hace esto es que cuando tiene que por ejemplo construir una lista de 15 turnos, hace primero una lista de 2, de 3, de 4, de ... N turnos validas (N < 15) y va añadiendo turnos al final que cumplan la condición. En este caso el programa solo consigue llegar a listas de 13 elementos. Como ve que ningún turno mas se puede introducir te construye todas las posibles listas de 13 elementos que pueda para intentar introducir un turno catorceavo, construir listas de 13 turnos es sin duda muchísimo menos costoso que hacer permutaciones de listas de 15 turnos, si en la ejecución no consigue introducir un catorceavo turno a lista la ejecución se detiene muchísimo antes de que pruebe permutaciones de una lista de 15 turnos, por eso tarda poco. Seguramente si las condiciones no fueran tan restrictivas como para poder hacer una lista de 15 turnos tardaría minutos u horas en sacarla. No se si me he explicado bien, xD.
< - >
Bueno por si te sirviera de algo, aqui tengo la lista entera de las posibles soluciones con listas de 13:
?- turnos(13).
11 12 13
vi ad cm
ac vm id
im dc av
vd am ic
cm vi ad
id ac vm
vc dm ai
am ic vd
dc av im
vm id ac
ad cm vi
ic vd am
dm ai vc
11 12 13
vi ad cm
ac vm id
dm ai vc
ic vd am
ad cm vi
vm id ac
dc av im
am ic vd
vc dm ai
id ac vm
cm vi ad
vd am ic
im dc av
11 12 13
vi ad cm
ac im vd
vm dc ai
id am vc
cm vi ad
vd ac im
ic dm av
am vc id
dc ai vm
im vd ac
ad cm vi
vc id am
dm av ic
11 12 13
vi ad cm
ac im vd
dm av ic
vc id am
ad cm vi
im vd ac
dc ai vm
am vc id
ic dm av
vd ac im
cm vi ad
id am vc
vm dc ai
11 12 13
vi ad cm
am vc id
ic dm av
vd ac im
cm vi ad
id am vc
vm dc ai
ac im vd
dm av ic
vc id am
ad cm vi
im vd ac
dc ai vm
11 12 13
vi ad cm
am vc id
dc ai vm
im vd ac
ad cm vi
vc id am
dm av ic
ac im vd
vm dc ai
id am vc
cm vi ad
vd ac im
ic dm av
11 12 13
vi ad cm
am ic vd
vc dm ai
id ac vm
cm vi ad
vd am ic
im dc av
ac vm id
dm ai vc
ic vd am
ad cm vi
vm id ac
dc av im
11 12 13
vi ad cm
am ic vd
dc av im
vm id ac
ad cm vi
ic vd am
dm ai vc
ac vm id
im dc av
vd am ic
cm vi ad
id ac vm
vc dm ai
11 12 13
vc dm ai
id ac vm
cm vi ad
vd am ic
im dc av
ac vm id
vi ad cm
am ic vd
dc av im
vm id ac
ad cm vi
ic vd am
dm ai vc
11 12 13
vc dm ai
id ac vm
cm vi ad
vd am ic
im dc av
ac vm id
dm ai vc
ic vd am
ad cm vi
vm id ac
dc av im
am ic vd
vi ad cm
11 12 13
vm dc ai
id am vc
cm vi ad
vd ac im
ic dm av
am vc id
vi ad cm
ac im vd
dm av ic
vc id am
ad cm vi
im vd ac
dc ai vm
11 12 13
vm dc ai
id am vc
cm vi ad
vd ac im
ic dm av
am vc id
dc ai vm
im vd ac
ad cm vi
vc id am
dm av ic
ac im vd
vi ad cm
11 12 13
ic dm av
vd ac im
cm vi ad
id am vc
vm dc ai
ac im vd
vi ad cm
am vc id
dc ai vm
im vd ac
ad cm vi
vc id am
dm av ic
11 12 13
ic dm av
vd ac im
cm vi ad
id am vc
vm dc ai
ac im vd
dm av ic
vc id am
ad cm vi
im vd ac
dc ai vm
am vc id
vi ad cm
11 12 13
im dc av
vd am ic
cm vi ad
id ac vm
vc dm ai
am ic vd
vi ad cm
ac vm id
dm ai vc
ic vd am
ad cm vi
vm id ac
dc av im
11 12 13
im dc av
vd am ic
cm vi ad
id ac vm
vc dm ai
am ic vd
dc av im
vm id ac
ad cm vi
ic vd am
dm ai vc
ac vm id
vi ad cm
11 12 13
dc av im
vm id ac
ad cm vi
ic vd am
dm ai vc
ac vm id
vi ad cm
am ic vd
vc dm ai
id ac vm
cm vi ad
vd am ic
im dc av
11 12 13
dc av im
vm id ac
ad cm vi
ic vd am
dm ai vc
ac vm id
im dc av
vd am ic
cm vi ad
id ac vm
vc dm ai
am ic vd
vi ad cm
11 12 13
dc ai vm
im vd ac
ad cm vi
vc id am
dm av ic
ac im vd
vi ad cm
am vc id
ic dm av
vd ac im
cm vi ad
id am vc
vm dc ai
11 12 13
dc ai vm
im vd ac
ad cm vi
vc id am
dm av ic
ac im vd
vm dc ai
id am vc
cm vi ad
vd ac im
ic dm av
am vc id
vi ad cm
11 12 13
dm av ic
vc id am
ad cm vi
im vd ac
dc ai vm
am vc id
vi ad cm
ac im vd
vm dc ai
id am vc
cm vi ad
vd ac im
ic dm av
11 12 13
dm av ic
vc id am
ad cm vi
im vd ac
dc ai vm
am vc id
ic dm av
vd ac im
cm vi ad
id am vc
vm dc ai
ac im vd
vi ad cm
11 12 13
dm ai vc
ic vd am
ad cm vi
vm id ac
dc av im
am ic vd
vi ad cm
ac vm id
im dc av
vd am ic
cm vi ad
id ac vm
vc dm ai
11 12 13
dm ai vc
ic vd am
ad cm vi
vm id ac
dc av im
am ic vd
vc dm ai
id ac vm
cm vi ad
vd am ic
im dc av
ac vm id
vi ad cm
DONE
Yes
?-
Está claro que por fuerza bruta este algoritmo no merece la pena resolverlo. Prolog o Lisp puede ser una buena elección, pero como yo no tengo ni idea de ninguno de los dos yo sigo dando guerra con mi algoritmo genético en java. ;)
He conseguido algunos avances. He dado con la condición que parece impedir que el problema tenga solución, y es bastante curiosa.
Resulta que no se puede dar al mismo tiempo las sentencias "la serie es cíclica" y "una persona no puede pasar dos semanas seguidas en la misma máquina". Es decir, o se cumple una o la otra, pero parece que no se puede hacer las dos al mismo tiempo.
Por alguna extraña razón sólo se encuentran soluciones para el resto de criterios al mismo tiempo si una persona ocupa la misma máquina en la primera y en la última semana de la serie, pudiendo cumplir la regla en el resto de casos.
Y lo más sorprendente: esto ocurre para series de 4 semanas o más. Es decir, este problema parece surgir aunque la serie tenga sólo 4 semanas. O eso me dice mi genético.
¿Qué voy a intentar hacer? Voy a intentar sacar dos series de 15 semanas con la pega ésta e intentar solaparlas de forma que se cree una de 30 semanas que pueda ser cíclica. De momento de 15 no he sacado ninguna, aunque de 10 semanas sí.
Por mucho que busques las condiciones son contradictorias entre ellas, ahora lo he visto. Es el mismo problema de las liguillas. En una liguilla son N equipos y todos han de jugar contra todos excepto con sigo mismos. Si los partidos se jugaran uno seguido de otro sin hacerse ningun partido paralelamente, nunca puedes evitar al final que un equipo acabe jugando dos partidos seguidos, esto esta demostrado. Tenemos el mismo problema aquí.
PD: Me he estado comiendo el coco un dia entero para darme cuenta que es imposible. xD
EDIT: Siempre te podria hacer un programa que te generara 15 turnos, pero se tendria que repetir alguna persona en alguna maquina 2 turnos seguidos, si no es imposible. Ya le he quitado esta condicion y ya me esta tardando bastante mas que lo que solia en generar la lista. xD
Eso que dices de la liga tiene bastante sentido, aunque no lo acabo de ver. Igual que no creo que este caso sea exactamente igual.
Mientras, os dejo un pseudo-solución con 10 semanas:
11 12 13
-- -- --
CV MD AI
AD IV MC
CI MA VD
MV ID CA
IA VC DM
MC DA VI
VA IM CD
ID CA MV
AM VD IC
VI CM AD
Notese que V, M y A tendrían que repetir máquina al recomenzar el ciclo.
Otro ejemplo con 12 semanas
11 12 13
-- -- --
ID AC VM
AV MD CI
MI CV DA
DC MA VI
IA VD CM
DM IC VA
CV AD IM
AM VI DC
DV CM IA
IC VA DM
DA IM CV
IV CD AM
Eso que dices de la liga tiene bastante sentido, aunque no lo acabo de ver. Igual que no creo que este caso sea exactamente igual.
Si que es muy parecido, una liguilla puedes representarla en una cuadricula dibujada en un papel. Esto no podrías, seria tres cuadriculas, una por maquina. Si en una cuadricula no puedes evitar que un equipo juegue dos partidos seguidos, como vas a evitar que una persona no acabe repitiendo en una maquina a sabiendas de que tienes mas restricciones respecto las otras cuadriculas?
PD: Lleva sus 20 minutos y aun no ha generado la lista, xD.
Esto demuestra el dicho de que si le das un problema a 10 programadores, te darán 10 soluciones distintas y a su vez válidas xDDD
No te darán diez soluciones distintas, probalemente te den la misma (o parecida) pero obtenida por distintos métodos. Mientras que tu has utilizado una búsqueda exhuastiba para el problema buscado todas las posibilidades y filtrando una que que sea buena otros han probado algoritmos huerísticos para general algunas que cumplan las reglas.
Creo que voy a optar por intentar sacar una secuencia cíclica de 30 semanas, en la que cada pareja esté dos veces por máquina en vez de una. Sería equivalente a hacer lo 15 semanas y una repetición, salvo que en este caso ma misma pareja no repite máquina cada 15 semanas exactamente, sino que puede ser cada 14-16, 10-20 o 1-29, por ejemplo.
En teoría cuanto más que acerque al 15-15 tanto mejor, pero como parece que no va a ser posible intentaré buscar una solución lo más óptima posible, como 14-16 para una pareja y 15-15 para el resto. Espero que te sirva... ;)
A la hora de la comida lo voy a dejar corriendo un par de horas a ver a ver que tal...
Yo de programación ando cortito, pero la solución que me parece más logica es aumentar el número de máquinas o disminuir el número de personas hasta que cuadre XD.
Saludos
Yo de programación ando cortito, pero la solución que me parece más logica es aumentar el número de máquinas o disminuir el número de personas hasta que cuadre XD.
Saludos
jajaj eso diselo a los jefes jejeje :D
En realidad no hay que hacer exactamente 15 semanas, lo de las 15 semanas lo decia porque habia 15 posibilidades diferentes, pero en realidad se puede hacer de las semanas que se quieran siempre que al año salgan mas o menos igual para todos. pero que se cumplan las condiciones...
En el horario de 2008 tenemos un total de 31 semanas, asi que si se hace un horario que aproximadamente sea igual para todos y que cumpla las reglas, ( si alguna pareja repite una vez mas que el resto no pasa nada... pero tampoco que repita 4 veces... lo mas ajustado posible seria valido tambien :)
Adjunto la hoja de calculo del horario para que veais como es por si os aclara mas la cosa, el horario esta formado por ciclos de mañanas tardes y noches, cada conjunto asi se considera 1 semana ya que siempre son 7 dias pero no corresponden de lunes a domingo. las semanas estan separadas por 2 dias de descanso entre si y ademas cada mes y algo hay una larga de descanso de 7 dias...
Lo que habria que hacer es sacar un horario de 31 semanas lo mas aproximado posible y luego repartirlo en las semanas trabajadas :)
Le he quitado las normas de repetirse personas entre una semana y otra al programa de PROLOG, y lleva desde las 10 mañana procesando y aun no ha sacado nada. xD
Eso si, horarios de 13 semanas que cumplan todo excepto que se hagan algunas parejas o que la gente este en algunas maquinas los que quieras tengo, de hecho, los tengo todos. xD
Le he quitado las normas de repetirse personas entre una semana y otra al programa de PROLOG, y lleva desde las 10 mañana procesando y aun no ha sacado nada. xD
Eso si, horarios de 13 semanas que cumplan todo excepto que se hagan algunas parejas o que la gente este en algunas maquinas los que quieras tengo, de hecho, los tengo todos. xD
Ums, lo siento pero no me vale, como minimo cada pareja tienen que pasar una vez por la makina... sino se me quejaran :S
Ums, lo siento pero no me vale, como minimo cada pareja tienen que pasar una vez por la makina... sino se me quejaran :S
Eso hace. :S Lo que pasa es que a lo mejor hay gente que repetirá máquina 2 turnos seguidos pero no pareja. Al menos todas las personas haran las 3 maquinas con las 5 personas con las que puede hacer pareja, pero a lo mejor le tocará repetir maquina con otra pareja, a eso me referia.
PD: Lleva desde las 10 de la mañana y aun no me ha sacado una solucion O_o. Menos mal que tengo 2 cores y uno esta libre.
< - >
Veamos, una alternativa:
11 12 13
-- -- --
av dc im
cm ai vd
vi dm ac
ad ic vm
im av dc
vd cm ai
am di vc
ic vm ad
dm ac vi
ai vd cm
dc im av
vm ad ic
di vc am
ac vi dm
vc am di
Marco en negrita por donde cojea.
No me he leído el hilo pero tras ver las premisas, me da la impresión de que este problema no tiene solución periódica; es decir, que es posible hacer lo que pides pero no hay manera de elaborar un patrón repetitivo; no se como explicarme; quiero decir que la posible solución es como el numero PI, tiene un valor determinado, pero no se pude representar con exactitud porque harían falta infinitas cifras no periódicas.
No me he leído el hilo pero tras ver las premisas, me da la impresión de que este problema no tiene solución periódica; es decir, que es posible hacer lo que pides pero no hay manera de elaborar un patrón repetitivo; no se como explicarme; quiero decir que la posible solución es como el numero PI, tiene un valor determinado, pero no se pude representar con exactitud porque harían falta infinitas cifras no periódicas.
En realidad no tiene porque ser ciclico, con hacerlo para 31 semanas y que quede repartido ya me vale.
Powered by vBulletin® Version 4.2.5 Copyright © 2025 vBulletin Solutions Inc. All rights reserved.