Voracidad y optimización | El distracción de la ciencia

En su viaje peninsular de la semana pasada, si Santa pudiera ir de Madrid a cualquier otra comunidad autónoma, tendría, en su primer viaje, 14 posibilidades distintas, y de cada una de ellas podría ir a una de las 13 restantes, y así sucesivamente. a partir de entonces, por lo tanto, los posibles itinerarios serían 14 x 13 x 12… = 14! = 87.178.291.200; un número demasiado alto, incluso para el muy poderoso Papá Noel, para comparar todos los itinerarios en busca del más corto.

El número de rutas se reduce drásticamente si, como parece razonable, el trineo va de cada comunidad a una de las comunidades vecinas, lo que supone ir de Madrid a una de las dos Castilla, y si Santa elige Castilla-La Mancha entonces tiene cinco posibilidades., y luego dos más si eliges Andalucía … El número de recorridos sería 2 x 5 x 2 …, muy por debajo de los indiscriminados 14 x 13 x 12 …

Pero Papá Noel podría reducir sus opciones a una, muy razonable, si pasara de cada comunidad a la más cercana (de las aún no visitadas): de Madrid a Toledo, de Toledo a Mérida, de Mérida a Sevilla … así. aplicaría un «algoritmo codicioso».

En informática, un algoritmo voraz (también conocido como codicioso, codicioso, devorador o …avaro) es una estrategia de investigación que consiste en elegir la mejor opción en cada etapa del proceso con la esperanza de obtener la mejor solución global. Generalmente se utilizan algoritmos voraces para resolver problemas de optimización, y las decisiones se toman en base a información -o evaluación- que se gestiona en todo momento. Suelen ser rápidos y fáciles de usar, pero no siempre conducen a la solución óptima.

Por ejemplo, en el caso que nos ocupa, el algoritmo voraz ofrece a Papá Noel un buen itinerario, pero no el mejor (es decir, el más corto), ya que el criterio de ir de cada comunidad a la más cercana lo llevaría de Valencia a Zaragoza, cuando un Una mejor solución sería ir primero a Barcelona para seguir el circuito que se indica en la figura.

Por cierto, mis astutos lectores no habrán escapado a que el circuito más corto parece ser, paradójicamente, el que engloba la mayor superficie. ¿Es realmente así? ¿Cómo?

Para este itinerario -o cualquier otro- se puede formar el equipo de trineos, de modo que cuatro parejas heterosexuales vayan tras Rodolfo, de 9.216 formas distintas (4! X 4! X 2⁴).

Un saltamontes y dos secuencias.

Y de renos voladores a saltamontes invisibles, porque la sección de comentarios de la semana pasada mencionó un problema interesante que sigue sin resolverse al momento de escribir:

Hay un saltamontes invisible en todo un punto de la línea real. El saltamontes salta hacia la izquierda o hacia la derecha, un número entero cada segundo. Podemos intentar «cazar» al saltamontes colocándonos cada segundo en un punto completo de la línea. ¿Existe una estrategia que nos permita cazar al saltamontes invisible tarde o temprano?

Y dado que estamos lanzando el nuevo año, vale la pena echarle un vistazo al ángel número 2022. ¿Mis lectores astutos están detectando propiedades interesantes en él?

Y un par de secuencias simples 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 trabajos de divulgación científica para adultos, niños y jóvenes, entre los que se encuentran «Physical Damn», «Damn Math» o «The Big Game». Fue guionista de «La bola de cristal».

puedes seguir PREGUNTA en Facebook, Gorjeo Y Instagram, o regístrese aquí para recibir nuestro boletín semanal.