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?