¿Por qué estos problemas geométricos son tan difíciles?

Me sorprendió saber que se han propuesto soluciones tanto para el problema del sofá en movimiento como para el empaquetamiento de 11 cuadrados , pero en cualquier caso, la optimización de la solución propuesta es, hasta el momento, solo una conjetura. A primera vista, estos problemas me parecen "inocentes", pero presumiblemente engañosamente. (Tenga la seguridad: no tengo ni idea de cómo acercarme a ninguno de ellos).

¿Cuál es la naturaleza del presunto obstáculo que debe tomarse aquí para probar la optimización? ¿Es el problema algún tipo de complejidad computacional que debe superarse, requiere alguna técnica que hasta el momento se desconoce, la optimización depende de algunas otras conjeturas, ...? ¿O es algo que no sabemos y no podemos saber hasta que realmente se haya hecho?

Me doy cuenta de que estos son dos problemas diferentes, pero pensé, quizás imprudentemente, ponerlos en una sola pregunta. Quizás compartan una dificultad que es compartida por muchos de estos problemas y aún es bastante específica para tales problemas.

Otras referencias: Problema del sofá en movimiento en Wikipedia , Problema del sofá en movimiento en MathWorld , Solución de Gerver al problema del sofá en movimiento (pdf) , Empaquetado de 11 cuadrados en MathWorld

Incluyo una imagen animada de Claudio Rocchini de (lamentablemente) una solución no óptima al primer problema. Solo porque se ve bien.

ingrese la descripción de la imagen aquí

Por lo general, los problemas como "¿Cuál es la mejor forma para X?" tienden a ser muy fáciles o muy difíciles. ¡Me sorprendió mucho saber lo rápido que se resolvió el problema de la curva de descenso más rápido !

Respuestas (1)

Esta es una respuesta inadecuada, pero...

Estos problemas son difíciles porque (a) el espacio de posibles soluciones es amplio, y (b) parece que la estructura es insuficiente para reducir el espacio de modo que la búsqueda sea factible.

Considera el problema de los 11 cuadrados. Cada cuadrado tiene una ubicación y una orientación, por lo que se puede precisar especificando tres parámetros. Entonces, 33 parámetros determinan una configuración de 11 cuadrados y, por lo tanto, determinan el cuadrado circundante. Pero esto significa que uno está, en cierto sentido, buscando en un espacio de 33 dimensiones la solución óptima.

Por supuesto, hay muchas limitaciones que hacen que este 33 sea una sobreestimación. (Por ejemplo, el primer cuadrado se puede restringir a, digamos, ( 0 , 0 ) − ( 1 , 1 ) , por lo que en realidad es "solo" un espacio de 30 dimensiones...) Pero cuando ve un empaque como el que se muestra a continuación (debido a Károly Hajba), su confianza en restringir los parámetros se tambalea.


     Embalaje cuadrado
     (Un embalaje de 51 cuadrados. Imagen de este enlace .)

(1) Excelente respuesta. (2) ¡Ese empaque de 51 cuadrados es bastante aterrador!
+1 Gracias. ¿No cree que hay una caracterización tipo topología de cualquier solución?
@aufkag: no estoy seguro de qué sería una "caracterización similar a una topología". En el problema de los cuadrados, ciertamente la no superposición de cualquier par de cuadrados conduce a restricciones algebraicas que tallan ese espacio de 33 dimensiones...
@JosephO'Rourke Lo que quiero decir es que la solución 51 (además de permitir inmediatamente 31 soluciones similares) parece tener un carácter claro de 18 (inclinado) -33 (recto). Eso parece estructura.
@aufkag: Bien, ya veo. Ciertamente, mientras busca, uno podría buscar k inclinado y norte − k recto, pero aún así uno presumiblemente tendría que verificar esto para cada k .
@JosephO'Rourke Se puede encontrar más estructura en (los recuentos de) los "tipos" de toques entre cuadrados. (No sabría si eso ayudaría, pero aún así).
@aufkag: Sin embargo, ni siquiera se sabe si esas soluciones son óptimas.
¿Por qué estos problemas geométricos son tan difíciles?
RespuestasAquíPolítica de privacidad1y, 0v