¿Se ha estudiado antes el siguiente problema? En caso afirmativo, ¿qué enfoques / algoritmos se desarrollaron para resolverlo?
Problema ("Problema de altura máxima de apilamiento")
Dados polígonos, encuentre su disposición estable y no superpuesta que maximice su altura de apilamiento en un piso fijo bajo la influencia de la gravedad.
Ejemplo
Tres polígonos:
y tres de sus infinitos arreglos estables, no superpuestos, con diferentes alturas de apilamiento:
Aclaraciones
- Todos los polígonos tienen masa uniforme e igual densidad.
- La fricción es cero
- La gravedad está actuando en cada punto en la dirección hacia abajo (es decir, los vectores de fuerza son todos paralelos)
- Una configuración no se considera estable si descansa sobre un punto de equilibrio inestable (por ejemplo, el triángulo verde en las imágenes no puede equilibrarse en ninguno de sus vértices, incluso si la masa a la izquierda y a la derecha del punto de equilibrio es igual)
- Para aclarar aún más el punto anterior: Un polígono se considera inestable ("volcarse") a menos que descanse en al menos un punto estrictamente a la izquierda y al menos un punto estrictamente a la derecha de su centro de gravedad (esta definición simplifica enormemente la simulación y en particular, hace innecesaria la integración de la posición, etc. con el fin de evaluar si una disposición es estable o no.
- El problema en su forma "física" es un problema continuo que solo puede resolverse aproximadamente en la mayoría de los casos. Para obtener un problema discreto que pueda abordarse algorítmicamente, restrinja tanto los vértices del polígono como su ubicación en la disposición a redes adecuadas.
Notas
- Los enfoques de fuerza bruta de cualquier tipo son claramente inviables. Incluso con restricciones estrictas en la colocación de polígonos dentro de la red (como proporcionar un "espacio de red" de región limitada) la complejidad simplemente explota por más de unos pocos polígonos.
- Los algoritmos iterativos deben aportar algunas heurísticas muy inteligentes, ya que es fácil construir arreglos donde la eliminación de un solo polígono da como resultado que la configuración se vuelva inestable y dichos arreglos son inalcanzables por algoritmos que dependen de que cada paso intermedio sea estable.
- Dado que el problema huele al menos NP- pero más probablemente EXPTIME-complete en el número total de vértices, incluso la heurística sería de considerable interés. Una cosa que da esperanza es el hecho de que la mayoría de los humanos reconocerán que la tercera disposición en el ejemplo es óptima.
Respuestas:
Si bien no conozco ningún algoritmo específico para este problema, podría abordarlo en un método bastante eficiente dividiéndolo en partes separadas.
Comenzaría por encontrar la rotación para cada forma individual que proporcione una altura máxima mientras mantiene una orientación de equilibrio válida (es decir, no en un punto como con el triángulo). Si una forma tiene varias alturas iguales, iría con la configuración que da la mayor área de superficie encima. Una vez que tenga esto, puede descubrir cómo apilar mejor cada objeto en una mansión que pueda equilibrarse.
fuente