Слияние соседних полигонов с равным суммарным значением атрибута

[nikpolit]

Давно уже задавали здесь такую задачу, но к решению так и не пришли. Есть сплошные полигоны с целочисленными значениями атрибута. Необходимо слить полигоны в меньшее число полигонов так, чтобы у новых больших полигонов было примерно равное суммарное значение атрибута.
Прилагаю картинку с изображением задачи.



Подскажите, пожалуйста, возможное решение или хотя бы свои мысли по этому поводу

[gamm]

задачка довольно стандартная (так, например, в штатах формируют избирательные округа из переписных кварталов). Но постановка задачи слишком мутная, поскольку должны быть заданы критерии оптимальности - число или площадь итоговых полигонов, компактность (например близость к окружности или квадрату), желаемая сумма значений, и т.д., иначе тривиальным решением является объединение всех полигонов в один. Еще многое в методе решения зависит от числа исходных полигонов.

Решения однозначного у таких задач обычно нет, и решаются они стохастическим методом типа artificial annealing. Начальное приближение строится исходя из критерия оптимальности, а потом поехали перекидывать полигончики соседям. Толковому программисту нужно будет недели две-три на прикидку (формат данных, построение матрицы или графа соседства, начальное приближение, методика перекидки частей соседям, формулирование энергии и процедуры "отжига"), потом как повезет, но обычно работает достаточно хорошо, параметры клиент обычно доводит сам под свою задачу. Либо искать готовое, это проще и дешевле (если найдется).