Algoritmos voraces

Nuestro Caballero Negro de la semana pasada se pasó de listo al no contemplar sino la posibilidad más obvia: dividir por 2 el número dicho por el guardia. No se dio cuenta de que en las parejas 24-12, 8-4 y 18-9, el segundo número no solo es la mitad del primero, sino que además indica su número de letras; por lo tanto, para entrar en el castillo, cuando el guardia le dijo “Cuatro” tendría que haber contestado “Seis”.

A partir de este acertijo, se propusieron algunos más relacionados con el binomio numerar/nombrar, uno de ellos vinculado al algoritmo de Kruskal (ver la correspondiente sección de comentarios), que es un ejemplo de “algoritmo voraz”: un expeditivo método para resolver problemas complejos de forma relativamente simple, aunque no necesariamente óptima.

Lo que intuitivamente haría el viajero sería partir de la capital que más le conviniera e ir desde allí a la más próxima

Imaginemos que un viajero desea recorrer las ocho capitales de provincia andaluzas y quiere hacerlo siguiendo el recorrido más corto. En principio, puede iniciar su viaje partiendo de cualquiera de las ocho capitales, ir luego a cualquiera de las siete restantes, de ahí a cualquiera de las seis que quedan y así sucesivamente, por lo que el número total de recorridos posibles es 8 x 7 x 6 x 5 x 4 x 3 x 2, o sea 8! (factorial de 8): 40.320. Medirlos todos para ver cuál es el más corto sería extremadamente largo y tedioso, por lo que, en la práctica, lo que intuitivamente haría el viajero sería partir de la capital que más le conviniera e ir desde allí a la más próxima, desde esta a la más próxima a ella y así sucesivamente. De este modo no tendría la certeza de haber seguido el itinerario más corto posible, pero sí una buena aproximación.

Sin saberlo (a no ser que sea matemático o informático), nuestro viajero hipotético ha aplicado un algoritmo voraz: en cada paso ha elegido el objetivo más apetecible en ese momento (la ciudad más cercana) sin preocuparse de los pasos siguientes.

Las máquinas que devuelven cambio (y también las personas) suelen aplicar un algoritmo voraz tendente a minimizar el número de monedas utilizadas. Si compras algo que vale 1.30 euros y pagas con un billete de 5, es probable que te den los 3.70 de vuelta con una moneda de 2, una de 1, una de 50 cts. y una de 20, que consiste en ir eligiendo en cada paso la de mayor valor que no supera la cantidad a cubrir. En este caso, el algoritmo voraz optimiza la operación, pero podría no ser así. Si existieran monedas de 90 cts. y hubiera que devolver 1.80 euros, el algoritmo voraz elegiría una moneda de 1 euro, una de 50 cts., una de 20 y una de 10, cuando la solución óptima sería dos monedas de 90 cts.

No hay cambio

Veamos ahora un caso en el que no hay nada que optimizar porque, sencillamente, no hay cambio.

Las máquinas que devuelven cambio suelen aplicar un algoritmo voraz tendente a minimizar el número de monedas utilizadas

Un hombre intenta infructuosamente sacar tabaco de una máquina de un bar con una moneda, al parecer defectuosa, de 2 euros. Se dirige al camarero y le pregunta:

-¿Podría cambiarme esta moneda por otra de 2 euros?

-Lo siento, no tengo ninguna -contesta el camarero.

-Entonces, por favor, cámbiemela por otras monedas.

-Lo siento, no puedo.

El hombre rebusca en su bolsillo, encuentra una moneda de 1 euro y dice:

-Pues cámbieme esta moneda para telefonear, por favor.

-Lo siento, tampoco puedo cambiársela -contesta el camarero con un gesto de impotencia-. Y tampoco podría cambiarle una de 50 céntimos, ni una de 20, ni siquiera una de 10.

-¿Cómo es posible que no tenga ninguna moneda? -se asombra el cliente.

-No he dicho tal cosa -replica el camarero-. De hecho, tengo 2.35 euros en monedas.

¿Qué monedas tiene?