这个问题来源于现实生活,但我把它转化为更通用的“教科书式”表述。我怀疑它是NP问题,但我特别想知道它是否有一个名称或者是否众所周知,因为我认为我不可能是第一个遇到它的人。;-)
假设有N个客人参加聚餐派对。每个客人可以带来自己的“招牌菜”,也可以什么都不带。每个客人都喜欢或讨厌其他客人可能带来的菜肴(因为他们都是老朋友,这一点是事先已知的!),但他们都喜欢自己的菜肴。
是否存在一种确定性算法,不需要指数时间来找到满足约束条件的最小菜肴集,以便所有客人都能找到至少一道自己喜欢的菜肴?我说“最小的” ,但实际上可能会有多个解决方案,如果可能的话,我想知道它们全部是什么。
或者,更抽象地说,想象一个正方形矩阵,其中所有元素都是0或1,并且所有对角线元素都是1。哪些行的最小集合使得每个集合中行的和(或二进制OR)没有零?(行代表菜肴,列代表客人,1表示一个客人喜欢一道菜,由于每个人都喜欢自己的菜,因此对角线元素为1。)
这可以推广到非正方形矩阵,或者通过删除对角线=1规则来推广(尽管后者保证始终至少有一个解)。但是我现在不关心那些情况...
我已经有一个通过穷举搜索解决它并足够快的程序,适用于N约为20左右,但它需要指数时间。我想我可能需要求助于随机算法,以找到更大N值的足够好的解决方案。
添加
哇,谢谢你的快速回答!“集合覆盖”,这就是我正在寻找的名称。:)