Мне нужно найти эффективный алгоритм, который найдет оптимальный набор двоичных векторов таким образом, чтобы каждый индекс имел бит, который установлен по меньшей мере в одном векторе в наборе.минимальный набор двоичных векторов для полного охвата
Забавная мотивация: Я хочу ворваться в замок и украсть его сокровища. Для этого мне нужно разблокировать 4 двери: синяя дверь, красная, желтая и зеленая. Есть 3 карлика, и у каждого из них есть другой набор ключей. карлик 1 имеет: синий ключ & красный ключ. гном 2 имеет: красный ключ & желтый ключ. карлик 3 имеет: синий ключ & зеленый ключ. Я хочу убить минимальное количество гномов, чтобы попасть в замок. поэтому в этом случае очевидно, что мы должны убить только карлика 2 и карлика 3, чтобы получить все ключи и что нет необходимости убивать карлика.
В общем случае мы имеем n двоичных векторов размера m (n карликов и м дверей): a0, a1 .... a (n-1). Нам нужен набор векторов, для которого мы имеем по крайней мере один ключ для каждого индекса в векторе. Если a1 [5] = 1, то мы знаем, что установлен 6-й бит во втором векторе. значение карлика № 2 имеет ключ №6. Пример в самом начале: a0 (1,1,0,0) a1 (0,1,1,0) a2 (1,0,0,1) поэтому мы выбираем векторы: a1, a2, чтобы получить полное покрытие с минимальными векторами.
Верный алгоритм грубой силы - это попробовать каждый вариант, а затем вернуть решение с минимальным количеством векторов, но поскольку существует n векторов, существует 2^n опций.
Далее я подумал о жадном алгоритме, который принимает каждый раз вектор с большинством клавиш. Но вот встречный пример, который доказывает этот метод не так:
- a0 (1,1,1,0,0,0) --greedy и неправильно choise--
- a1 (1,0, 0,1,0,0)
- a2 (0,1,0,0,1,0)
- а3 (0,0,1,0,0,1)
с этим алгоритм, мы выберем все 4 вектора, но оптимальное решение имеет только 3 вектора {a1, a2, a3}.
Теперь, я подумал о другом жадном алгоритме, мы выбираем вектор с самым редким ключом (и в случае галстука мы ищем следующий редкий ключ и т. Д.), Но опять же я нашел встречный пример:
- a0 (1,1,1,0,0,0) --greedy и неправильно choise--
- a1 (1,0,0,1,0,0)
- a2 (0,1,0,0,1,0)
- a3 (0,0,1,0,0,1)
- a4 (0,0,0,1,0,0)
- а5 (0,0,0,0,1,0)
- а6 (0,0,0,0,0,1)
в этом примере все индексы имеют один и тот же «редкость (2), поэтому мы в конечном итоге выберем a0, хотя сулотион с a0 (такой как {a0, a1, a2, a3}) имеет не менее 4 векторов, а оптимальное решение имеет только 3 {a1, a2, a3}.
Я думаю, что, возможно, если бы я уничтожил векторы, которые являются подмножествами другого вектора (например, a6 - подмножество a3), то этот алгоритм может работать, но даже при этом проверка этого будет стоить n !.
Надеюсь, вы могли бы помочь мне найти эффективный алгоритм или помочь мне доказать, что такого алгоритма не существует.
Это является проблемой [Установить обложку] (http://en.wikipedia.org/wiki/Set_cover_problem). В общем, нет эффективного алгоритма для нахождения оптимального решения. Однако существуют эффективные алгоритмы для приближенных решений. – mbeckish