Diferencia entre revisiones de «El problema de la organización del calendario de un campeonato con Divide y Vencerás»
Contenido eliminado Contenido añadido
Sin resumen de edición |
Sin resumen de edición |
||
Línea 7:
== Descripción ==
Si '''n''' es una potencia de '''2''', dar un algoritmo para construir un horario que permita que el
torneo concluya en '''n-1''' días.
Línea 14:
== Esquema ==
La estrategia Divide y Vencerás consiste en descomponer un problema en subproblemas más simples del mismo
tipo, resolverlos de forma independiente y una vez obtenidas las soluciones parciales combinarlas para
obtener la solución del problema original.
== Suposiciones ==
Por concreción, y sin perdida de generalidad, puede suponerse que las competiciones se celebran en días
sucesivos y que cada participante compite una vez por día.
El número de participantes es potencia de dos, que nos simplificará el problema. Por lo tanto n = 2k
participantes, con k entero positivo.
Línea 34:
'''DIVIDE Y VENCERÁS''' => n<sup>2</sup>
En la técnica divide y vencerás descomponemos el problema en un conjunto de subproblemas más
pequeños. En nuestro caso, el coste cuadrático se debe a que, al combinar las soluciones para obtener la
solución para el problema original se realizan dos bucles anidados completando el resto de la tabla con los
mismos valores existentes en la otra mitad.
'''MUCHO MÁS EFICIENTE QUE LA FUERZA BRUTA'''
La solución del problema puede representarse en una tabla de dimensión n*(n-1). El elemento (i,j)–esimo
de la tabla, 1<= i<=n, 1<=j<n, contiene el numero del participante contra el que el participante i-esimo
compite el día j-esimo. Línea 60 ⟶ 64:
La unión de los dos subresultados no da la solución final.
Después de conseguirlas individualmente tendremos que combinarlas:
Para ello habrá que cruzarlas puesto que faltan las competiciones de los participantes de la primera subsolución
con los de la segunda.
Se trata de que los participantes de la primera parte jueguen con los de la segunda y viceversa. Para formar el
subcalendario del primer participante basta con que compita en días sucesivos con los participantes de numeración
| |||