Проблема присвоения региона

Question

Я использую Povray для рендеринга изображений через кластер.Каждый рабочий узел собирается визуализировать частичное изображение.Предметом этого вопроса является поиск подходящего алгоритма расщепления.

Povray рендерит пиксель за пикселем.Но каждый пиксель имеет уникальную сложность, поэтому для его рендеринга требуется разное время.

Я разделил изображение на несколько областей.Например, области 2x2 пикселей.И оказали некоторые из этих регионов.Сложность этих областей влияет на сложность окружающих областей, поэтому весь массив областей заполняется значением сложности.

Я делю изображение на регионы.Каждый регион определяет:

• Начальный столбец, конечный столбец.
• Начальный ряд, конечный ряд.
• Сложность этой зоны.

Цель состоит в том, чтобы создать список заданий, которые при объединении охватывают все регионы.Задания должны иметь аналогичные сложности.

Каждое задание определяет:

• Начальный столбец, конечный столбец.
• Начальный ряд, конечный ряд.

Contrains:

• Допустимый макрорегион для задания в форме прямоугольника или квадрата.
• Число рабочих мест - N.

Answer 1

Спасибо за обновление вашего вопроса.

В качестве альтернативной стратегии у вас может быть соглашение о подчиненном, в котором работники просят работу у начальника, выполняют работу, а затем просят больше работы.,Босс раздает небольшие фрагменты работы, пока не останется работы.Преимущество этой стратегии заключается в том, что при условии, что задания выбираются достаточно маленькими (например, квадраты 2x2 пикселя), все работники будут заняты до самого конца, и вы избегаете необходимости заранее рассчитывать явные оценки сложности региона.

Answer 2

Алгоритм, который я окончательно использовал, довольно сложен и неэффективен, поэтому я открыт для следующих ответов.

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