El problema de asignación región

Question

Estoy usando Povray para representar imágenes más de un clúster. Cada nodo trabajador va a hacer que una imagen parcial. El objeto de esta pregunta es encontrar un algoritmo de división adecuado.

Povray render pixel por pixel. Pero cada píxel tiene una complejidad única y por lo tanto se necesita una cantidad diferente de tiempo para rendirlo.

Me divide la imagen en muchas regiones. Por ejemplo, 2x2 píxeles regiones. Y rendido algunas de estas regiones. La complejidad de estas regiones afecta a la complejidad de las regiones circundantes y así todo el conjunto de regiones se llena con un valor de complejidad.

Me dividir una imagen en regiones. Cada región define:

• A partir de la columna, la columna final.
• A partir fila, terminando fila.
• Complejidad de esa zona.

El objetivo es crear una lista de trabajos que, cuando se fusionó cubiertas todas las regiones. Los trabajos deben tener complejidades similares.

Cada uno define de empleo:

• A partir de la columna, la columna final.
• A partir fila, terminando fila.

Contrains:

• Una macro-región válida para un trabajo es en la forma de un rectángulo o cuadrado.
• El número de empleos es N.

Answer 1

Gracias por la actualización de su pregunta.

Como una estrategia alternativa, que podría tener un acuerdo maestro-esclavo en el que los trabajadores piden un trabajo de un proceso jefe, hacer el trabajo, y luego piden más trabajo. Las manos fuera jefe pequeños fragmentos de la obra hasta que no quede de trabajo. La ventaja de esta estrategia es que proporcionó los puestos de trabajo son elegidos suficientemente pequeño (por ejemplo 2x2 píxeles cuadrados) todos los trabajadores se mantendrán ocupado hasta muy cerca del final, y que evitan la necesidad de calcular estimaciones explícitas de la región de la complejidad de antemano.

Answer 2

El algoritmo que finalmente he utilizado es bastante compleja e ineficiente, por lo que estoy abierto para los próximos respuestas.

https://gist.github.com/gists/729677