Algoritmos para juegos | Tema 2: Algoritmos voraces Por Alejandro Vargas Lugo Obra de creación propia bajo licencia Creative Commons BY-NC-SA 4.0 Internacional https://creativecommons.org/licenses/by-nc-sa/4.0/deed.es

Introducción

Complejidad de algoritmos: NP

Un gran número de problemas de informática consisten en encontrar la mejor solución posible (solución óptima) cuando existen un gran número de posibles alternativas. Se considera que un problema es "fácil" cuando la solución puede hallarse en tiempo polinómico (p. ej. N², N³...), en contraposición a tiempo exponencial (p. ej. 2ⁿ, N!). En términos matemáticos, se dice que los primeros pertenecen a la familia de problemas P, mientras que los segundos pertenecen a los problemas NP.

Existen diferentes categorías de problemas NP, pero algo que tienen en común es que requieren una gran cantidad de cómputo, y por tanto, de tiempo, para hallar una solución óptima. Es muy fácil ver por qué si comparamos un problema de tiempo polinómico con otro de tiempo exponencial:

Como puedes observar, los problemas de tiempo polinómico pueden llegar a tener miles de elementos, pero aún así mantenerse en un número razonable de unas pocas millones de iteraciones (algo bastante asequible para los computadores modernos), mientras que los problemas de tiempo exponencial son totalmente inviables a partir de unos cientos de elementos, alcanzando un número de iteraciones en el orden de varias decenas o centenas de cifras.

Un ejemplo clásico es el problema del viajante (TSP, del inglés Travelling Salesman Problem), en el cual un vendedor debe visitar una serie de ciudades exactamente una vez y regresar al punto de partida, minimizando la distancia total recorrida. Aunque a primera vista el enunciado es sencillo, el número de rutas posibles crece extremadamente rápido con el número de ciudades. Se requieren, para N ciudades, evaluar aproximadamente (N-1)! / 2 iteraciones para hallar la solución óptima.

En la práctica, sin embargo, rara vez se necesita la mejor solución. Existen algoritmos que nos pueden ahorrar una cantidad enorme de cómputo hallando una solución no perfecta, pero suficientemente buena, en un tiempo muchísimo más corto. Estos son los algoritmos voraces.

Algoritmos voraces

Estos algoritmos tienen la característica de que, en cada paso/iteración, se elige la opción más favorable (menor distancia, mayor beneficio... dependiendo del problema) sin evaluar inicialmente el problema de forma global ni corrigiendo decisiones pasadas. Esta estrategia reduce drásticamente la complejidad de obtener una solución (de tiempo exponencial (o peor) a tiempo polinómico). Sin embargo, hay que tener cuidado, ya que en casos límite un algoritmo voraz podría llegar a dar soluciones muy inoptimizadas.

Veamos un ejemplo, de nuevo con el problema del viajante. Supongamos que tenemos los siguientes puntos en un mapa, y queremos hallar el ciclo (camino cerrado) que conecte todos los puntos minimizando la distancia. Partimos desde el punto azul.

¿Cómo resolvería un algoritmo voraz este problema? Recordemos que, en cada paso, elegimos el punto más favorable para nosotros. En este caso, aquel que esté a menor distancia, sin tener en cuenta el mapa de puntos al completo. Con esta lógica, es fácil ver que, desde el punto azul, avanzaríamos al punto verde justo al lado derecho, y desde allí, seguiríamos la espiral de puntos hacia la izquierda. Una vez que llegásemos al punto de la esquina superior izquierda, sólo nos quedaría un punto más que conectar, el de la esquina opuesta. Y desde allí volveríamos al punto azul...

No solo esta ruta no es óptima, cosa que ya podíamos esperar, sino que también es ineficiente. Basta con echar un vistazo al resultado para ver que se podría acortar considerablemente si pasamos por el punto 9 antes de llegar al punto 2, de esta manera:

Esta ruta sí que se corresponde con la solución óptima. Pero claro, si hubiera que computarlo llevaría mucho más tiempo que la primera solución. Y la gran mayoría de casos no van a ser tan enrevesados como este. Así que, aunque muy de vez en cuando podamos toparnos con un ejemplo así, el ahorro de tiempo que obtenemos de todos aquellos otros casos que sean más directos hacen que merezca la pena.

Pero es que además... ¿Y si te dijera que hay algoritmos voraces que siempre proporcionan una solución óptima?

Algoritmos voraces óptimos

Hay ciertos problemas que, aunque a primera vista parecen complejos de abordar, pueden resolverse usando una estrategia voraz, obteniendo siempre la mejor solución. En este tema estudiaremos tres de los más populares: el problema del cambio de monedas, el problema de la mochila fraccional y el problema de selección de actividades. En el próximo tema (voraces sobre grafos) veremos más algoritmos que se aplican directamente sobre grafos.

