Bipartite graph algorithm
Consider the following question relative to graph theory :
Let G a bipartite graph. To make the problem more concrete suppose G is the disjoint union of two sets, say I and S. Suppose
- I represents Individuals with name 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- S represents Skills with name a, b, c, d, e, f, g, h.
So, each indi开发者_StackOverflow社区vidual has some skills, for instance,
- individual 1 has skills b, d, g and h,
- individual 2 has skills a, f, and h,
- etc.
[in the example, datas are randomly given].
We aim to build a team composed of the minimum number of individuals from I in such a way that every skill in S will be represented in the team, that is for each skill s in S, there exists a member of the team having the skill s.
Does this problem have a name ? Does an efficient algorithm for solving it is known ?
Sounds like a set cover problem
Groups of items from l create a subset of s
Your problem is a minimum set cover problem:
Buy X items from M out of N lots where M is the minimum number of lots you need to obtain all of the X items.
In your example, skills are items and students are lots.
http://www.cs.sunysb.edu/~algorith/files/set-cover.shtml
The problem is NP-hard. The efficient way of solving it is to use the greedy set cover approximation algorithm.
精彩评论