Разбиение набора объектов на несколько подмножеств в соответствии с определенной оценкой

Question

Предположим, у меня есть набор объектов, S, Есть алгоритм f что, учитывая набор S строит определенную структуру данных D в теме: f(S) = D, Если S большой и / или содержит совершенно разные объекты, D становится большим, до такой степени, что становится непригодным для использования (т.е. не помещается в выделенную память). Чтобы преодолеть это, я разделил S на несколько непересекающихся подмножеств: S = S1 + S2 + ... + Sn и построить Di для каждого подмножества. С помощью n структуры менее эффективны, чем их использование, но, по крайней мере, так я могу вписаться в ограничения памяти. С размером f(S) растет быстрее чем S сам по себе, совокупный размер Di намного меньше, чем размер D,

Тем не менее, все еще желательно уменьшить nчисло подмножеств; или уменьшить общий размер Di, Для этого мне нужно разделить S таким образом, что каждый Si содержит "похожие" объекты, потому что тогда f будет производить меньшую выходную структуру, если входные объекты "достаточно похожи" друг на друга.

Проблема в том, что пока "сходство" объектов в S и размер f(S) коррелируйте, нет другого способа вычислить последнее, кроме как просто оценить f(S), а также f не совсем быстро.

Алгоритм, который я имею в настоящее время, состоит в том, чтобы итеративно добавлять каждый следующий объект из S в один из Si, так что это приводит к наименьшему (на данном этапе) увеличению совокупного Di размер:

for x in S:
    i = such i that
             size(f(Si + {x})) - size(f(Si))
             is min
    Si = Si + {x}

Это дает практически полезные результаты, но, безусловно, довольно далеко от оптимального (т. Е. Минимально возможный общий размер). Кроме того, это медленно. Чтобы ускорить немного, я вычисляю size(f(Si + {x})) - size(f(Si)) только для тех i где x "достаточно похож" на объекты уже в Si,

Есть ли стандартный подход к таким проблемам?

Я знаю семейство алгоритмов ветвления и границ, но здесь его нельзя применить, потому что он будет слишком медленным. Я предполагаю, что просто невозможно рассчитать оптимальное распределение S в Si в разумные сроки. Но есть ли какой-то общий итеративно улучшающийся алгоритм?

РЕДАКТИРОВАТЬ:

Как отмечалось в комментариях, я никогда не определял "сходство". На самом деле, все, что я хочу, это разделить на такие подмножества Si этот совокупный размер Di = f(Si) минимален или, по крайней мере, достаточно мал. "Сходство" определяется только как это и, к сожалению, просто не может быть легко вычислено. У меня есть простое приближение, но только оно - приближение.

Итак, мне нужен (вероятно, эвристический) алгоритм, который минимизирует sum f(Si) учитывая, что не существует простого способа вычисления последнего - я использую только приближения, чтобы отбросить случаи, которые вряд ли дадут хорошие результаты.

Answer 1

Что касается медлительности, я обнаружил, что в подобных задачах достаточно хорошее решение состоит в том, чтобы вычислить совпадение, просто выбрав фиксированное количество случайных кандидатов.

Правда, результат не будет лучшим (часто хуже, чем полное "жадное" решение, которое вы реализовали), но, по моему опыту, это не так уж плохо, и вы можете определить скорость... его даже можно реализовать в предписанном количестве время (то есть вы продолжаете поиск, пока не истечет выделенное время).

Другой вариант, который я использую, - это продолжать поиск, пока некоторое время не вижу улучшений.

Чтобы обойти жадную логику, вы можете сохранить очередь из N "x" элементов и попытаться упаковать их одновременно в группы "k" (с k