Algoritmos voraces

Cambio de monedas

El problema del cambio de monedas es probablemente el más sencillo de los tres conceptualmente. El objetivo consiste en hallar el mínimo número de monedas (o billetes) de distintas denominaciones necesarias para sumar una determinada cantidad.

Por ejemplo, en el euro, tenemos monedas de 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02 y 0.01 euros. Para obtener 2.68€ usando la menor cantidad de monedas posible seguimos estos pasos:

1. Escoger la moneda/billete de valor más alto, pero que sea igual o inferior a la cantidad objetivo.

2. Tomar la moneda y restar su valor a la cantidad objetivo.

3. Repetir el proceso hasta llegar a cero.

Con estos pasos, la secuencia con 2.68€ quedaría...

• 2.68€ | moneda más alta: 2€ | quedan 0.68€

• 0.68€ | moneda más alta: 0.50€ | quedan 0.18€

• 0.18€ | moneda más alta: 0.10€ | quedan 0.08€

• 0.08€ | moneda más alta: 0.05€ | quedan 0.03€

• 0.03€ | moneda más alta: 0.02€ | queda 0.01€

• 0.01€ | moneda más alta: 0.01€ | quedan 0€.

• FIN DEL ALGORITMO

A continuación, veamos la implementación en código:

​x
def greedy_coins(value, coins):

    solution = [0] * len(coins)

    for i in range(len(coins)):
        coin = coins[i]
        if value >= coin:
            count = value // coin
            solution[i] = count
            value -= count * coin

    return solution

value es el valor objetivo, mientras que coins es la lista de denominaciones que podemos usar, ya ordenada de mayor a menor. La lista solution contiene el número de monedas que se necesitan de cada denominación en relación a la lista coins (por ejemplo: para el caso superior, 2.68€, el array quedaría [1, 0, 1, 0, 1, 1, 1, 1]).

Es prácticamente el proceso que ya hemos descrito más arriba con una pequeña mejora: en los casos donde se requieren varias monedas de una misma denominación, primero calculamos el número de monedas de la denominación en la iteración actual (variable count) en vez de usar una iteración por cada moneda.

Applet interactivo: ¿Aún tienes dudas? ¿Quieres probar con tus propias denominaciones? ¡Prueba el applet interactivo del cambio de monedas!

https://algoritmos.neocities.org/applets/coins/

Aunque no lo tendrás que tener en cuenta en los ejercicios de este tipo, es muy importante indicar que esta implementación voraz solo funciona dando la solución óptima en el caso de divisas canónicas. En otras palabras, cada denominación debe tener valor igual o superior al doble de la denominación inmediatamente inferior para que el algoritmo funcione. Esta condición la cumplen prácticamente todas las divisas en circulación, pero hay algunos casos históricos en los que esto no era el caso, como la libra esterlina no decimal:

La libra esterlina no decimal contaba con, entre otras, denominaciones de 1, 3, 6, 12, 24, 30 y 60 peniques. El problema radica específicamente en las monedas de 24 y 30, ya que 30 es inferior al doble de 24. Esto causa problemas con valores objetivo como 48 peniques: un algoritmo voraz eligiría primero la moneda de 30, después la de 12 y finalmente la de 6. Pero en este caso, la solución óptima es de dos monedas de 24 peniques.

Mochila fraccional

En el problema de la mochila (llamado knapsack en inglés) dado un conjunto de ítems, donde cada uno tiene asociado un peso (o coste) y un valor, el objetivo consiste en determinar qué ítems se deben seleccionar para que el peso o coste total no exceda un límite establecido, manteniendo el valor total lo más alto posible. El nombre hace alusión a una mochila que hay que llenar con objetos sin sobrepasar un límite de peso, pero puede aplicarse a infinidad de situaciones (comprar objetos dentro de un presupuesto máximo, visitar ciudades en coche con un límite de combustible, realizar tareas dentro de un tiempo establecido, etc.).

El problema de la mochila se divide en dos tipos principales:

• Si debes tomar o dejar el ítem en su totalidad, sin la posibilidad de tomar una parte fraccionaria, entonces se trata del problema de la mochila discreta (o mochila 0-1) y no se puede resolver de forma óptima usando un algoritmo voraz. Sin embargo, sí que se puede resolver mediante una estrategia de vuelta atrás, y lo estudiarás en el tema correspondiente.

• Si puedes tomar parte del ítem, entonces se trata del problema de la mochila fraccional (o continua), y sí puede resolverse de forma óptima mediante un algoritmo voraz. Este es el que estudiaremos a continuación.

Cuando podemos seleccionar una parte fraccionaria de cualquier ítem, el problema se simplifica enormemente ya que únicamente hay que seguir estos pasos, ejemplificado con una mochila real:

