Algoritmos de programación dinámica para calcular torneos de eliminación directa óptimos
Autores: Bdic, Amelia; Bdic, Costin; Buligiu, Ion; Ciora, Liviu Ion; Logoftu, Doina
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Algoritmos de programación dinámica para calcular torneos de eliminación directa óptimos
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Torneos
óptimo
Programación dinámica
Algoritmos
Eficiencia
Python
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 32
Citaciones: Sin citaciones
Estudiamos competiciones estructuradas como torneos de eliminación única con forma jerárquica. Definimos torneos óptimos maximizando la atracción de tal manera que los jugadores más destacados tengan la oportunidad de encontrarse en etapas superiores del torneo. Proponemos un algoritmo de programación dinámica para calcular torneos óptimos y proporcionamos su análisis de complejidad sólida. Basándonos en la idea del enfoque de programación dinámica, también desarrollamos algoritmos subóptimos más eficientes determinísticos y estocásticos. Presentamos resultados experimentales obtenidos con la implementación en Python de todos los algoritmos propuestos con respecto a la optimalidad de las soluciones y la eficiencia del tiempo de ejecución.
Descripción
Estudiamos competiciones estructuradas como torneos de eliminación única con forma jerárquica. Definimos torneos óptimos maximizando la atracción de tal manera que los jugadores más destacados tengan la oportunidad de encontrarse en etapas superiores del torneo. Proponemos un algoritmo de programación dinámica para calcular torneos óptimos y proporcionamos su análisis de complejidad sólida. Basándonos en la idea del enfoque de programación dinámica, también desarrollamos algoritmos subóptimos más eficientes determinísticos y estocásticos. Presentamos resultados experimentales obtenidos con la implementación en Python de todos los algoritmos propuestos con respecto a la optimalidad de las soluciones y la eficiencia del tiempo de ejecución.