El siempre difícil acertijo: ¿Cuál es la mejor manera de cortar las galletas navideñas?

En algún momento de la vida, la mayoría de la gente se ha parado sobre una losa de masa para galletas y se ha preguntado cuál es la mejor manera de cortar las galletas con el menor desperdicio posible. Ahora, incluso los expertos en matemáticas han renunciado a encontrar un algoritmo informático que responda a este tipo de problema geométrico.

¿Cómo podemos maximizar la masa mientras cortamos las galletas navideñas? ¿Cómo empacamos una maleta o llenamos un mueble de cocina aprovechando al máximo el espacio? Uno puede haber pensado, “debe haber una mejor manera de hacer esto”. Reflexionar sobre estas cuestiones con demasiada profundidad parece ahora una completa pérdida de tiempo. La ciencia ahora está aquí para respaldar que es imposible, por el momento, averiguar qué funciona mejor para más de cuatro o cinco hombres de pan de jengibre picantes o galletas de árbol de Navidad.

El profesor asistente Mikkel Abrahamsen del Departamento de Ciencias de la Computación y dos colegas de investigación estudiaron lo difícil que es descubrir la forma óptima de empaquetar objetos en dos dimensiones sin superposición, un enigma que los científicos de la computación han solucionado durante décadas.

“Si bien los algoritmos nos permiten resolver problemas muy complejos, este sigue siendo demasiado complicado para las computadoras de hoy. Por ahora, no es posible empaquetar más de 5-10 objetos de manera óptima. Y nuestro resultado sugiere que este número probablemente no aumente mucho por el momento “, explica Mikkel Abrahamsen.

Empacar las cosas de manera óptima no es solo un problema ocasional en el hogar, sino en una variedad de industrias, incluida la fabricación de ropa y el procesamiento de metales. En cada caso, es importante cortar los materiales con el menor desperdicio posible. En el transporte, se aplica al embalaje de contenedores.

Solo cuatro galletas de jengibre

Conocemos el tamaño del contenedor cuadrado más pequeño en el que podemos embalar hasta 10 palets cuadrados de 1×1 metro. Pero simplemente agregando un palé adicional, se vuelve imposible calcular el tamaño óptimo del contenedor. Abrahamsen explica:

“A medida que se agregan más paletas, el tiempo de cálculo aumenta exponencialmente. Ni siquiera las mejores computadoras pueden mantenerse al día. Teóricamente es posible. Pero según la velocidad a la que aumenta la potencia informática, probablemente pasarán millones de años antes de que podamos para optimizar el manejo de algunos objetos adicionales “.

Además, si uno está trabajando con formas más complicadas, como un pan de jengibre en forma de árbol de Navidad, Mikkel Abrahamsen dice que las soluciones óptimas solo se pueden encontrar para hasta cuatro objetos en la actualidad.

Infinidad de opciones

¿Qué lo hace tan difícil? Abrahamsen explica que el problema es similar a resolver ecuaciones de grado cinco o superior, y con muchas incógnitas. Aquí, se sabe que tal solución no siempre se puede escribir usando operaciones aritméticas regulares.

“Nuestro estudio demuestra que el problema tiene una naturaleza a la que en matemáticas nos referimos como continuo, lo que en pocas palabras, significa que uno debe conocer todas las coordenadas en las que se pueden colocar las galletas y todos los ángulos en los que se pueden colocar. rotado “, explica Abrahamsen.

Como las combinaciones posibles son infinitas, no hay forma de crear una lista de todas las ubicaciones necesarias para probar para encontrar una solución de embalaje óptima. En cambio, los algoritmos que resuelven los problemas de empaquetado de manera óptima deben ser más analíticos, lo que requiere mucho tiempo. Esto contrasta con muchos otros problemas algorítmicos conocidos, en los que se puede probar un número limitado de combinaciones antes de encontrar una que sea óptima. Por tanto, los problemas de empaque son mucho más difíciles.

Entonces, en la práctica, no hay mejores soluciones para los problemas de empaque que las que podemos encontrar los humanos.

“Tanto en la industria como en el mostrador de la cocina, debemos seguir estando satisfechos con nuestras soluciones menos que óptimas y tener la seguridad de que los humanos seguimos siendo mejores que las computadoras para este tipo de tareas, o por el momento”, concluye Mikkel Abrahamsen.