Optimización de Plantillas de Fútbol en Python: POO vs. Backtracking

Este documento explora dos enfoques de programación en Python para abordar un desafío común en la gestión deportiva: la optimización de la plantilla de un equipo de fútbol bajo un presupuesto limitado. Presentaremos una implementación basada en la Programación Orientada a Objetos (POO) y una solución algorítmica utilizando el principio de backtracking, destacando cómo cada paradigma puede ser aplicado para seleccionar la mejor combinación de jugadores y maximizar el rendimiento del equipo.

Implementación Orientada a Objetos para la Gestión de Equipos

La primera sección detalla un modelo de clases en Python diseñado para representar jugadores y equipos. Este enfoque POO permite una gestión estructurada y modular de los recursos, facilitando la toma de decisiones sobre la contratación de deportistas.

Clase Jugador

La clase Jugador encapsula las propiedades fundamentales de cada deportista: su posición en el campo, el costo asociado a su contratación y el aporte o valor que suma al rendimiento general del equipo.

class Jugador:
    def __init__(self, posicion, costo, aporte):
        self.posicion = posicion
        self.costo = costo
        self.aporte = aporte

    def __repr__(self):
        # Representación legible del objeto Jugador
        return self.posicion

Clase Equipo

La clase Equipo es responsable de gestionar el presupuesto disponible, las opciones de jugadores en el mercado y la lógica para evaluar y seleccionar la plantilla óptima. Incluye métodos para calcular los costos y el valor del equipo, así como para decidir si un jugador candidato debe ser aceptado o rechazado según criterios predefinidos.

class Equipo:
    def __init__(self):
        self.presupuesto = 700000
        self.opciones = []
        # Inicialización de jugadores disponibles en el mercado
        jugador = Jugador("Defensa", 100000, 2)
        self.opciones.append(jugador)
        jugador = Jugador("Lateral", 200000, 4)
        self.opciones.append(jugador)
        jugador = Jugador("Mediocampista", 200000, 5)
        self.opciones.append(jugador)
        jugador = Jugador("Delantero", 400000, 7)
        self.opciones.append(jugador)
        self.equipo = [] # Plantilla actual del equipo

    def evaluar_costo_equipo(self, equipo_candidato):
        """Calcula el costo total de un equipo candidato."""
        costo = 0
        if len(equipo_candidato) == 0:
            # Si el equipo está vacío, retorna un costo que excede el presupuesto
            # para que no sea considerado una opción válida por sí mismo.
            return self.presupuesto + 1
        for jugador in equipo_candidato:
            costo += jugador.costo
        return costo

    def evaluar_aporte_equipo(self, equipo_candidato):
        """Calcula el aporte total (valor) de un equipo candidato."""
        valor = 0
        if len(equipo_candidato) == 0:
            # Si el equipo está vacío, retorna -1 para indicar que no tiene aporte.
            return -1
        for jugador in equipo_candidato:
            valor += jugador.aporte
        return valor

    def evaluar_aporte_actual(self):
        """Evalúa el aporte del equipo actualmente seleccionado."""
        return self.evaluar_aporte_equipo(self.equipo)

    def evaluar_costo_actual(self):
        """Evalúa el costo del equipo actualmente seleccionado."""
        return self.evaluar_costo_equipo(self.equipo)

    def generar_equipos_candidatos(self, equipo_base):
        """Genera nuevas combinaciones de equipos añadiendo un jugador de las opciones disponibles."""
        alternativas = []
        for jugador in self.opciones:
            opcion = equipo_base.copy()
            opcion.append(jugador)
            alternativas.append(opcion)
        return alternativas

    def aceptar_candidato(self, equipo_candidato):
        """Determina si un equipo candidato es mejor que el actual, considerando presupuesto y valor.
        La lógica original prioriza la aceptación si el presupuesto restante es bajo y el valor es superior,
        o si el valor es igual pero el costo es menor.
        """
        costo = self.evaluar_costo_equipo(equipo_candidato)
        valor = self.evaluar_aporte_equipo(equipo_candidato)

        if costo > self.presupuesto:
            return False # Excede el presupuesto, no se puede aceptar

        diferencia_presupuesto = self.presupuesto - costo
        # Si el presupuesto restante es bajo (menos de 100,000), se prioriza el valor
        if diferencia_presupuesto < 100000:
            costo_actual = self.evaluar_costo_actual()
            valor_actual = self.evaluar_aporte_actual()

            if valor > valor_actual:
                return True # Mejor valor, se acepta
            elif valor == valor_actual:
                if costo < costo_actual:
                    return True # Mismo valor, pero más barato, se acepta
        # En otros casos, la lógica original no especifica una aceptación por defecto
        # si hay mucho presupuesto restante y el equipo no es 'casi completo'.
        # Se mantiene el comportamiento original de retornar False.
        return False

    def rechazar_candidato(self, equipo_candidato):
        """Determina si un equipo candidato debe ser rechazado (principalmente por exceder el presupuesto)."""
        costo = self.evaluar_costo_equipo(equipo_candidato)
        return costo > self.presupuesto

    def contratar(self, equipo_candidato):
        """Proceso recursivo para construir el equipo óptimo, evaluando candidatos.
        Este método explora combinaciones y actualiza el equipo si encuentra una mejor opción.
        """
        if len(equipo_candidato) != 0:
            if self.rechazar_candidato(equipo_candidato):
                return # Si el candidato excede el presupuesto, se descarta
            if self.aceptar_candidato(equipo_candidato):
                self.equipo = equipo_candidato # Si el candidato es aceptado, se convierte en el equipo actual
                return

        # Generar y evaluar nuevas alternativas recursivamente
        alternativas = self.generar_equipos_candidatos(equipo_candidato)
        for equipo in alternativas:
            # print(equipo) # Descomentar para visualizar el proceso de construcción del equipo
            self.contratar(equipo)

    def planificar_temporada(self):
        """Inicia el proceso de planificación y contratación del equipo para la temporada."""
        equipo_candidato = []
        self.contratar(equipo_candidato)

