作者sorryChen (陈扬和)
看板Programming
标题Re: 算法问题 (从N个set选m个包含最少的元素)
时间Sat Jun 2 11:02:58 2012
※ 引述《yauhh (哟)》之铭言：
举个一次只换一个非最好的例子
S1={1,2,3}, S2={2,3,4},S3={1,3,4}, S4={5,6}, S5={5,6}, S6={5,6}
: : M=3好了, 选S4,S5,S6 最好
但假设一开始选到 S1,S2,S3开始.. 用S4, S5, S6 一个代换时
集合都会变成四个元素, 最好的只要两个元素
但每次考虑多个, 除非所有c(M,N)全部组合都考虑才保证最好, 这样就非polynomial了
: 借你这个例子,忽略掉你所问的推文问题,我的粗浅想法是:
: 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,4}
: 其中要用到的基础运算单元就是联集运算和差集运算了.
--
Life is continuous
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 207.151.93.115
※ 编辑: sorryChen 来自: 207.151.93.115 (06/02 11:05)
1F：推 yauhh:没错,第一个方式是卡到local minimum了.218.160.110.179 06/04 10:15
2F：→ yauhh:还好有想到第二个方法依组合顺序找,不无小补218.160.110.179 06/04 10:28