Re: 算法問題 (從N個set選m個包含最少的元素)

[yauhh (喲)]

※ 引述《sorryChen (陳揚和)》之銘言：
: ※ 引述《sorryChen (陳揚和)》之銘言：
: : 給定N個set, 規定至少個set, 使選的sets的集合包含的element個數越少越好
: 請原諒不太懂推文中所寫的所以舉例一下
: ex: S0={0}, S1={1}, S2={2},S3={3}, S4={1,2}, S5={1,2}, S6={2,3}, S7={1,3}
: 假設都排好了
: M=4好了, 選S1,S2,S4,S5
: M=7好了, 選S1,S2,S3,S4,S5,S6,S7, 反正不選S0, 想說排序選前面的不見得最好

借你這個例子,忽略掉你所問的推文問題,我的粗淺想法是:

1. 取指定集合數M: 在此為3.

2. 隨便取第一個M sets, 做一個binding B, 對應到M sets包含的全部元素:

   取 S0={0}, S1={1}, S2={2} ===> B = { {S0, S1, S2}, {0, 1, 2} }

3. 取下一個集合 S4 = {1, 2}.

4. 問 S4 替換掉 S0, S1, S2 之一, 會不會減少M sets元素數目:

   4-1. { {S4, S1, S2}, {1, 2} } 減少了元素數目.

   4-2. { {S0, S4, S2}, {0, 1, 2} } 沒有減少元素數目.

   4-3. { {S0, S1, S4}, {0, 1, 2} } 沒有減少元素數目.

   4-4. 經過以上核對, 取 {S1, S2, S4} 為M sets.

5. 如果有其餘集合, 回到3.


--------- 這個解決辦法的另一種解釋 -------------

取(N,M)組合,例如(8,3)組合,依序求聯集,看有沒有出現元素量更少的聯集:

S0 S1 S2 S3 S4 S5 S6 S7
*  *  *                 {0,1,2}
*  *     *              {0,1,3}
*  *        *           {0,1,2}
......
   *  *     *           {1,2}

其中要用到的基礎運算單元就是聯集運算和差集運算了.


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.228.180
※ 編輯: yauhh           來自: 59.112.228.180       (06/01 22:16)
推 sorryChen:感謝,所選組合會越來越好,但除非所有
→ sorryChen:組合都試過,不然沒有保證最好
→ sorryChen:一次最多換一個,很可能是local min
→ yauhh:我就在想著,咦,會只有local minimum嗎?
→ yauhh:第二個想的是,想找一個解還是多找幾個解?
推 sorryChen:謝謝 只要一個, 讓我想想local min的例
推 sorryChen:主要是一次只檢查替代一個是否更好
→ sorryChen:因為有可能一次替換多個才會更好