Вычислить наибольшее подмножество набора так, чтобы все элементы подмножества попарно соответствовали определенному условию
У меня есть набор S, состоящий из натуральных чисел, и функция, которая, если на входе даны два натуральных числа, возвращает либо true, либо false. Назовем критерии, на основе которых он вычисляет выходные данные, именем «независимость». Итак, некоторые пары чисел независимы, другие — нет. Пара, состоящая из одного и того же числа, не является независимой. Я хочу вычислить наибольшее подмножество S такое, что все его элементы попарно независимы.
Существуют ли классические алгоритмы, решающие подобные задачи? У вас есть предложения или подсказки? Я просто действительно не знаю, что попробовать, даже с использованием грубой силы я не уверен, как эффективно вычислять и хранить различные подмножества и сравнивать их, чтобы найти самое большое.
Обновлено: я только что понял, что проблему можно описать с помощью графа, где независимость между двумя числами определяет ребро, соединяющее две вершины. Проблема сводится к поиску самого длинного пути в графе.
P.S. Я предпочитаю C++, но меня устраивают другие синтаксисы.
Это задача о максимальной l клике. en.m.wikipedia.org/wiki/Clique_problem Это NP-сложно. Нет хорошего алгоритма.
Либо вы неправильно используете термин «попарно», либо ошибаетесь в том, что решение эквивалентно самому длинному пути. В случае «попарно» мы будем искать набор вершин, в котором каждые две вершины в наборе соединены, то есть клику.
Ответы 1
Ваша интерпретация проблемы в теории графов не совсем правильна - простым контрпримером может быть отношение, в котором два числа являются «независимыми», если они последовательные. Хотя допустимым путем, если вы построили граф, будет 1, 2, 3 и т. д., очевидно, что 1 и 3 не являются независимыми. Таким образом, существуют бесконечно длинные пути, а самое большое такое подмножество может содержать только 2 элемента.
Аналогия, которая вам нужна, - это поиск наибольшего полного подграфа графа, к которому я бы направил вас в этой статье в Википедии, и это эквивалентно задаче о максимальной клике. Вы можете найти некоторые реализации рекурсивного кода MCP в Интернете.
Можете ли вы добавить код и примеры? Или код, который, по крайней мере, имеет входные данные и желаемые выходные данные?