2

我有一大堆类似的东西（称之为小部件），我需要选择其中的一个子集。小部件可以与其他小部件发生冲突，并且可以将它们“比较”[1] 以查看哪个“更好”来解决冲突。我想选择包含尽可能多的非冲突小部件的最佳子集。

我希望我的选择是稳健和确定性的——如果我添加一些与许多其他小部件冲突的不相关小部件，我不希望这些小部件与未包含它们相比会改变结果——这就是我的意思是找到“确定性最佳”子集，一个唯一的子集，或者在最坏的情况下每次出现一组等效的子集时都是相同的。

我的实现看起来像这样：

Build a graph of widgets, where edges are conflicts between widgets.

While there are edges in the conflict graph:

    Make a list of the edges in the conflict graph, sorted so that the most
    conflicted widgets are at the front of the list.

    Pick the first edge in the list, compare the two, delete the loser. (note:
    this step includes tidying up the graph, which is why we need to refresh
    the list of conflict edges)

Make a list, possibles, of deleted widgets that don't conflict with any in the
final set.

Call this procedure recursively on possibles in case they're conflicted with
each other.

Add back the return values from the recursive call, and return the subset.

（不要太担心递归 - 它永远不会超出一次递归调用，因为在我的情况下可能的子集很小。）

不幸的是，这个算法并没有达到我想要的效果，因为它不受输入集的一些高度冲突的添加的影响！我认为这是因为我偏向于首先查看最不相关的小部件的过程，并且这些对冲突图中留下的边有连锁反应。我首先删除它们的目的是尽快消除它们的影响——这似乎被误导了。

大概这个问题类似于已解决的问题 - 如果是这样，如果有人能告诉我是哪一个，并且（甚至更好）简要解释他们参考中的任何行话，我将不胜感激！

如果不是（或者我的解释太模糊），请告诉我 CS 文献的哪些部分可以阅读。

[1] 比较有点适合排序（即，如果 w1 > w2 和 w2 > w3，那么我们免费知道 w1 > w3。）但是评估子集的“适合度”作为一个整体是行不通的因为没有明智的方法将 (w1, w2, w3) 与 (w1, w2, w4, w5) 进行比较。

4

1 回答 1

3

这是一个 NP 完全问题，称为“加权独立集”问题。我不确定您所说的“确定性”是什么意思，但一个简单的定义可能是“如果将小部件添加到输入集会导致输出集发生更改，则至少有一个添加的小部件包含在输出中set”——也就是说，新的小部件可以通过看起来有吸引力来改变输出，但它们不能与图表中不相关部分的内容发生冲突。

满足这一要求的简单近似是贪婪地识别一个最高分数的小部件，将其添加到输出集中，然后删除所有冲突的小部件。重复直到没有未选择的小部件剩余。不过，我不确定这是否能提供一个不错的近似保证。

于 2013-10-11T11:10:08.700 回答