MIT Los ordenadores de hoy no saben empaquetar
Los ordenadores de hoy en día aún no están listas para una pregunta común en las fiestas: cómo eliminar las cookies con el menor desperdicio posible.
Incluso los expertos en matemáticas han renunciado a encontrar un algoritmo informático para responder a este tipo de problema geométrico , que también podría aplicarse a hacer la maleta o llenar un espacio de cocina mientras se aprovecha al máximo el espacio.
El profesor asistente Mikkel Abrahamsen del departamento de informática de la University of Copenhagen – University of Copenhagen (ku.dk) y dos colegas investigadores 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 informáticos han solucionado durante décadas.
los ordenadores de hoy no saben solucionar cosas fáciles
“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 aumentará mucho por el momento ”, explica Abrahamsen.
Empaquetar 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 marítimo, se aplica al embalaje de contenedores.
los ordenadores de hoy no saben solucionar cosas fáciles
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 mantener el ritmo. Teóricamente es posible. Pero según la velocidad a la que crece la potencia informática, probablemente pasarán millones de años antes de que podamos optimizar el manejo de algunos objetos adicionales «.
Además, si uno está trabajando con formas más complicadas , como el pan de jengibre en forma de árbol de Navidad, Abrahamsen dice que las soluciones óptimas solo se pueden encontrar para hasta cuatro objetos hoy.
¿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 que nosotros en matemáticas llamamos 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.
los ordenadores de hoy no saben solucionar cosas fáciles
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 empaquetar 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, por el momento”, concluye Abrahamsen.
Los investigadores presentaron el estudio en FOCS 2020 (Simposio IEEE sobre fundamentos de la informática). Investigadores adicionales de la Universidad de Copenhague, la Universidad de Utrecht en los Países Bajos y la Freie Universität Berlin en Alemania.
Otros Reportajes:
MIT, Impacto extracción de minerales en aguas profundas Revista NUVE
MIT, nuevas pistas sobre la enfermedad de Parkinson Revista NUVE