集合覆盖问题

✍ dations ◷ 2025-04-04 12:49:43 #组合数学,计算机科学,计算复杂性理论

集合覆盖问题( Set covering problem,SCP)是组合数学、计算机科学和计算复杂性理论中的一个经典问题。

集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。

给定全集 U {\displaystyle {\mathcal {U}}} 指一个集合 C {\displaystyle {\mathcal {C}}} C S {\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}} ,且 C {\displaystyle {\mathcal {C}}} 的元素的并集为 U {\displaystyle {\mathcal {U}}}

集合覆盖问题的决定性问题为,给定 ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} 和一个整数 k {\displaystyle k} ,求是否存在一个大小不超过 k {\displaystyle k} 的覆盖。集合覆盖的最佳化问题为给定 ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} ,求使用最少的集合的一个覆盖。

决定性问题的集合覆盖是NP完全问题,最佳化问题的集合覆盖是NP困难问题。

此外,问题可以在每个集合上添加权值而变为带权集合覆盖问题。

相关

  • 昆虫见内文昆虫在分类学上属于昆虫纲(学名:Insecta),是世界上最繁盛的动物,已发现超过100万种。其中单鞘翅目(Coleoptera)中所含的种数就比其它所有动物界中的种数还多。昆字原作䖵。昆
  • NMDARN-甲基-D-天门冬胺酸受体(英语:N-methyl-D-aspartate receptor,简称NMDA受体或NMDAR)为麸胺酸盐受体,是一个主要的分子装置,控制突触的可塑性与记忆功能。NMDA受体是一种离子型麸
  • 西班牙超级人瑞列表这些是西班牙的超级人瑞(年龄超过110岁)西班牙的史上最长寿者是安娜·玛丽亚·薇菈·鲁比欧,史上最长寿男性是琼·里路德阿伯特,享嵩寿114岁81天。西班牙的在世最长寿男性是Fr
  • 太阳太阳物理学(solar physics)是研究我们的太阳,它是天文物理学的分支,对最接近我们的恒星尽可能的进行精密观测,进行研究、利用和解释。它与许多纯科学都有交集,像是物理学、天文
  • 灵猫科灵猫科(学名Viverridae)是食肉目下的一个科,包括大灵猫、小灵猫、熊狸等。
  • 宣和遗事《大宋宣和遗事》,简称《宣和遗事》,是知名的话本,是成书于南宋的笔记小说辑录,结合了多个类型的笔记小说并以说书的方式连贯而成,作者不详。现今流传为后人所著,已非宋代原本。宣
  • 塞尔维亚人塞尔维亚人 (塞尔维亚语:Србијанци/Srbijanci)是居住于塞尔维亚的区域居民称谓词,常用于塞尔维亚族人,但是泛指不分种族居住于塞尔维亚的人。在塞尔维亚语中,“Srbi”被
  • 澳大利亚国家篮球联赛澳大利亚国家篮球联赛(英语:National Basketball League)是澳大拉西亚最高级别的职业篮球赛事。 联赛始于1979年,赛事通常在夏季举行(4月 - 9月),这一模式沿袭了20年直到1998年。在
  • 京滨东北线京滨东北线(日语:京浜東北線/けいひんとうほくせん  */?)是日本一条由埼玉县埼玉市大宫区大宫站开始,途经东京都千代田区东京站,以神奈川县横滨市西区横滨站结束,由东日本旅客铁
  • 割据割据在一个国家内,是指一些可称为豪强、军阀的地方政治势力或政权,拥有一定武装力量,对外强调其控制之地区脱离原国管治架构而高度自治,不承认既有中央政府的地籍、税赋、人事等