Задачка на вычеркивание множеств

[pierrevanstulov]

Казалось бы элементарная задачка с элементарным решением: есть совокупность множеств $S_1=\left\{A_1,A_2,...,A_n\left\}$. Нас просят назвать элемент, который принадлежит хотя-бы одному множеству из $S_1$, после чего все множества, содержащие этот элемент удаляют из $S_1$ - таким образом получается новая совокупность $S_2$. Далее все повторяется: нас просят назвать элемент, который принадлежит хотя-бы одному множеству из $S_2$, после чего все множества, содержащие этот элемент удаляют из $S_2$ - таким образом получается новая совокупность $S_3$. И т.д., пока совокупность множеств не станет пустой.

Вопрос: какой элемент нужно называть на каждом шаге, чтобы количество итераций до полного исчерпания исходной совокупности было максимальным?

Ответ напрашивается сам собой: на k-м шаге нужно называть такой элемент, который входит в наименьшее число множеств из $S_k$.

Но как это доказать? Хотябы какой подход к доказательству здесь можно применить?

[Sonic86]

Задача формализуется комбинаторной задачей на графах: дано конечное множество элементов $A=A_1\cup ... \cup A_n$ и конечное множество $\{A_1,...,A_n\}=B$, вершины $v(a), a\in A$ и вершины $v(b),b\in B$ соединяем ребром тогда и только тогда, когда $a\in b$. Получаем двудольный граф и на нем задачу вершинного покрытия (или как она называется, я уже не помню), только с ограничением выбора вершин лишь из множества $v(A)$. Дальше легко строится задача булева линейного программирования с $|A|+n$ переменными (из которых последние $n$ равны нулю по последнему условию) и $n$ условиями. Задача, есс-но, NP-полная.

pierrevanstulov в сообщении #684877 писал(а):

Ответ напрашивается сам собой: на k-м шаге нужно называть такой элемент, который входит в наименьшее число множеств из $S_k$.

Но как это доказать? Хотябы какой подход к доказательству здесь можно применить?

Это скорее всего неверно, это часто выполняется, но не всегда, это т.н. "жадный алгоритм". Контрпримеры обычно имеют число вершин порядка $10-20$, я не буду их искать.
Хотя можно утверждать, что если существует элемент, входящий в только одно множество $A_j$, то можно смело брать его. И т.д. брать то тех пор, пока все такие не исчезнут. Это известный частичный алгоритм тоже.

[pierrevanstulov]

Понял, как можно применить Ваш метод для поиска наиболее короткой цепочки (см. граф на рисунке).


Задача оптимизации:

$\sum_{i=1}^{|A|}b_i \to \max$

$b_1b_2+b_2b_3+b_2b_4=0$

$b_i \in \{0,1\}$

Если $b_i^{*}=0$, то называем элемент $a_i$.

А как найти наиболее длинную, не совсем понятно.

[Sonic86]

pierrevanstulov в сообщении #684930 писал(а):

Понял, как можно применить Ваш метод для поиска наиболее короткой цепочки:

Слово "цепочка" не определено, поясните.
Если имеется ввиду число вычеркиваний, то да, наверное, надо подумать.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы оформлены неправильно

Запишите все формулы с картинки ТеХом, а на картинке оставьте только граф. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

[AKM]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

[pierrevanstulov]

Sonic86 в сообщении #684974 писал(а):

pierrevanstulov в сообщении #684930 писал(а):

Понял, как можно применить Ваш метод для поиска наиболее короткой цепочки:

Слово "цепочка" не определено, поясните.
Если имеется ввиду число вычеркиваний, то да, наверное, надо подумать.

Под "цепочкой" я имел ввиду последовательность элементов, которую мы называем (число циклов вычеркиваний). Мне нужно определить, как нужно называть элементы, чтобы исходная совокупность множеств исчерпывалась как можно дольше.

[Sonic86]

pierrevanstulov в сообщении #685052 писал(а):

Под "цепочкой" я имел ввиду последовательность элементов, которую мы называем (число циклов вычеркиваний).

Хорошо.

Не. Как задачу БЛП сформулировать, кажется, не получается. Мы же не можем вычеркивать 2 элемента из одного и того же множества (тогда решение было бы просто: выбираем $A_k:|A_k|=\min$ и вычеркиваем все $a:a\not\in A_k$). Тогда

Sonic86 в сообщении #684891 писал(а):

Это скорее всего неверно, это часто выполняется, но не всегда, это т.н. "жадный алгоритм". Контрпримеры обычно имеют число вершин порядка $10-20$, я не буду их искать.

неверно.

неудачные попытки удалены.

pierrevanstulov в сообщении #684877 писал(а):

Ответ напрашивается сам собой: на k-м шаге нужно называть такой элемент, который входит в наименьшее число множеств из $S_k$.

Да, похоже, что это верно. Только доказать действительно немного затруднительно.

[pierrevanstulov]

Эм. Я видимо не совсем ясно выразился. Говоря про "вычеркивания" я имел ввиду, что мы называем элемент, а потом из исходной совокупности множеств убираем (то есть вычеркиваем) те множества, которые этот элемент содержат. Прочитайте, пожалуйста, повнимательнее мой первый пост.

