Есть прямоугольная область (дискретная, из клеточек одинакового размера), каждая клеточка имеет свой вес. Нужно разбить эту область на подобласти, такие что:
1) вес подобласти не превышал некоторого заданного значения;
2) сумма весов всех подобластей была минимальна.
Вес подобласти НЕ является суммой входящих в нее клеточек а рассчитывается по отдельному заморочному алгоритму (относительно недорогому но лень описывать, кроме того он зависит от табличных данных которые могут меняться от запуска к запуску), можно утверждать что сумма весов клеточек является оценкой сверху. Т.е. если мы разбиваем область на две подобласти - сумма их весов возрастает, но вес каждой становится меньше чем у исходной области.
Кроме того подобласти должны быть по возможности компактными (близкими к квадратным?), так их вес меньше.
Размер исходной области - неск. сот клеточек по каждой стороне. Целевое число подобластей - в пределах первых сотен.
Мы пробовали два алгоритма:
1) ввести неравномерную сетку по каждой оси (использовать расщепление).
2) k-d дерево.
Оба алгоритма дают примерно одинаковые результаты, k-d дерево чуть лучше. Но видно, что это не предел, по субьективным ощущениям можно улучшить ситуацию раза в два. Может у кого то будут еще какие то мысли?
