Voracidad y optimizaci¨®n

En su periplo peninsular de la semana pasada, si Pap¨¢ Noel pudiera ir desde Madrid a cualquier otra de las comunidades aut¨®nomas tendr¨ªa, en su primer desplazamiento, 14 posibilidades distintas, y desde cualquiera de ellas podr¨ªa ir a cualquiera de las 13 restantes, y as¨ª sucesivamente, por lo que los itinerarios posibles ser¨ªan 14 x 13 x 12¡­ = 14! = 87.178.291.200; un n¨²mero demasiado elevado, incluso para el superpoderoso Pap¨¢ Noel, como para comparar entre s¨ª todos los itin...

En su periplo peninsular de la semana pasada, si Pap¨¢ Noel pudiera ir desde Madrid a cualquier otra de las comunidades aut¨®nomas tendr¨ªa, en su primer desplazamiento, 14 posibilidades distintas, y desde cualquiera de ellas podr¨ªa ir a cualquiera de las 13 restantes, y as¨ª sucesivamente, por lo que los itinerarios posibles ser¨ªan 14 x 13 x 12¡­ = 14! = 87.178.291.200; un n¨²mero demasiado elevado, incluso para el superpoderoso Pap¨¢ Noel, como para comparar entre s¨ª todos los itinerarios en busca del m¨¢s corto.

El n¨²mero de itinerarios se reduce dr¨¢sticamente si, como parece razonable, el trineo va desde cada comunidad a una de las lim¨ªtrofes, lo que supone ir desde Madrid a una de las dos Castillas, y si Pap¨¢ Noel elige Castilla-La Mancha luego tiene cinco posibilidades, y luego otras dos si eligiera Andaluc¨ªa¡­ El n¨²mero de itinerarios ser¨ªa 2 x 5 x 2¡­, muy por debajo del indiscriminado 14 x 13 x 12¡­

Pero Pap¨¢ Noel podr¨ªa reducir sus opciones a una, muy razonable, si desde cada comunidad viajara a la m¨¢s pr¨®xima (de las a¨²n no visitadas): de Madrid a Toledo, de Toledo a M¨¦rida, de M¨¦rida a Sevilla¡­ De este modo estar¨ªa aplicando un ¡°algoritmo voraz¡±.

En?ciencias de la computaci¨®n, un?algoritmo voraz?(tambi¨¦n conocido como?glot¨®n,?¨¢vido,?devorador?o?greedy) es una estrategia de b¨²squeda que consiste en elegir la mejor opci¨®n en cada paso del proceso con la esperanza de obtener la mejor soluci¨®n global. Los algoritmos voraces se utilizan generalmente para resolver problemas de optimizaci¨®n, y las decisiones se toman en funci¨®n de la informaci¨®n -o la valoraci¨®n- que se maneja en cada momento. Suelen ser r¨¢pidos y f¨¢ciles de utilizar, pero no siempre llevan a la soluci¨®n ¨®ptima.

Por ejemplo, en el caso que nos ocupa, el algoritmo voraz le ofrece a Pap¨¢ Noel un buen itinerario, pero no el mejor (es decir, el m¨¢s corto), pues el criterio de ir de cada comunidad a la m¨¢s pr¨®xima lo llevar¨ªa de Valencia a Zaragoza, cuando una soluci¨®n mejor ser¨ªa ir antes a Barcelona para seguir el circuito esquematizado en la figura.

Por cierto, a mis sagaces lectoras/es no se les habr¨¢ escapado que el circuito m¨¢s corto parece ser, parad¨®jicamente, el que encierra una superficie mayor. ?Es realmente as¨ª? ?Por qu¨¦?

Para este itinerario -o cualquier otro- el tiro del trineo puede formarse, de forma que detr¨¢s de Rudolph vayan cuatro parejas heterosexuales, de 9.216 maneras distintas (4! x 4! x 2?).

Un saltamontes y dos sucesiones

Y de los renos voladores a los saltamontes invisibles, pues en la secci¨®n de comentarios de la semana pasada se mencion¨® un interesante problema que sigue sin resolver en el momento de escribir estas l¨ªneas:

Hay un saltamontes invisible en un punto entero de la recta real. El saltamontes se desplaza a saltos o bien a derecha o bien a izquierda, una cantidad entera cada segundo. Podemos intentar ¡°cazar¡± al saltamontes situ¨¢ndonos cada segundo en un punto entero de la recta. ?Hay alguna estrategia que nos permita cazar tarde o temprano al saltamontes invisible?

Y puesto que estrenamos nuevo a?o, no est¨¢ de m¨¢s echarle una ojeada al n¨²mero 2022. ?Detectan en ¨¦l alguna propiedad interesante mis sagaces lectoras/es?

Y un par de sencillas sucesiones para terminar el a?o sin esforzarse demasiado:

2000, 2002, 2020, 2022¡­

62, 138, 262, 446¡­

?Cu¨¢les son los siguientes n¨²meros?

Carlo Frabetti es escritor y matem¨¢tico, miembro de la Academia de Ciencias de Nueva York. Ha publicado m¨¢s de 50 obras de divulgaci¨®n cient¨ªfica para adultos, ni?os y j¨®venes, entre ellos ¡®Maldita f¨ªsica¡¯, ¡®Malditas matem¨¢ticas¡¯ o ¡®El gran juego¡¯. Fue guionista de ¡®La bola de cristal¡¯.

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.