作者yauhh (哟)
看板Programming
标题Re: 算法问题 (从N个set选m个包含最少的元素)
时间Fri Jun 1 19:39:16 2012
※ 引述《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)
1F：推 sorryChen:感谢,所选组合会越来越好,但除非所有 207.151.93.115 06/02 04:27
2F：→ sorryChen:组合都试过,不然没有保证最好 207.151.93.115 06/02 04:28
3F：→ sorryChen:一次最多换一个,很可能是local min 207.151.93.115 06/02 04:28
4F：→ yauhh:我就在想着,咦,会只有local minimum吗? 59.112.228.180 06/02 08:17
5F：→ yauhh:第二个想的是,想找一个解还是多找几个解? 59.112.228.180 06/02 08:19
6F：推 sorryChen:谢谢 只要一个, 让我想想local min的例 207.151.93.115 06/02 10:53
7F：推 sorryChen:主要是一次只检查替代一个是否更好 207.151.93.115 06/02 10:57
8F：→ sorryChen:因为有可能一次替换多个才会更好 207.151.93.115 06/02 10:57