Выберите максимальное количество строк, удовлетворяющих этому условию

Я столкнулся с этой проблемой в конкурсе кодирования, который сводится к следующей проблеме:

Какое максимальное количество строк можно выбрать из двоичной матрицы, чтобы никакие две строки не имели столбца AND ненулевого значения? (Все пары для строк должны иметь столбец И ноль).

Ограничения: строки‹=50 , столбцы‹=20

Eg.

00101101

10110001

10000010

Ответ 2 (первая и третья строки).

Я мог предположить, что существует какой-то экспоненциальный алгоритм по количеству столбцов (из-за ограничений). Я просто не мог добраться до решения. Все мои другие попытки были слишком сложными с созданием графика и поиском независимого набора, и они также были экспоненциальными по количеству строк. Может ли кто-нибудь помочь мне с решением для этого?

Я пытался проверить код других участников после конкурса, они, похоже, решают его с помощью DP. Я не прошу полного решения. Буду признателен за подробные подсказки.

РЕДАКТИРОВАТЬ:

Если описание непонятно, выбранные строки не должны иметь общего в одном столбце (извините, если все еще непонятно). Как и в данном примере, первая и вторая строки не могут быть выбраны, потому что они есть в 3-м и 8-м столбцах. Точно так же 2-я и 3-я строки не могут быть выбраны, потому что они имеют общую в 1-м столбце. В 1-м и 3-м рядах НЕТ ОБЩЕГО.


algorithm dynamic-programming language-agnostic
person Naman    schedule 10.08.2015    source источник
comment
... так что никакие две строки не имеют столбца AND ненулевого значения. (Все пары для строк должны иметь столбец И ноль). Что это обозначает? Возможно, вы пропустили несколько слов, потому что я не понимаю, что это значит.   -  person dpmcmlxxvi    schedule 10.08.2015
comment
Я попытался быть более ясным об этом в редактировании. Пожалуйста, дайте мне знать, если это имеет смысл сейчас.   -  person Naman    schedule 11.08.2015

Ответы (2)


arrow_upward
1
arrow_downward

Это NP-сложная задача упаковки множеств. Предполагаемое решение O (m 2 ^ n) времени (где m — количество строк, а n — количество столбцов, меньше размера слова) подготавливает таблицу, проиндексированную на 0..m, умноженную на 0..2^n. -1, где ячейка (i, j) — это максимальное количество строк с индексами от 0 до i, чьи попарные пересечения/И являются пустыми/нулевыми, а объединение/ИЛИ равно j.

person David Eisenstat    schedule 10.08.2015
comment
Это именно то, что я ищу. Не могли бы вы немного подробнее рассказать о своем решении. Я был бы очень рад. - person Naman; 11.08.2015

arrow_upward
0
arrow_downward

https://en.wikipedia.org/wiki/Set_packing дает эквивалентную проблему определения того, существует ли есть k подмножеств из набора заданных подмножеств универсального набора из N элементов, таких, что ни одно из k выбранных подмножеств не пересекается. Задача максимизации очевидна и может быть решена за полиномиальное время, если проблема решения может быть решена за полиномиальное время: задача максимизации требует максимального k, такого что можно найти k подмножеств, таких, что ни одно из k подмножеств не пересекается.

К сожалению, эти проблемы являются NP-трудными (в частности, проблема решения для конкретного k является NP-полной), поэтому, если P = NP, для вашей проблемы не существует универсального быстрого решения. Возможно, учитывая небольшое количество строк и столбцов в вашей задаче, можно разработать «достаточно быстрое» решение. Однако, основываясь на моем первоначальном прочтении классической задачи упаковки множества, неясно, как такое решение будет работать.

person user2566092    schedule 10.08.2015
comment
Это именно то, что я упомянул в описании, что мне нужен экспоненциальный алгоритм по количеству столбцов. Пожалуйста, перечитайте описание. - person Naman; 11.08.2015
comment
@ Наман, я понимаю, я пытался найти в литературе решение, которое было бы слегка экспоненциальным по количеству столбцов или строк, но я его не нашел. Я просто пытался указать, почти одновременно с Дэвидом Эйзенстатом, что для вашей задачи почти наверняка не существует алгоритма с полиномиальным временем, потому что он NP-сложный. Вы не упомянули об этом в своем посте, поэтому я хотел, чтобы вы знали. Динамическое программирование может быть полиномиальным, псевдополиномиальным или экспоненциальным по времени, в зависимости от задачи и того, что является переменным. Я пытался направить вас в поисках алгоритма динамического программирования. - person user2566092; 11.08.2015