Алгоритм для нахождения максимальной независимой подгруппы хэшмапов

Question

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

Я попытался пройти через массив из HashMaps и отправлять и индекс каждый раз, и посмотреть, что HashMaps в массиве не независимой с HashMaps в этом индексе, он работал, но в случае

A and B independent 
B and C independent 
but A and C can be not independent 

Определение максимальной независимой подгруппы хэшмапов:

У меня есть массив, содержащий хэш-карты, каждый хэш-файл содержит ключ, каждые два хеш-карты называются независимыми, если каждый ключ в первом хэш-карте не содержится во второй карте, поэтому мне нужно найти подгруппу тех хэшмапов, которые все являются inde pendent

Answer 1

Прежде всего, эта проблема NP-полная. Чтобы доказать это, предположим граф с индексированными ребрами. Создайте HashMap для каждой вершины и заполните ее индексами для каждого края инцидентности этой вершины. Тогда, если два HashMaps независимы, они не содержат одного и того же ребра, поэтому соответствующие вершины также независимы. Поиск максимального независимого подмножества этих HashMaps, следовательно, дает вам максимальный независимый набор в графе, который, как мы знаем, является NP-полным.

Вы можете решить эту проблему, построив граф с вершиной для каждого HashMap и добавив ребро для каждых двух зависимых HashMaps, а затем используя некоторый алгоритм для независимых множеств. Другой способ - взять граф дополнений и finde max clique.

Поскольку это неэффективно, вы можете использовать алгоритм с некоторым приближением.