Эффективное вычисление минимальных элементов над частично упорядоченными множествами

Question

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

На самом деле, я не требую полного упорядочения, только минимальные элементы.

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

Каков был бы наиболее удобный в пространстве и времени способ решения этой проблемы?Возможно, есть способ, который не требует построения всего графика целиком?Возможно, существует известный алгоритм с лучшей терминологией, чем тот, который я наивно описал выше?

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

Предыстория:В настоящее время я создаю целую базу данных графов, которая содержит все ребра между наборами, а затем ищу узлы, которые не имеют обобщений, но это довольно сложно, медленно и требует много места на диске.Упомянутый выше список содержит примерно 100 миллионов комплектов.

Answer 1

Один подход - сортировать множества путем увеличения размера, то неоднократно выполняют следующее: сделайте первый набор в списке, выведите его и удалите из списка всех суперсец. Это выкроет все минимальные наборы. Время работы - $ O (NK) $ Установленные сравнения плюс $ O (n \ log n) $ Шаги для сортировки, где $ n $ - это количество наборов, которые у вас есть и $ K $ - это номер минимальных элементов. Или, чтобы поставить его другим способом, если каждый набор содержит Элементы $ m $ , время работы будет приблизительно $ O ( n (k + \ log n) m) $ Основные шаги.

Почему отрицать по размеру? Это оптимизация. Самый маленький набор гарантированно будет минимальным (в списке нет меньших мощностей, поэтому ни одно из его подмножеств не может быть в списке), поэтому размер является полезным трюком, чтобы определить набор, который обязательно должен быть минимальным.

без сортировки по размеру, время работы в худшем случае, скорее всего, будет в конечном итоге $ O (N ^ 2) $ Установленные сравнения (или <класс SPAN= «Математический контейнер»> $ o (n ^ 2 m) $ Основные шаги), который хуже, когда $ K \ ll n $ . .

---

Вот оптимизированная версия этого алгоритма. Пусть $ m $ - структура данных, которая хранит набор наборов, как TRIE: например, множество $ \ {1,3,6,7 \} $ соответствует слову $ 1367 $ и хранится в TRIE соответственно. Первоначально $ m $ пустой. Повторите следующее: возьмите следующий набор $ S $ из списка; Проверьте, есть ли набор в $ m $ - это подмножество $ s $ ; Если нет, вставьте $ s $ в $ m $ ; Наконец, удалите $ s $ из списка (или продвиньте свой указатель на следующий элемент в списке). Операция «Проверка ...» может быть выполнена довольно эффективно, используя рекурсивный обход TRIE. В конце, как только вы пройдете весь список, выведите $ m $ .

Время работы в худшем случае оптимизированного алгоритма остается прежним. На практике время работы может быть значительно улучшено, возможно, так же быстро, как $ O (NM) $ Основные шаги в некоторых случаях, если вам повезет (но не считай в теме). Вы можете попробовать и посмотреть, что работает лучше на практике на вид рабочей нагрузки, с которыми вы имеете дело.

Answer 2

Я нашел решение в этот документ, стр.12.

Алгоритм, упомянутый там в качестве доказательства, должен быть переведен в следующий код python:

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

Я ожидаю, что break иметь решающее значение для реального времени выполнения, поэтому было бы неплохо отсортировать X заранее, чтобы сделать перерыв пораньше, но я не уверен в этом.

Еще один момент, который я вижу здесь, заключается в том, что > предполагается, что это нерефлексивно, так что x>x не держится.Но для этого кода было бы лучше, если бы это было так.Если a==x, он ломается вместо того, чтобы без необходимости смотреть дальше.

Обновить: Теперь я смог протестировать различные реализации на Python.Пожалуйста, позвольте мне напрямую привести код python, я думаю, что он достаточно похож на псевдокод - и, возможно, более конкретный для многих людей.

Вот реализация, взятая из статьи:

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

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

Хитрость заключается в том, чтобы сделать этот алгоритм независимым от m избегая прохождения всех текущих минимальных элементов.Вместо этого мы можем использовать тот факт, что поиск в результирующем наборе выполняется быстро (я думаю, именно здесь в игру вступает trie).

Для каждого x мы генерируем все обобщения.Теперь сложность зависит от количества x и их размера, но не столько от количества минимальных элементов (только O (n log n)?).Что еще лучше, поскольку теперь нам приходится удалять неминимальные элементы из начального списка элементов вместо их добавления, время, используемое для каждого x, уменьшается, а не увеличивается во время выполнения.

Вот соответствующий код:

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

При этом используется функция генератора generalizations() чтобы избежать вычисления дополнительных обобщений x один раз один из них уже был найден в текущих минимальных элементах.Это уже довольно быстро с моими данными, но, возможно, это можно было бы улучшить, сначала сгенерировав обобщения, которые являются более общими (их необходимо протестировать, если это ускорит процесс), и, в частности, сгенерировав только обобщения, состоящие из элементов, которые уже наблюдались в текущих минимальных элементах.Например, если наш x является {a,b,c}, но ни один текущий минимальный элемент не имеет c в нем нам не нужно генерировать какое-либо подмножество x который содержит c, т. е.Только {a,b},{a},{b},{}.