k*****e
发帖数: 152 | 1 请问有没有人知道有没有现成的算法解决以下问题:
假定有set S 和 n个sets S1,...,Sn. 判断在S1,...,Sn中是否存在k个sets Sk1,...,skk
,such that
Sk1 \union Sk2 \union ... \union Skk 是 superset of S.
或者算法用于找出这个k. 多谢了!!
这有点象knap-sack 问题, 但knap-sack是整数, 这个是集合. | s*****v
发帖数: 360 | 2 haha
【在 k*****e 的大作中提到】
: 请问有没有人知道有没有现成的算法解决以下问题:
: 假定有set S 和 n个sets S1,...,Sn. 判断在S1,...,Sn中是否存在k个sets Sk1,...,skk
: ,such that
: Sk1 \union Sk2 \union ... \union Skk 是 superset of S.
: 或者算法用于找出这个k. 多谢了!!
: 这有点象knap-sack 问题, 但knap-sack是整数, 这个是集合.
| m****h
发帖数: 261 | 3 This is the Set Covering problem if k is fixed or if you want to find the mini
mum k. And it is NP-hard.
【在 k*****e 的大作中提到】
: 请问有没有人知道有没有现成的算法解决以下问题:
: 假定有set S 和 n个sets S1,...,Sn. 判断在S1,...,Sn中是否存在k个sets Sk1,...,skk
: ,such that
: Sk1 \union Sk2 \union ... \union Skk 是 superset of S.
: 或者算法用于找出这个k. 多谢了!!
: 这有点象knap-sack 问题, 但knap-sack是整数, 这个是集合.
| w******T
发帖数: 71 | 4 yes it is set-cover problem,
and you can not get an approximation algorith with worst case ratio better
than log n, for any input instance.
pls refer this site,
http://www.nada.kth.se/~viggo/wwwcompendium/node146.html
【在 m****h 的大作中提到】
: This is the Set Covering problem if k is fixed or if you want to find the mini
: mum k. And it is NP-hard.
|
|
