区域分配问题

Question

我正在使用Povray在集群上渲染图像。每个工作节点将呈现部分图像。这个问题的主题是找到一个合适的分裂算法。

Povray逐像素渲染。但是每个像素都具有独特的复杂性，因此需要不同的时间来渲染它。

我在很多地区划分了图片。例如，2x2像素区域。并呈现其中一些区域。这些地区的复杂性影响了周边地区的复杂性，因此整个地区都充满了复杂性价值。

我在区域中划分图像。每个区域定义如下：

• 开始列，结束列。
• 开始行，结束行。
• 该区域的复杂性。

目标是创建合并时覆盖所有区域的作业列表。这些工作应该有类似的复杂性。

每个职位定义：

• 起始列，结束列。
• 开始行，结束行。

Contrains：

• 为作业的有效宏区域是矩形或正方形的形式。
• 作业的数量是N.

Answer 1

感谢您更新的问题。

作为一种替代策略，你可以有一个主从安排，在这种安排中，工人从老板的工作流程中寻找工作，做好工作，然后要求更多的工作。老板递出一小段工作，直到没有工作。这种策略的优势在于，只要工作选择得足够小（例如2x2像素方块），所有工作人员都将保持忙碌，直到非常接近尾声，并且避免了事先计算明确的地区复杂度估计值的需要。

Answer 2

，我终于用是相当复杂和低效的算法，所以我打开下一个答案。

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