算法问题 - 未名空间MITBBS历史存档

s*s2007-09-17 07:09

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.

S*n2007-09-17 07:09

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.

s*u2007-09-17 07:09

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.

s*s2007-09-17 07:09

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 的大作中提到】

: 感觉只能搜

s*u2007-09-17 07:09

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

D*a2007-09-17 07:09

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.

s*u2007-09-17 07:09

7 楼

不错，果然只能搜

这个就是set cover problem，NP-hard

【在 D*******a 的大作中提到】

: 这个就是set cover problem，NP-hard

s*u2007-09-17 07:09

8 楼

不过n不大而且数的总数不大的话，可以用2^n的dp

【在 s****u 的大作中提到】

: 不错，果然只能搜
:
: 这个就是set cover problem，NP-hard

s*s2007-09-17 07:09

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

k*f2007-09-17 07:09

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
: 多谢了

g*g2007-09-17 07:09

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
: 多谢了