# --- Ejecución del ejemplo con Programación Orientada a Objetos ---
colocolo = Equipo()
colocolo.planificar_temporada()
print("\n--- Resultados de la Implementación POO ---")
print(f"Equipo final seleccionado: {colocolo.equipo}")
print(f"Aporte total del equipo: {colocolo.evaluar_aporte_actual()}")
print(f"Costo total del equipo: {colocolo.evaluar_costo_actual()}")

Optimización de Equipo con Backtracking

Esta sección presenta una solución alternativa al problema de selección de jugadores utilizando el algoritmo de backtracking. Este enfoque explora sistemáticamente todas las combinaciones posibles de jugadores, podando las ramas que exceden el presupuesto, para encontrar la configuración que maximice el aporte total.

Funciones Auxiliares para Backtracking

Se definen funciones simples para calcular el costo y el aporte de una lista de jugadores, que serán utilizadas por el algoritmo de backtracking para evaluar las combinaciones.

def costo(lista_jugadores):
    """Calcula el costo total de una lista de jugadores. Cada jugador es un sub-array [posición, costo, aporte]."""
    suma = 0
    for jug in lista_jugadores:
        suma += jug[1] # El costo se encuentra en la posición 1 del sub-array del jugador
    return suma

def aporte(lista_jugadores):
    """Calcula el aporte total de una lista de jugadores. Cada jugador es un sub-array [posición, costo, aporte]."""
    suma = 0
    for jug in lista_jugadores:
        suma += jug[2] # El aporte se encuentra en la posición 2 del sub-array del jugador
    return suma

Algoritmo de Backtracking: Función combinacion

La función combinacion implementa el algoritmo de backtracking para encontrar la mejor combinación de jugadores. Utiliza variables globales (maximoGlobal y solucionGlobal) para mantener el seguimiento del máximo aporte encontrado y la solución de equipo correspondiente a ese aporte.

def combinacion(jugadores_disponibles, lista_combinacion_actual, presupuesto_maximo):
    """
    Algoritmo de backtracking para encontrar la combinación óptima de jugadores.

    Args:
        jugadores_disponibles (list): Lista de todos los jugadores disponibles (formato: [posición, costo, aporte]).
        lista_combinacion_actual (list): La combinación de jugadores que se está construyendo en la recursión actual.
        presupuesto_maximo (int): El presupuesto máximo permitido para el equipo.
    """
    global maximoGlobal
    global solucionGlobal

    # Caso base: si el costo de la combinación actual excede el presupuesto, se poda esta rama de búsqueda.
    if costo(lista_combinacion_actual) > presupuesto_maximo:
        return

    # Si no excede el presupuesto, es una solución válida. Se verifica si es la mejor encontrada hasta ahora.
    else:
        if aporte(lista_combinacion_actual) > maximoGlobal: # Si es el mejor aporte que he encontrado
            maximoGlobal = aporte(lista_combinacion_actual) # Guardo el aporte
            solucionGlobal.clear() # Borro la solución anterior
            for elem in lista_combinacion_actual: # Y guardo la solución actual
                solucionGlobal.append(elem)

    # Caso recursivo: se intenta agregar cada jugador disponible a la lista de combinaciones.
    # La implementación original itera sobre la lista completa de jugadores disponibles en cada paso.
    # Esto puede generar combinaciones con jugadores repetidos si no se maneja el índice de inicio
    # para asegurar que cada jugador se considere solo una vez en una combinación única.
    # Para mantener la fidelidad al código original, se conserva esta iteración.
    for jugador in jugadores_disponibles:
        lista_combinacion_actual.append(jugador) # Se agrega el jugador a la combinación actual
        if costo(lista_combinacion_actual) <= presupuesto_maximo:
            # Si la combinación con el nuevo jugador no excede el presupuesto, se llama recursivamente.
            combinacion(jugadores_disponibles, lista_combinacion_actual, presupuesto_maximo)
        lista_combinacion_actual.remove(jugador) # Se hace backtracking: se remueve el jugador para probar otras combinaciones

Ejecución del Algoritmo de Backtracking

Se inicializan las variables globales necesarias para el algoritmo de backtracking y se ejecuta la función principal combinacion para encontrar la solución óptima de la plantilla.

maximoGlobal = 0
solucionGlobal = []
presupuesto = 700000
# Definición de jugadores disponibles en formato: [posición, costo, aporte]
jugadores = [["defensa", 100000, 2], ["lateral", 200000, 4], ["mediocampista", 200000, 5], ["delantero", 400000, 7]]

print("\n--- Resultados de la Implementación con Backtracking ---")
combinacion(jugadores, [], presupuesto)
print(f"Máximo aporte global encontrado: {maximoGlobal}")
print(f"Solución de equipo óptima: {solucionGlobal}")

Conclusión

Ambos enfoques presentados, la programación orientada a objetos y el algoritmo de backtracking, ofrecen soluciones válidas para el problema de optimización de la plantilla de un equipo de fútbol. Mientras que el modelo POO proporciona una estructura más modular y extensible para la gestión de entidades como jugadores y equipos, el backtracking es una técnica algorítmica poderosa para explorar espacios de búsqueda y encontrar soluciones óptimas en problemas combinatorios, como la selección de subconjuntos bajo restricciones.

La elección entre uno y otro dependerá de la complejidad específica del problema, la necesidad de modularidad en el diseño del software y la eficiencia requerida para el tamaño de los datos y el espacio de búsqueda.