Il problema assegnazione regione

Question

Sto usando Povray per rendere le immagini più di un cluster. Ogni nodo lavoratore sta per rendere un'immagine parziale. Il soggetto di questa domanda è quello di trovare un algoritmo di divisione adatto.

Povray rendere pixel per pixel. Ma ogni pixel ha una complessità unica e quindi richiede una diversa quantità di tempo per renderlo.

I diviso l'immagine in molte regioni. Ad esempio, 2x2 pixels regioni. E reso alcune di queste regioni. La complessità di tali regioni influisce sulla complessità delle regioni circostanti e quindi l'intera matrice di regioni è riempita con un valore complessità.

I dividere un'immagine in regioni. Ogni definisce regione:

• A partire colonna, che termina colonna.
• A partire fila, terminando fila.
• La complessità di quella zona.

L'obiettivo è quello di creare un elenco di lavori che, quando fuse copre tutte le regioni. I posti di lavoro devono avere complessità simili.

Ogni definisce di lavoro:

• A partire colonna, che termina colonna.
• A partire fila, terminando fila.

Contrains:

• Una macro-regione valida per un posto di lavoro è nella forma di un rettangolo o un quadrato.
• Il numero di lavori è N.

Answer 1

Grazie per l'aggiornamento alla tua domanda.

In una strategia alternativa, si potrebbe avere un accordo di master-slave in cui i lavoratori chiedono un processo da un processo di capo, fare il lavoro, e poi chiedere più lavoro. Le mani capo fuori piccoli frammenti di lavoro fino a che non rimane di lavoro. Il vantaggio di questa strategia è che ha fornito i posti di lavoro sono scelte abbastanza piccolo (ad esempio 2x2 pixel quadrati) tutti i lavoratori saranno tenuti occupati fino a poco verso la fine, e si evitano la necessità di calcolare le stime esplicite della regione di complessità in anticipo.

Answer 2

L'algoritmo che alla fine ho usato è abbastanza complessa e inefficiente, quindi sono aperti per i prossimi risposte.

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