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

[Sonic86]

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

И кстати, формулировка неточна: не число независимых множеств, а число различных равенств типа $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$ вычеркиваний.

Это неверно. Контрпример $A_1=\{a_1,a_2\}, A_2=\{a_3,a_4\}, A_3=\{a_1,a_2,a_3\},A_4=\{a_4\}$ - все множества независимые, а вычеркиваний - 3.

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

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

Это не задача о независимых множествах на графе. Это мы с самого начала и проверяли фактически - задача БЛП, задача на графе.

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

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

Можете точно свести? Я попозже попробую, сейчас не могу.

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

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

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

Хороший пример.

[pierrevanstulov]

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

Можете точно свести? Я попозже попробую, сейчас не могу.

Как выяснилось - не могу. Это, действительно, не задача о поиске максимального числа несмежных вершин. Скорее это задача о наибольшем числе "мазков", которое необходимо сделать, чтобы закрасить граф. Изначально все вершины незакрашены. Под "мазком" имеется ввиду следующее: мы дотрагиваемся кисточкой до какой-либо вершины, эта вершина закрашивается, при этом краска протекает в смежные с ней вершины и закрашивает их тоже. Разумеется нельзя тыкать кисточкой в закрашенные вершины, все смежные вершины которых тоже закрашены.

[pierrevanstulov]

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

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

[Sonic86]

По ходу, утверждение все-таки неверно. Проверьте:
$A_1=\{3,4\}$
$A_2=\{1,2\}, A_3=\{3,4,5\}$
$A_4=\{1\}, A_5=\{2,3\}, A_6=\{4,5\}$
1-й способ: если вычеркнуть $1$, то потом вычеркивается $2$, потом, например, $3$, а потом $5$.
2-й способ: если вычеркнуть $5$, то потом надо $4$, потом надо $3$, потом надо $2$, потом надо $1$.
Число вычеркиваний получается разное.
Вот в виде "кирпичей":

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

Кстати, остался вопрос об удобном формализме работы с такой задачей.

[pierrevanstulov]

Отличный пример! А вот и полный контрпример к моему правилу:
{2,3,4}, {2,3,5}, {2,3,4,5}, {3,4,5}, {1,4}, {1}.

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

А если мы действуем поперек правила, то можно назвать 2, затем 3, затем 4, затем 1 и получить аж четыре вычеркивания.

Интересно, а как тогда решить задачу об отыскании максимальноготчисла вычеркиваний? Ограничимся случаем, когда множества равномощны, если это имеет значение.

[Sonic86]

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

Интересно, а как тогда решить задачу об отыскании максимальноготчисла вычеркиваний? Ограничимся случаем, когда множества равномощны, если это имеет значение.

Вот не знаю. Скорее всего она NP-полная, но сильно не смотрел, просто так часто бывает. Надо пытаться сводить задачу к уже известным задачам на графе типа задачи независимого множества (можно Гэри Джонсона полистать). Но у меня не получается на этом пути обойти некоммутативность вычеркивания.

[pierrevanstulov]

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

Тут я, было, вздохнул с облегчением! НО! Обнаружилось еще одно условие На k-м шаге мы имеем право называть не любой элемент из объединения множеств из $S_k$, а только элемент, который принадлежит определенному множеству из $S_k$, которое выбирается компьютером (будем считать, что нам неизвестно, как оно выбирается). И получается так, что это множество может и не содержать элемента, принадлежащего максимальному независимому множеству и мы не сможем его назвать, а следовательно пойдем уже не по самому длинному пути. Как тут быть я не знаю

[Sonic86]

Мдя, в таком случае это уже какая-то вероятностная игра. Как распределен выбор компьютера?

[pierrevanstulov]

Там все хитро. Он выбирает множество по определенному алгоритму. Сегодня подумаю сам, чтобы не парить Вас (Вы и так сильно помогли). Если уж ничего не придумается, изложу здесь задачу полностью.

[pierrevanstulov]

Хм, неправильно я написал, что "нельзя называть те элементы, которые принадлежат хотя-бы одному из вычеркнутых множеств"

Короче, исходная задача такова.

Пусть требуется принять комплексное решение, которое состоит из $n$ подрешений.

$i$-е подрешение выбирается из $m_i$ альтернатив.

Каждая альтернатива оценена по шкале от 1 до 5.

Каждая пара альтернатив, относящихся к различным подрешениям либо является сочетаемой, либо несочетаемой. Изначально о сочетаемости пар ничего неизвестно. Информацию о сочетаемости можно получать постепенно, показывая ЛПР различные комплексные решения, и прося его ткнуть пальцем в несочетаемые пары подрешений (если таковые в решении присутствуют).

Требуется найти такое комплексное решение, в котором:
1) все пары подрешений сочетаемы (такое комплексное решение будем называть согласованным)
2) сумма оценок подрешений максимальна.

Алгоритм достаточно прост. Сначала показываем ЛПР комплексное решение, состоящее из самых "хороших" альтернатив. Если ЛПР указывает в нем несочетаемые пары подрешений, то решаем специально сконструированную БЛП, которая позволяет найти, как нужно "подправить" решение, чтобы сумма оценок подрешений в новом комплексном решении была максимальна и это решение не содержало "отбракованных" ранее пар подрешений. Далее новое комплексное решение опять оценивается ЛПР на предмет согласованности и, если в нем есть несочетаемые пары подрешений...

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

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