1. Ordenar los ítems disponibles por su relación valor/peso en orden descendente.

2. Tomar el primer ítem de la lista. Si cabe entero dentro de la mochila, seleccionarlo al completo (junto a su valor íntegro), y restar su coste al límite de peso.

3. Repetir el paso 2 con cada elemento de la lista ordenada. Al llegar al punto en el que el peso del siguiente ítem es mayor al peso disponible restante, tomar la fracción (y su valor) proporcional al espacio disponible en la mochila.

4. La mochila está llena, con el valor máximo posible. FIN DEL ALGORITMO.

Como puedes ver es un problema bastante sencillo también, donde sobre todo deberás tener cuidado al calcular la parte fraccionaria del valor del último objeto introducido. Fíjate en la implementación en código Python de la parte inferior:

xxxxxxxxxx
def greedy_knapsack(items, capacity):

    items = sorted(items, key=lambda x: x[0] / x[1], reverse=True)
    solution = []
    total_value = 0.0

    for value, weight in items:
        # Caso 1: Si ya no queda espacio en la mochila
        if capacity == 0:
            break
            
        # Caso 2: Si el ítem cabe completamente en la mochila
        if weight <= capacity:
            solution.append(1.0)
            total_value += value
            capacity -= weight
            
        # Caso 3: Si el ítem solo cabe parcialmente
        else:
            fraction = capacity / weight
            solution.append(fraction)
            total_value += value * fraction
            break

    return solution, total_value

items es una lista donde cada entrada consiste en un pareado valor/coste, mientras que capacity es el peso/coste total máximo. el array solution contiene, para cada uno de los elementos ordenados por su relación valor/peso, la cantidad tomada de ese objeto (1 si se ha tomado en su totalidad, o un decimal entre 0 y 1 correspondiente a la parte fraccionaria).

En algunos ejercicios la lista items contendrá entradas de tres elementos (nombre, valor y coste, no necesariamente en ese orden) y por tanto habrá que modificar ligeramente la instrucción sorted para que realice la ordenación con los elementos adecuados. Además, si nos piden devolver una lista con los nombres de los elementos tomados, por ejemplo, también será necesario cambiar los solution.append para que añadan la información que nos interesa.

Applet interactivo: ¿Aún tienes dudas? ¿Quieres probar con tu propia mochila e ítems personalizados? ¡Prueba el applet interactivo de la mochila fraccional!

https://algoritmos.neocities.org/applets/knapsack/

Selección de actividades

El objetivo de el problema de selección de actividades es el de seleccionar la mayor cantidad posible de actividades, cada una con una hora de inicio y de fin, dentro de un intervalo de tiempo. En este problema asumimos que no es posible realizar dos actividades al mismo tiempo, por lo que las actividades seleccionadas no pueden solaparse.

La mayoría de problemas de selección de actividades giran en torno a problemas de planificación de horarios.

Aunque a primera vista pueda parecer que el problema requiere muchos pasos para obtener la mejor solución, este es, de hecho, uno de los problemas más representativos que pueden resolverse de forma óptima mediante un algorimo voraz. Los pasos a seguir son los siguientes:

1. Ordenar todas las actividades cronológicamente por hora de finalización.

2. Añadir la primera actividad de la lista ya ordenada (aquella que finalice antes que todas las demás). Llevar la cuenta de la última hora de finalización.

3. Para todas las demás actividades de la lista, si su hora de inicio es igual o posterior a la última hora de finalización, añadirla a la lista de actividades seleccionadas, y actualizar la última hora de finalización con la de dicha actividad.

4. Cuando se haya iterado por toda la lista, se habrá seleccionado la mayor cantidad posible de actividades. FIN DEL ALGORTIMO.

A continuación se muestra la implementación del código en Python:

xxxxxxxxxx
def activity_select(activities):

    activities = sorted(activities, key=lambda x: x[2])

    # Seleccionar la primera actividad
    selection = [[activities[0][0], activities[0][1], activities[0][2]]]
    last_finish = activities[0][2]

    # Ir añadiendo el resto de actividades (el [1:] es para comenzar desde el índice 1)
    for name, start, finish in activities[1:]:
        if start >= last_finish:
            selection.append([name, start, finish])
            last_finish = finish

    return selection

Este código asume que, en la lista activities, cada entrada está compuesta por tres elementos: el nombre de la actividad, su hora de inicio y su hora de finalización. De la misma forma, la lista solución selection contiene cada actividad con sus tres elementos (nombre, inicio, fin). El código se puede adaptar fácilmente para, por ejemplo, solo guardar el nombre de la actividad:

xxxxxxxxxx
selection = [activities[0][0]]
(...)
selection.append(name)