这个问题是NP问题吗，有名字吗？
这个问题在现实世界中出现过，但我已将其转化为更通用的“教科书式”表述。我怀疑它是 NP，但我特别想知道它是否有名字或众所周知，因为我认为我不可能是第一个遇到它的人。 ;-)
想象一下有一个有 N 位客人的聚餐聚会。每位客人可以携带他/她的“招牌菜”参加聚会，也可以什么都不带。每个客人要么喜欢要么讨厌其他客人可能带来的每道菜（这是提前知道的，因为他们都是老朋友！），但他们都喜欢自己的菜肴。
是否有一种确定性算法，不需要花费指数时间来找到满足所有客人都会找到至少一道自己喜欢的菜肴这一约束的最小菜肴集？我说的是“最小”，但实际上可能有多种解决方案，如果可能的话我想知道它们。
或者，以更抽象的方式，想象一个方阵，其中所有元素都是 0 或 1，并且所有对角线元素都是 1。使得每个行中的行的总和（或二进制 OR）的最小行集是多少？设置没有零？ （行是菜肴，列是客人，1 表示客人喜欢一道菜，对角线元素为 1，因为每个人都喜欢自己的菜。）
这可以推广到非方阵，或者通过删除对角线 = 1 规则（尽管后者保证总会有至少一个解决方案）。但我现在不关心这些情况......
我已经有了一个程序，可以通过详尽的搜索来解决它，并且对于 N 大约 20 来说足够快，但它需要指数时间。我想我可能需要重复使用随机算法来为较大的 N 值找到足够好的解决方案。
已添加
哇，感谢您的快速回答！ “设置封面”，这就是我要找的名字。 :)
This problem came up in the real world, but I've translated it into a more generic "textbook-like" formulation. I suspect it is NP, but I'm particularly interested in knowing if it has a name or is well known since I think I can't be the first one to encounter it. ;-)
Imagine there is a potluck party with N guests. Each guest may bring his/her "signature dish" to the party, or bring nothing. Each guest either likes or hates each of the dishes that the other guests may bring (and this is known in advance since they are all old friends!), but they all like their own dishes.
Is there a deterministic algorithm that does not take exponential time to find the smallest set of dishes that satisfies the constraint that all guests will find at least one dish to their liking? I say "the" smallest, but actually there may be multiple solutions, and I'd like to know them all if possible.
Or, in a more abstract way, imagine a square matrix where all elements are either 0 or 1, and all diagonal elements are 1. What are the smallest sets of rows such that the sum (or the binary OR) of the rows in each set have no zeroes? (The rows would be the dishes, the columns would be the guests, 1 would mean that a guest likes a dish, and diagonal elements are 1 since everyone likes their own dish.)
This could be generalized to non-square matrices, or by removing diagonal=1 rule (although the latter guarantees that there will always be at least one solution). But I don't care about those cases for now...
I already have a program that solves it through an exhaustive search and is fast enough for N around 20, but it takes exponential time. I'm thinking I may need to recur to stochastic algorithms to find good-enough solutions for larger values of N.
Added
Wow, thanks for the quick answer! "Set cover", that's the name I was looking for. :)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这称为 SET COVER 问题，它是 NP 完全问题。
This is called the SET COVER problem and it is NP-complete.
正如 Antti Huima 链接到的维基百科文章中所描述的，布景封面问题缺乏每位客人喜欢自己菜品的特征。顺便说一句，我不知道这是否有什么区别。
The set cover problem, as described in the Wikipedia article which Antti Huima linked to, lacks the feature of each guest liking his own dish. Offhand, I don't know whether this makes any difference.