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

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

0 голосов
/ 12 июня 2010

Предположим, у меня есть набор объектов, 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 за разумное время. Но есть ли какой-то общий итеративно улучшающийся алгоритм?

EDIT:

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

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

1 Ответ

1 голос
/ 12 июня 2010

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

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

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

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

...