Последовательность здесь безусловно играет роль. Мне всетки кажется, что изначальная гипотеза верна. Да и доказываться она должна достаточно несложно, просто никак не пойму, как подступиться к доказательству.

Полностью согласен с последними двумя upd перед гипотезой в предыдущем Вашем посте.

Upd: Подозреваю, что нужно доказать, что если использовать выдвинутое правило, то к k-му шагу количество вычеркнутых ранее множеств будет наименьшим из возможных. Для k=2 это верно по определению. Попробую доказать для k=3... Присоединяйтесь

Upd: Sonic86, спасибо большое за проявленный интерес. Будут идеи, обязательно пишите.

[Sonic86]

У меня что-то тоже не получается
Не получится использовать оптимальные последовательности вычеркиваний: их может быть несколько, а при добавлении следующего множества они могу полностью изменится.
Заметил еще такое: оптимальное число вычеркиваний по Вашему правилу равно числу "независимых" множеств в последовательности $A_1,...,A_n$ (независимым я называю тут множество, которое не получается суммой нескольких непересекающихся множеств $A_{i_1},...,A_{i_m}$). Не знаю, может ли это чем-то помочь.
А правило вычеркиваний все-таки верно.

[pierrevanstulov]

pierrevanstulov в сообщении #685075 писал(а):

Upd: Подозреваю, что нужно доказать, что если использовать выдвинутое правило, то к k-му шагу количество вычеркнутых ранее множеств будет наименьшим из возможных. Для k=2 это верно по определению. Попробую доказать для k=3... Присоединяйтесь

Это неверно. Построил контрпример.

[pierrevanstulov]

Sonic86 в сообщении #685097 писал(а):

Заметил еще такое: оптимальное число вычеркиваний по Вашему правилу равно числу "независимых" множеств в последовательности $A_1,...,A_n$ (независимым я называю тут множество, которое не получается суммой нескольких непересекающихся множеств $A_{i_1},...,A_{i_m}$). Не знаю, может ли это чем-то помочь.
А правило вычеркиваний все-таки верно.

Хм, а ведь в моей изначальной задаче ни одно множество не может быть получено объединением других множеств (в первом посте я написал более общую формулировку, чем моя изначальная задача). А что может быть длиннее, чем вычеркивать множества по одному? Ничего! Уважаемый, Sonic86, не могли бы Вы привести доказательство своего утверждения про "независимые" множества. Это и будет решением моей задачи.

[Sonic86]

pierrevanstulov в сообщении #685441 писал(а):

не могли бы Вы привести доказательство своего утверждения про "независимые" множества. Это и будет решением моей задачи.

Пока не могу. Я его просто заметил.
И кстати, формулировка неточна: не число независимых множеств, а число различных равенств типа $A_{i_1}+...+A_{i_r}=A_{j_1}+...+A_{j_k}$. Например, можно взять $A_1=\{a_1,a_2,a_3\},A_2=\{a_4,a_5,a_6\},A_3=\{a_7,a_8,a_9\}$, $A_4=\{a_2,a_3,a_4\},A_5=\{a_5,a_6,a_7\},A_6=\{a_8,a_9,a_1\}$, $A_7=\{a_3,a_4,a_5\},A_8=\{a_6,a_7,a_8\},A_9=\{a_9,a_1,a_2\}$ (три зацикленных слоя кирпичей) Здесь имеется ровно $2$ соотношения:
$A_1+A_2+A_3=A_4+A_5+A_6=A_7+A_8+A_9$. Т.е. максимум $9-2=7$ вычеркиваний.

[pierrevanstulov]

Глубоко Вы, однако, копнули.

Самое неприятное, это то, что нельзя утверждать, что к любому k-му шагу количество вычеркнутых множеств при условии применения правила будет наименьшим из возможных.

Пример: $\{2,4\}, \{2,3,5\}, \{2,3,4,5\}, \{3,4,5\}, \{1,4\}, \{1\}$.

Согласно правилу сначала нужно назвать элемент $1$, а потом $2$. В этом случае к третьему шагу будет вычеркнуто 5 множеств. Но если мы назовем сначала элемент $2$, а потом $3$, то к третьему шагу будет вычеркнуто только 4 множества.

Попробовал доказать верность правила "грубой силой" (составляя возникающие по ходу неравенства и применяя формулу включений-исключений) для множеств, состоящих не более чем из трех элементов в случае исчерпания их на втором шаге. Исписал три листа А4 неравенствами и еле-еле доказал. Для доказательства в общем случае, думаю, такой подход будет малопродуктивен

----

А ведь смотрите, задачу можно свести к поиску максимального количества несмежных вершин в неориентированном графе. Наверняка ведь такая задача уже рассматривалась и как-нибудь там называется.

Если элементы входят в какое-либо множество, то они соединяются дугой. Например для системы множеств: $\{1,2,3\}, \{1,6\}, \{1,5\}, \{2,3,4\}$ граф будет таким:

[pierrevanstulov]

Нашел: http://ru.wikipedia.org/wiki/Задача_о_независимом_множестве . Видимо моя изначальная гипотеза неверна, раз задача NP-полна