Проблема назначения региона

Question

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

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

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

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

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

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

Каждая работа определяет:

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

Согласно:

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

Answer 1

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

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

Answer 2

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

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