algorithm - una - ¿Cerrar puntos de embalaje en el plano?
como unir un tejido de dos agujas (3)
Es un problema de empaquetado de contenedores 2D (que es NP difícil) con restricciones adicionales. He escuchado que el recocido simulado funciona bastante bien para el diseño de circuitos / chips.
De hecho, estoy buscando datos de prueba reales de un gran problema de empaque de contenedores para Drools Planner .
Supongamos que tengo un gráfico G completo, no dirigido, con una distancia asociada a cada borde. El significado del borde (u, v) que tiene la longitud l es "los puntos u y v no pueden estar más cerca uno del otro que l". Mi objetivo es colocar los nodos de este gráfico en un plano para que no se infrinja ninguna de estas restricciones de distancia y para que el casco convexo de los puntos tenga el área menos total. Como ejemplo, supongamos que tengo un montón de componentes eléctricos que quiero colocar en un chip, cada uno de los cuales genera cierta cantidad de interferencia eléctrica. Si pongo los componentes demasiado juntos, comenzarán a interferir entre sí, haciendo que todo el sistema sea inútil. Teniendo en cuenta las distancias mínimas que cada punto debe tener entre sí, ¿cuál es la forma más eficiente de colocar los componentes en un chip?
No tengo ni idea de cómo empezar a pensar en esto. Tampoco sé cómo se podría generalizar el problema en el caso de dimensión superior (puntos de empaquetado en un hiperplano). ¿Alguien sabe de una buena manera de abordar este problema?
Supongo que será difícil encontrar el algoritmo óptimo. No me sorprendería si resultara ser un problema difícil de NP. Sin embargo, si está interesado en un algoritmo práctico que produzca soluciones decentes, recomiendo echar un vistazo a los algoritmos de dibujo de gráficos basados en la fuerza .
Aquí está la idea general (aparecerán algunas matemáticas superiores). Se generaliza a cualquier número de dimensiones.
Construya una función f que asigne un valor a cada diseño de nodo, un valor que desee minimizar. En su caso, la función podría calcular el área del casco convexo para un diseño dado + una gran penalización por cada restricción que no se cumplió. O podría ser una función g más simple que se aproxima razonablemente a la anterior: en resumen, queremos que g se reduzca cada vez que f haga más pequeña, y viceversa. Es bueno elegir una función relativamente simple, ya que tendrá que calcular sus derivadas parciales (con respecto a las coordenadas de los nodos).
Ahora digamos que tiene 100 nodos y desea colocarlos en 3D. Eso significa que tiene 300 números desconocidos (100 nodos por 3 coordenadas para cada nodo). La función f es una función de R 300 a R , e idealmente queremos encontrar su mínimo global. De manera más realista, bastará un mínimo local suficientemente profundo.
Hay algoritmos numéricos bien conocidos para encontrar tal mínimo, por ejemplo: Gradiente de conjugado , BFGS . Lo bueno es que no tienes que entenderlos en detalle, estos algoritmos están implementados en muchos idiomas. Todo lo que tiene que hacer es proporcionar un método para calcular f(x) y f''(x) para cualquier x solicitada por el algoritmo, y un diseño inicial x₀ .
Tengo una solución óptima, pero no te va a gustar :).
Etiquetemos nuestros nodos x 0 , x 1 , ..., x n . Sea B = max i, j <n (dist (x i , x j )), donde dist (x i , x j ) es la distancia mínima entre x i y x j . Para cada i, coloque el nodo x i en la posición (0, i * B). Ahora, cada nodo está al menos B alejado de todos los demás, y el casco convexo tiene área 0.
El punto real aquí es que minimizar el área del casco convexo solo le dará una solución sin sentido. Una medida posiblemente mejor sería el diámetro del casco convexo.