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

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

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

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

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

Answer 2

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