Как называется этот вариант задачи о покрытии множества?

Input вселенная и семейство подмножеств , скажем, . Будем считать , что подмножества можно покрыть , то есть, .U F ⊆ 2 U F U ⋃ E ∈ F E = $U$$U$${\cal F} \subseteq 2^U$${\cal F}$$U$$\bigcup_{E\in {\cal F}}E=U$

Инкрементный последовательность покрытие представляет собой последовательность подмножеств , скажем, , что удовлетворяетA = { E 1 , E 2 , … , E | A | ${\cal F}$${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$

1) $\forall E\in {\cal A}, E\in {\cal F}$ ,

2) у каждого новичка есть новый вклад, т. Е. \ Forall $\forall i>1$ , $\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$ ;

Проблема состоит в том, чтобы найти инкрементную покрывающую последовательность максимальной длины (т. Е. С максимальной $|{\cal A}|$ ). Следует отметить , что последовательность максимальной длины должна в конечном итоге покрыть $U$ , то есть, $\bigcup_{E\in {\cal A}}E=U$ .

Я попытался найти алгоритм или приблизительный алгоритм, чтобы найти самую длинную инкрементную последовательность покрытия. Мне было просто интересно, как называется этот вариант проблемы с множеством покрытий. Спасибо!

Здесь я показываю, что проблема является NP-полной.

Мы конвертируем CNF в экземпляр вашей проблемы следующим образом. Предположим, что переменными CNF являются , а предложения - , где . Пусть где все множества в объединении полностью не пересекаются. Фактически, и , в то время как - это любое множество элементов . Также обозначим и зафиксируем для каждого растущее семейство длины внутри него, обозначаемое дляx i m C j n < m U = ∪ i ( A i ∪ B i ∪ Z i ) A i = { a i , j ∣ x i ∈ C j } ∪ { a i , 0 } B i = { b i , j ∣ x i ∈ C j } $n$ $x_i$$m$ $C_j$$n<m$$U=\cup_i (A_i\cup B_i\cup Z_i)$$A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$Z i k = 2 n + 1 Z = ∪ i Z i Z i k Z i , l l = 1 .. k x i 2 k F A i ∪ Z i , l B i ∪ Z i , l C j F Z x i ∈ C j { $B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$$Z_i$$k=2n+1$$Z=\cup_i Z_i$$Z_i$$k$$Z_{i,l}$$l=1..k$ . Для каждой переменной мы добавляем наборов в , каждый набор вида и . Для каждого предложения мы добавляем один набор в , который содержит , и для каждого элемента и для каждого элемента .$x_i$$2k$$\mathcal F$$A_i \cup Z_{i,l}$$B_i \cup Z_{i,l}$$C_j$$\mathcal F$$Z$$x_i\in C_j$ ˉ х я ∈ С J { Ь I , J$\{a_{i,j}\}$$\bar x_i\in C_j$$\{b_{i,j}\}$

Предположим, что формула выполнима и исправим удовлетворяющее присваивание. Затем выберите наборов в форме или , в зависимости от того, является ли истинным или нет. Это инкрементальных множеств. Теперь добавьте наборов, соответствующих пунктам. Они также продолжают увеличивать размер, поскольку пункты являются выполнимыми. Наконец, мы можем даже добавить больше наборов ( по одному для каждой переменной) , чтобы сделать последовательность крышку .A i ∪ Z i , l B i ∪ Z i , l x i n k m k $k$$A_i \cup Z_{i,l}$$B_i \cup Z_{i,l}$$x_i$$nk$$m$$k$$U$

Теперь предположим, что наборов расположены в последовательной последовательности. Обратите внимание , что в большинстве устанавливает соответствующие могут быть выбраны для каждого . Таким образом, если в добавочной последовательности нет наборов предложений, можно выбрать не более , что слишком мало. Обратите внимание, что как только набор предложений выбран, мы можем выбрать не более двух наборов, соответствующих каждому , всего не более наборов. Следовательно, нам нужно выбрать как минимум наборов переменных, прежде чем будет выбран любой набор предложений. Но так как мы можем выбрать самое большее для каждого , это означает, что для каждого мы выбрали по крайней мереk + 1 x i x i n ( k + 1 ) x i 2 n n ( k - 1 ) k + 1 x i 1 k = 2 n + $n(k+1)+m$$k+1$$x_i$$x_i$$n(k+1)$$x_i$$2n$$n(k-1)$$k+1$$x_i$$1$ , так как . Это определяет «значение» переменной, поэтому мы можем выбирать только «истинные» предложения.$k=2n+1$

Обновление: изменено значение с до как указал Марцио.n 2 n + $k$$n$$2n+1$

Это проблема упаковки множеств при условии, что для решения для любого подмножества мы имеем, что в всегда есть элемент , который покрывается ровно один раз.B ⊆ A ⋃ X ∈ B$\mathcal{A}$$\mathcal{B} \subseteq \mathcal{A}$$\bigcup_{X \in \mathcal{B}} X$

Доказательство: учитывая решение вашей проблемы, оно сразу же имеет это свойство. В самом деле, если является оптимальным решением вашей задачи, то рассмотрим подмножество этих множеств и предположим, что является последним множеством в этой последовательности, встречающимся в . Из обязательного свойства, что решение является инкрементным, следует, что покрывает элемент, который не охватывает предыдущий набор, что подразумевает указанное выше свойство.$E_1, \ldots, E_m$E i B E $\mathcal{B}$$E_i$$\mathcal{B}$$E_i$

Что касается другого направления, то это тоже легко. Начните с решения , найдите элемент, который покрыт ровно один раз, установите его как последний набор в последовательности, удалите этот набор и повторите. QED.$\mathcal{A}$

Это довольно естественная проблема ....

Быстрое напоминание: в задаче упаковки наборов для данного семейства наборов найдите максимальное подмножество наборов, которое соответствует некоторому дополнительному ограничению (скажем, ни один элемент не покрывается более 10 раз и т. Д.)