miércoles, julio 19, 2006

El problema de la Bundesliga

Imaginen una liga de football como la Bundesliga en Alemania, donde el campeón es aquel que acumule más puntos al final de la temporada. Ahora supongan que, en un momento determinado de la temporada, quieren saber si su equipo favorito todavía tiene posibilidades de ser campeón.
Si nos basamos en las antiguas reglas, donde el ganador de un juego obtenía dos puntos, y en caso de empate cada equipo recibía un punto, este problema se puede resolver en tiempo polinomial utilizando un algoritmo de flujo en redes, donde la entrada son siempre dos puntos y la salida son otros dos puntos, distribuidos dependiendo del resultado del encuentro.
Pensemos ahora en las nuevas reglas, donde el ganador recibe 3 puntos, y el resto del puntaje permanece igual. Resulta que ese pequeño cambio produce que el problema se vuelva NP-completo. Este resultado se publicó en 1999. Ahora, para alcanzar tal cota se asumió que la forma de diseñar el calendario de juegos es completamente aleatoria. Sin embargo, la Bundesliga tiene un algoritmo para generar tal calendario que tiene muchas restricciones; es decir, algunos juegos no pueden ocurrir.
Hasta donde yo sé, la complejidad del problema de decidir si un equipo todavía puede ser campeón, dadas las restricciones en juegos de la Bundesliga sigue sin conocerse a la fecha, así que ya saben, si quieren publicar un resultado, solo tienen que resolver ese problema.

3 comentarios:

Saffog Tochtli dijo...

Ohh por Dios, nooo un problema np-completo. E imagino al iluso que se le ocurrió: "Ya sé, ya sé, que tal si el que gana recibe 3 puntos."

Rafael Peñaloza dijo...
Este blog ha sido eliminado por un administrador de blog.
Rafael Peñaloza dijo...

Yo creo que no expliqué bien, Jordi, porque ahora que lo leo, también suena confuso para mí. Todos los equipos juegan contra todos 2 veces en la temporada, las restricciones que hay es sobre cuándo pueden jugar. De esta forma, tras cierta cantidad de semanas jugadas, es posible que, dadas las restricciones, los dos juegos entre ciertos equipos ya se hayan llevado a cabo. Sin embargo, el modelo simplista asume que cualquier órden de juegos es posible, cosa que no sucede en la Bundesliga