Die Region Zuordnungsproblem

Question

Ich bin mit Povray Bilder über einen Cluster zu machen. Jeder Arbeiter Knoten wird ein Teilbild zu machen. Das Thema dieser Frage ist es, einen geeigneten Teilungsalgorithmus zu finden.

Povray machen Pixel für Pixel. Aber jedes Pixel hat eine einzigartige Komplexität und so ist es eine unterschiedliche Menge an Zeit in Anspruch nimmt, es zu machen.

geteilt ich das Bild in vielen Regionen. Beispielsweise 2x2 Bildpunkte Regionen. Und einige dieser Regionen gemacht. Die Komplexität dieser Regionen wirkt sich auf die Komplexität der umgebenden Bereiche und so die ganze Reihe von Regionen mit einem Komplexitätswert gefüllt ist.

Ich teile ein Bild in Regionen. Jede Region definiert:

• Starten Spalte endet Spalte.
• Starten Zeile endet Reihe.
• Die Komplexität dieser Zone.

Das Ziel ist es, eine Liste von Jobs, die zu erstellen, wenn Abdeckungen fusionieren die alle Regionen. Die Arbeitsplätze sollten ähnliche Komplexität haben.

Jeder Job definiert:

• Starten Spalte endet Spalte.
• Starten Zeile endet Reihe.

Contrains:

• Eine gültige Makroregion für einen Job in Form eines Rechtecks ??oder quadratisch.
• Die Anzahl der Jobs ist N.

Answer 1

Vielen Dank für Ihre Frage zu aktualisieren.

Als alternative Strategie, könnten Sie eine Master-Slave-Anordnung haben, bei denen Arbeitnehmer für einen Job von einem Chef Prozess fragen, machen die Arbeit, und dann für mehr Arbeit fragen. Die Chef Hände kleine Fragmente von Arbeit, bis keine Arbeit bleibt. Der Vorteil dieser Strategie ist, dass, sofern die Arbeitsplätze klein genug gewählt werden (zum Beispiel 2x2 Pixelquadrate) alle Arbeiter beschäftigt, bis sehr nahe am Ende gehalten werden, und Sie vermeiden die Notwendigkeit zu vorher expliziten Schätzungen der Region Komplexität zu berechnen.

Answer 2

Der Algorithmus, dass ich verwende, schließlich ist recht komplex und ineffizient, so dass ich für die nächsten Antworten offen bin.

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