algorithm - 这个问题是 NP 问题吗，它有名字吗？

Question

这个问题在现实世界中出现过，但我已将其转化为更通用的“教科书式”表述。我怀疑它是 NP，但我特别想知道它是否有名字或是否广为人知，因为我想我不可能是第一个遇到它的人。 ;-)

假设有一个有 N 位客人的便餐聚会。每位客人可以带他/她的“招牌菜”参加聚会，也可以什么都不带。每个客人要么喜欢要么讨厌其他客人可能带来的每道菜(这是事先知道的，因为他们都是老 friend !)，但他们都喜欢自己的菜。

是否有一种确定性算法不需要指数时间来找到满足所有客人至少会找到他们喜欢的一道菜的约束的最小菜品集？我说的是“最小”，但实际上可能有多种解决方案，如果可能的话，我想知道所有的解决方案。

或者，以更抽象的方式，想象一个方阵，其中所有元素都为 0 或 1，并且所有对角线元素都为 1。最小的行集是什么，使得和(或二进制或)每组中的行没有零？ (行是菜品，列是客人，1 表示客人喜欢一道菜，对角线元素为 1，因为每个人都喜欢自己的菜。)

这可以推广到非方阵，或者通过删除 diagonal=1 规则(尽管后者保证总是至少有一个解决方案)。但我现在不关心那些案例......

我已经有一个程序可以通过穷举搜索来解决它并且对于 N 大约 20 来说足够快，但是它需要指数时间。我在想我可能需要重新使用随机算法来为更大的 N 值找到足够好的解决方案。

已添加

哇，感谢您的快速回答! “设置封面”，这就是我要找的名字。 :)

Answer 1

这叫做 SET COVER问题，它是 NP 完全的。