代码之家 › 专栏 › 技术社区 › lijie

布景封面的变化

complexity-theory algorithm

lijie · 技术社区 · 14 年前

集合覆盖优化问题是:给定一个宇宙 U 还有一套 S 的子集 U型 (即S-子集2^U),找到最小子集 C 属于 S公司 使其元素的结合 U型 . 众所周知是NP难。

我感兴趣的变化是,考虑到同样的事情( U型 和 S公司 ),找到最小子集 C类 属于 S公司 如此 C类 是一个封面,也适用于某些(未指定的)元素 u 在里面 U型 ,所有集合 S公司 包含 u型 在 C类 。

我应用这个的问题是:给定一组我看到的症状( U型 ),我有这些问题的潜在原因( S公司 -每个元素 S公司 对应于潜在多个症状的“原因”)。我希望能导致我看到的所有症状的原因最少,而且我还希望得到这样的结果:消除所有这些“原因”也将导致至少一个症状得到解决。

有人对这个问题是否比原来的问题简单有什么好的想法吗?

编辑以包含解决方案(包含注释)

它至少和封面一样硬。

SetCover(U,S) 可以通过 SetCoverNew(U + {w}, S + {{w}}) 具有 w 作为一个元素不在 U型 和 + 表示集合并。

给定SetCoverNew实例的任何解决方案都必须包含 {w} (否则,它不是 U + {w} ).

据称 封套(美国) 是 X = SetCoverNew(...) \ {{w}} . 第一, X 必须是 U型 ,否则 X + {{w}} 不能做封面 U+{w} . 其次, 十 必须是 U型 ,否则, SetCover(U,S) + {{w}} 是一个基数低于 SetCoverNew(...) .

2 回复 | 直到 14 年前

Itay Karo 14 年前

这也是NP难的,因为我们可以用它来解决原始集覆盖问题。
假设我们有一个解决这个新问题的算法(称为 SetCoverNew ).

这是一个求解SetCover的算法。

SetCover(U, S)
  1. build new universe U1 = {U + w} (w is not in `U`, and `+` means `union`).
  2. build the new set S1 = S + {w}.
  3. result = SetCoverNew(U1, S1, w)
  4. return result - {w}.

编辑对不起,我没看到 unspecified u 让我仔细想想:)

mcdowella 14 年前

前一段时间,我考虑了一个问题,即考虑到来自节点的各种报告,找出电信网络中的问题所在。要求是指定一些可能导致大量警报(警报风暴)的根本原因。有许多(非常昂贵的)产品在那里,采取了各种各样的方法。

我认为这个问题在理论上是很难解决的,因此唯一可行的方法是安排收集数据,以便使发现问题从何处开始的问题变得微不足道(例如,确保每个节点都报告了它认为它在做什么,以及它所依赖的节点是否在做它们的工作)。考虑到这一点,我认为您应该能够将大多数警报分配给根本原因,只需减去您希望由仪表显示的根本原因产生的警报即可。

我不知道你的问题域是什么,但我建议你花点时间看看收集正确的数据是否会使诊断更容易。