Autor Tema: Algoritmo de los equipos equilibrados

0 Usuarios y 1 Visitante están viendo este tema.

18 Septiembre, 2009, 01:38 pm
Leído 2445 veces

maesla

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
Hola a todos:
Hice una pequeña aplicación para mi y para mis amigos para conseguir hacer equipos lo más equilibrados posibles a la hora de jugar a futbol sala.
Dicho algoritmo consiste en asignar a los 10 jugadores una puntuación numérica.
Luego el algoritmo explora iterativamente todas las posibles combinaciones, que son (corregidme si me equivoco)
\( \displaystyle\binom{10}{5} \)=252

La repartición optima de jugadores se hace de la siguiente manera:

Se busca que la diferencia de medias entre ambos equipos, sea minima
Se busca que la varianza dentro de los equipos, sea minima.

Se itera 252 veces:
  • Si la nueva combinación N de equipos da una diferencia de medias menor, N es la nueva combinación óptima
  • Si la nueva combinacion N de equipos da una diferencia de medias igual, pero la varianza dentro de los equipos es menor,N es la nueva combinación óptima
  • Si no se cumple estos casos, pasamos a la siguiente iteración

Todo esto lo escribo porque estoy intentando hacer un algoritmo que no tenga que explorar las 252 combinaciones, algún método más directo.

He probado con el tipico algoritmo de colegio, en el que se van cogiendo los mejores por orden ascendente, y se van repartiendo primero a un equipo y luego al otro, pero salen mucho peor.

Yo creo que tiene que haber algún método más directo, y quería ver si a alguien se le ocurría algo.

Muchas gracias

21 Septiembre, 2009, 12:28 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 No estoy seguro de que haya un método más directo, que la inspección completa de los casos. Es un problema de optimización discreta, lo cual en general complica las cosas.
 
 De todas formas el volumen de datos es suficientemente pequeño como para que eso no sea un drama. ¿No?.

 Por otro lado si entiendo bien parece que tu primer criterio es minimizar la diferencia de medias y sólo en caso de igualdad interviene la varianza. ¿Es así?.

Saludos.

23 Septiembre, 2009, 01:53 pm
Respuesta #2

maesla

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 20
  • Karma: +0/-0
Sí, primero minimizo la diferencia de medias, y entre todos los que tienen la misma diferencia de medias, me quedo con los equipos que entre sí tienen menor varianza.

Es verdad que no es un drama, porque no son muchos casos.

Pero si lo extrapolamos a fútbol 7, ya serían \( \displaystyle\binom{14}{7}\textsf{ = 3432} \) o en fútbol 11  \( \displaystyle\binom{22}{11}\textsf{ = 705432} \) , que vamos, realmente para un computador, tampoco es demasiado

Era más curiosidad matemática que otra cosa  ;)