0votos

Torneo round-robin balanceado en Haskell

por josejuan hace 3 años

.

Crear emparejamientos para una liga de una forma concreta.

1
2
3
4
rondas :: Int -> [[(Int, Int)]] 
rondas n = take (n - 1) $ rot [2 .. n2] [n2 + 1 .. n] 
 where n2 = n `div` 2 
       rot xs ys = zip (1:xs) ys : rot (head ys: init xs) (tail ys ++ [last xs]) 
4 comentarios
0votos

Escrito por JCarles hace 3 años

Ese es el algoritmo estándar de un round-robin que funciona bien para muchas competiciones, pero no para el caso expuesto.

Por ejemplo: rondas 9 = [[(1,5),(2,6),(3,7),(4,8)],[(1,6),(5,7),(2,8),(3,9)],[(1,7),(6,8),(5,9),(2,4)],[(1,8),(7,9),(6,4),(5,3)],[(1,9),(8,4),(7,3),(6,2)],[(1,4),(9,3),(8,2),(7,5)],[(1,3),(4,2),(9,5),(8,6)],[(1,2),(3,5),(4,6),(9,7)]]

El jugador 9 descansa en la primera jornada y en la segunda es el último en jugar. La idea es mejorar esa situación y cambiar el orden de los emparejamientos para que haya un equilibrio. ¿ya no te lees los requisitos josejuan? :D
0votos

Escrito por josejuan hace 3 años

Aunque el enunciado es un poco largo y aburrido hice el esfuerzo de leerlo completamente :P

El tema es que, si me ciño al enunciado, no estoy de acuerdo (puesto que la función a optimizar debería ser, en mi opinión, el máximo de la espera máxima de cada jugador, no esa suma "rara") y en todo caso, el problema bajo el paraguas de la optimización no me parece fácil (a mi), pues si se usa heurística ya no se garantiza optimalidad y yo no he encontrado un algoritmo óptimo para el caso impar (cuya cota inferior de espera es ceil(n/2)).

Como mi algoritmo heurístico no se ciñe al aburrido enunciado (sino a mi función de optimización) y es un poco feo (aunque no tanto como el enunciado :P) y dado que no había soluciones, preferí poner el algoritmo típico que sí es óptimo para el caso par.

Recuerdo que el enunciado pone que la solución debe ser óptima (la heurística por definición no se sabe si es óptima) y fácil ¿tienes tú un algoritmo que cumpla con ambas cosas?.
0votos

Escrito por JCarles hace 3 años

El enunciado está expresamente escrito así para que sea comprensible para todas las "edades". Ya entiendo que para algunos os sea muy simplón.

La suma "rara" es una forma sencilla de puntuar una solución expuesta respecto a otras. Lo que sugieres tu de "la espera máxima" no sería lo mismo, ya que los requisitos especifican que también es insatisfactorio jugar dos partidas seguidas. El objetivo no es la espera mínima, sino jugar cada ceil(njug/2) partidas.

Quizás me equivoqué al decir óptimo. Es suficiente en aplicar algún sistema que se acerque en lo posible a la situación ideal, según la capacidad de cada uno.

El requisito de que sea fácil será porque estamos en un sitio de katas, no porqué lo haya dicho yo :D

Y por último, y no menos importante, la fuerza bruta es una opción en determinados casos, y éste es uno de ellos. Y se conseguiría una solución óptima y fácil ¿verdad?
0votos

Escrito por josejuan hace 3 años

No JCarles, discrepo en lo principal, eres veterano en esto y además con capacidad para apreciar la diferencia entre diferentes soluciones y su dificultad.

Lo de "expresamente escrito" obviamente tienes razón, lo de aburrido era sólo una broma en recompensa a tu acicate primero ;P

Buscar la espera mínima es lo óptimo si se quiere balancear la espera, promediar (minimizar la suma) no balancea nada (dar a uno 0 caramelos y a otro 10 hacen una media de 5 caramelos a cada uno :/ que es lo que indicas tu, mientras que si dices que hay que maximizar el mínimo de caramelos te dará 5 a cada uno), si quieres, añade la restricción de no jugar dos veces en la misma ronda (si es que la solución no lo hace ya) y listo.

Efectivamente, el error principal y para mí más importante es la definición de optimalidad. Como dije antes, fácil y óptimo son dos propiedades que creo no casan con este problema.

No dudo que ya sabes (pillín) que de la gran mayoría de desafíos se puede encontrar fácilmente un algoritmo que lo resuelva, siempre que no se exija optimalidad. De ahí que exigir que sea óptimo hace el desafío difícil y justifique mi primer comentario (en el que creo haber aclarado el por qué).

Por último, el desafío me ha parecido muy interesante, pues es de los que permite a los que inician su andadura en la fascinante búsqueda de algoritmos, descubrir la tremenda complejidad de los problemas combinacionales (al que se moleste un poco en buscar literatura al respecto claro).

¿Existirá para tu caso un algoritmo óptimo?, es posible, pero en mi opinión no será nada fácil y/o incluirá rotaciones de las rondas en tamaños coprimos.

Este tipo de problemas está lleno de números mágicos y de instancias sin solución.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.