avatar
s*s
1
【 以下文字转载自 Computation 讨论区 】
发信人: spiritless (逝去日子), 信区: Computation
标 题: 算法问题
发信站: BBS 未名空间站 (Mon Sep 17 11:06:08 2007), 站内
最近遇到个问题,忘了有没有相关算法了。
有一些set, from A1 to An, each set contains a number of elements
Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
How to find the minimum number of sets from A1 to An so that
Union of these sets = Union of A1 ... An
Thanks.
avatar
S*n
2
做一个元素到集合的倒排表可能有帮助。

【在 s********s 的大作中提到】
: 【 以下文字转载自 Computation 讨论区 】
: 发信人: spiritless (逝去日子), 信区: Computation
: 标 题: 算法问题
: 发信站: BBS 未名空间站 (Mon Sep 17 11:06:08 2007), 站内
: 最近遇到个问题,忘了有没有相关算法了。
: 有一些set, from A1 to An, each set contains a number of elements
: Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
: How to find the minimum number of sets from A1 to An so that
: Union of these sets = Union of A1 ... An
: Thanks.

avatar
s*u
3
感觉只能搜

【在 s********s 的大作中提到】
: 【 以下文字转载自 Computation 讨论区 】
: 发信人: spiritless (逝去日子), 信区: Computation
: 标 题: 算法问题
: 发信站: BBS 未名空间站 (Mon Sep 17 11:06:08 2007), 站内
: 最近遇到个问题,忘了有没有相关算法了。
: 有一些set, from A1 to An, each set contains a number of elements
: Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
: How to find the minimum number of sets from A1 to An so that
: Union of these sets = Union of A1 ... An
: Thanks.

avatar
s*s
4
I thought there is an existing algorithm that I forgot, but seems
I need to figure out a way, like using greedy algorithm
Thanks anyway

【在 s****u 的大作中提到】
: 感觉只能搜
avatar
s*u
5
怎么greedy?简单greedy明显不work啊

【在 s********s 的大作中提到】
: I thought there is an existing algorithm that I forgot, but seems
: I need to figure out a way, like using greedy algorithm
: Thanks anyway

avatar
D*a
6
这个就是set cover problem,NP-hard

【在 s********s 的大作中提到】
: 【 以下文字转载自 Computation 讨论区 】
: 发信人: spiritless (逝去日子), 信区: Computation
: 标 题: 算法问题
: 发信站: BBS 未名空间站 (Mon Sep 17 11:06:08 2007), 站内
: 最近遇到个问题,忘了有没有相关算法了。
: 有一些set, from A1 to An, each set contains a number of elements
: Ai and Aj has intersection. 比如 Ai=(1,2,3,4) Aj=(3,4,7,8,9,10).
: How to find the minimum number of sets from A1 to An so that
: Union of these sets = Union of A1 ... An
: Thanks.

avatar
s*u
7
不错,果然只能搜

这个就是set cover problem,NP-hard

【在 D*******a 的大作中提到】
: 这个就是set cover problem,NP-hard
avatar
s*u
8
不过n不大而且数的总数不大的话,可以用2^n的dp

【在 s****u 的大作中提到】
: 不错,果然只能搜
:
: 这个就是set cover problem,NP-hard

avatar
s*s
9
看来远难于我预计啊,有几千个set,每个set有4000到5000个element,
总element有20k, dp是没戏了
搜了一下,果然最简单的办法是greedy algorithm
每次选 the set which contains the largest number of uncovered elements
多谢了

【在 s****u 的大作中提到】
: 不过n不大而且数的总数不大的话,可以用2^n的dp
avatar
k*f
10
如果所有element可以找个顺序,而且set都是包含连续的元素,
可能branch-and-bound可以快速求解的。

【在 s********s 的大作中提到】
: 看来远难于我预计啊,有几千个set,每个set有4000到5000个element,
: 总element有20k, dp是没戏了
: 搜了一下,果然最简单的办法是greedy algorithm
: 每次选 the set which contains the largest number of uncovered elements
: 多谢了

avatar
g*g
11
Try to do a simple N^2 screen, if a - b = null, then a is redundant,
You may reduce quite some sets.

【在 s********s 的大作中提到】
: 看来远难于我预计啊,有几千个set,每个set有4000到5000个element,
: 总element有20k, dp是没戏了
: 搜了一下,果然最简单的办法是greedy algorithm
: 每次选 the set which contains the largest number of uncovered elements
: 多谢了

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。