sen*_*nel 6 algorithm complexity-theory
我们设置了S 1,S 2,...,S n.这些集合不必是不相交的.我们的任务是为每个集合选择一个代表成员,以便所选元素的总数尽可能小.一个元素可以存在于多个集合中,并且可以表示它所包含的所有集合.是否有算法可以有效地解决这个问题？
重述后更容易回答这个问题:让原始集合S 1,S 2,...,S n成为宇宙的元素,并让原始集成员自己设置:T 1,T 2,... ,T m(其中T i包含元素{ S j },它们是包含相应成员的原始集合).
现在我们必须用集合T 1,T 2,...,T m覆盖宇宙S 1,S 2,...,S n.这正是设置封面问题.这是一个众所周知的NP难问题,因此没有算法可以有效地解决它(除非P = NP,正如理论家通常所说).从维基百科页面可以看出,有一种贪婪的近似算法; 它是有效的,但近似比不是很好.