二分圖算法

Question

考慮以下與圖論相關的問題：

讓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 ，
• 等

[在該示例中，DATAS隨機給出。

我們的目標是從我在在小號每技術人員將會在球隊表示這樣的方式建立的最低一些個人組成的小組，即每個技能小號 in S，存在技能s的團隊成員。

這個問題有一個名字嗎？是否知道解決這個問題的有效算法？

Answer 1

聽起來像是項目的set cover problem
組從升創建的小號

Answer 2

你的問題的一個子集是最小集合覆蓋問題：

購買X的M項目出來的N個地段，其中M是獲得所有X個項目所需的最少手數。

在你的例子中，技能是項目，學生是很多。

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

的問題是NP難問題。解決它的有效方法是使用貪心集覆蓋近似算法。