los problemas de acumulación revisited

Question

Estoy desarrollando un juego y me encontré con un problema que tiene que resolver para manejar el diseño de un componente que se me parece un problema de embalaje.

Para resumir lo que necesito hacer suponer Tengo un espacio similar al siguiente:

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

en la que cada celda de la esquina es 4x4, mientras que uno central es 3x3 (de modo que las restantes son de 3x4 y 4x3). Entonces tengo un conjunto de elementos a cabo dentro de estos bloques que pueden variar de 1x1 a 3x3 (no creo que se necesita ningún 4x4 sin embargo, pero no debería cambiar nada). Por supuesto, estos elementos no pueden cruzar las líneas y deben poner enteramente dentro de un solo bloque.

¿Cuál podría ser la mejor manera de asignar ellos? Suponiendo que prefiero no tener a todos ellos stickied juntos si no es necesario (por ejemplo. No coloque dos elementos juntos si hay suficiente espacio alrededor para colocarlos aparte). Estoy buscando un simple algoritmo, también porque la situación es bastante limitado ..

Bono pregunta: suponiendo que otros bloques además de estos 9 (tal vez otro 3-4) ¿cómo podría dar prioridad a éstas en comparación con las otras nuevas? (Me refiero simplemente no utilizar el bloque adicional hasta que se haya alcanzado un umbral de llenado) ..

Por supuesto que estoy buscando la idea general, sin aplicación:)

Answer 1

Esta 2D Bin Packing miradas problemas como si fuera NP duro .

Aquí hay un par de opciones:

• La fuerza bruta o mejor aún rama y encuadernado. No escala (en absoluto!), Pero va a encontrar la solución óptima (no en nuestra vida tal vez).

• algoritmo determinista: ordenar los bloques en tamaño más grande o lado mayor y pasar por esa lista uno por uno y asignarle el mejor lugar restante. Que acabará muy rápido, pero la solución puede estar lejos de ser óptimo (o posible). He aquí una buena foto que muestra un ejemplo de lo que puede salir mal. Pero si quieres que sea sencillo, que es el camino a seguir.

• Meta-heurística, a partir del resultado de un algoritmo determinista. Esto le dará un muy buen resultado en un tiempo razonable, mejor que lo que los humanos ocurra. Dependiendo de la cantidad de tiempo que le des y la dificultad del problema que puede o no ser la solución óptima. Hay un par de bibliotecas por ahí, como Drools Planificador (Java de código abierto).