1

考虑以下与图论相关的问题:

让 G 成为二分图。为了使问题更具体,假设 G 是两个集合的不相交并集,例如 I 和 S。假设

  • I 代表姓​​名为 1、2、3、4、5、6、7、8、9、10 的个人
  • S 代表技能,名称为 a、b、c、d、e、f、g、h。

所以,每个人都有一些技能,例如,

  • 个人 1 具有技能 b、d、g 和 h,
  • 个人 2 具有技能 a、f 和 h,
  • 等等

[在示例中,数据是随机给出的]。

我们的目标是建立一个由来自I的最少数量的个人组成的团队,这样S中的每个技能都将在团队中得到体现,也就是说,对于 S 中的每个技能s 都有一个具有该技能的团队成员小号_

这个问题有名字吗?解决它的有效算法是否已知?

4

2 回答 2

7

听起来像集合覆盖问题l
中的项目组创建s的子集

于 2011-08-03T19:18:30.673 回答
2

您的问题是最小集覆盖问题:

从 N 批次中的 M 件中购买 X 件物品,其中 M 是获得所有 X 件物品所需的最小批次数。

在您的示例中,技能是项目,学生是很多。

http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml

问题是NP难的。解决它的有效方法是使用贪心集覆盖逼近算法。

于 2011-08-04T08:47:01.653 回答