Поиск минимального подмножества объектов с атрибутами.

Question

У меня алгоритмическая проблема. Я не знаю, как его решить. Может быть, кто-то может мне помочь?

У меня есть объекты. Каждый объект имеет те же функции. Это можно проиллюстрировать в таблице:

    Feature1 Feature2 Feature3 Feature4 
     Object1  1   0   1   1 

     Object2  0   0   0   1 

     Object3  0   1   1   1 

     Object4  0   1   0   0 

Теперь я хочу найти все минимальные подмножества объектов. Каждое подмножество должно иметь по крайней мере одно значение «1» для каждой функции. Для таблицы выше приведены два подмножества: {Object1, Object3} и {Object1, Object4}. Я не могу сгенерировать все возможные подмножества, потому что это может занять слишком много времени.

Answer 1

Это точно set cover problem. Проблема NP-hard, поэтому, если вам нужен минимальный , генерация всех возможных подмножеств не будет намного хуже, чем другие решения во времени.

Но существуют некоторые алгоритмы приближения полиномиального времени. Подробнее см. На странице Википедии. «Лучший» является жадный алгоритм, который работает так:

1. Инициализировать нереализованные функции, как {Feature1, feature2, Feature3, ...}
2. Выберите объект, который реализует наиболее нереализованные возможности.
3. Повторите 2 до тех пор, пока не будут реализованы все функции.

Answer 2

Вы можете уменьшить проблему, включив по необходимости все объекты, являющиеся единственным обладателем данной функции (или функций). Object1 является единственным, у которого есть Feature1, поэтому вы знаете, что вам нужно это в своем решении.