找到不冲突的子集的确定性最好的选择 [英] find a deterministic best choice of non-conflicting subset
问题描述
我有一个大集相媲美的东西（叫他们小部件），我需要选择其中的一个子集。的部件可以与其它窗口小部件可以相冲突，并且可以将它们相比[1]，看它是更好，以解决冲突。我想选择一个包含许多非冲突的部件尽可能最好的子集。
I have a big set of comparable things (call them widgets), and I need to choose a subset of them. The widgets can be conflicted with other widgets, and they can be "compared"[1] to see which is "better" to resolve the conflicts. I want to choose the best subset that contains as many non-conflicting widgets as possible.
我想我的选择是稳健性和确定性 - 如果我添加一些无关痛痒的小部件，它们有很多其他人的冲突，我不希望这些改变的结果相比，如果他们没有被列入 - 这就是我所说的每一次寻找确定性最好的子集，一个独特的一个，或在最坏的情况相同的一出一组子集是等价的
I want my choice to be robust and deterministic - if I add some irrelevant widgets that conflict with lots of others, I don't want these to change the result compared to if they hadn't been included - this is what I mean by finding the "deterministic best" subset, a unique one, or at worst the same one every time out a set of subsets that are equivalent.
我的实现看起来是这样的：
My implementation looks something like this:
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.
（不要太担心了递归 - 它从来没有下降超过一个递归调用作为候选条件子集小在我的情况。）的
不幸的是，这种算法并没有做我想做的是不受少数高度冲突增加的输入设置条件！我想这是因为我偏置程序来看看第一个最不相关部件的方式，而这些具有连锁效应上边缘留在冲突图。我在删除它们的目的首先是要尽快消除他们的影响力 - 看来这是错误的。
Unfortunately, this algorithm doesn't do what I want in terms of being immune to a few highly conflicted additions to the input set! I think this is because of the way I bias the procedure to look at the most irrelevant widgets first, and these have a knock-on effect on which edges are left in the conflict graph. My aim in deleting them first was to remove their influence as soon as possible - it seems this was misguided.
presumably这个问题类似于一个解决了一个 - ！如果是这样，我会很感激，如果有人能告诉我是哪一个，和（甚至更好）简要说明任何行话他们引用
Presumably this problem is analogous to a solved one - if so, I'd be grateful if someone could tell me which one, and (even better) briefly explain any jargon in their references!
如果没有（或我的解释太模糊）请让我知道什么是CS文学的部分去阅读。
If not (or my explanation is too vague) please let me know what parts of the CS literature to go and read.
[1]比较排序适合排序（即，如果W1> W2和W2> W3，那么我们就知道自由是W1> W3）的但的评价健身的一个子集作为一个整体的是行不通的，因为没有合理的方式来比较（W1，W2，W3）至（W1，W2，W4，W5）。
[1] comparison is sort-of suitable for sorting (i.e., if w1 > w2 and w2 > w3, then we know for free that w1 > w3.) but evaluating the "fitness" of a subset as a whole wouldn't work as there's no sensible way to compare (w1, w2, w3) to (w1, w2, w4, w5).
推荐答案
这是被称为加权独立集问题的NP完全问题。我不知道是什么，你的确定性，但一个简单的定义，意味着可能是如果将小工具添加到输入设置导致改变输出设置，添加小部件中的至少一个包含在输出集 - 即，新的小部件可以通过查看吸引力改变输出，但它们不能与在图中的不相关的部分的东西回事螺杆
This is an NP-complete problem known as the "weighted independent set" problem. I'm not sure what-all you mean by "deterministic", but one easy definition might be "if adding widgets to the input set results in a change to the output set, at least one of the added widgets is contained in the output set" -- that is, new widgets can change the output by looking attractive, but they can't screw with stuff going on in unrelated parts of the graph.
这信纳将是贪婪地确定一个最高得分小部件，将其添加到输出设定，然后删除所有冲突的小部件的简单近似。重复，直到没有未选择的部件依然存在。我不知道这是否给出了一个体面的近似保证，虽然。
A simple approximation which satisfied that would be to greedily identify a maximum-score widget, add it to the output set, then remove all conflicting widgets. Repeat until no unselected widgets remain. I'm not sure if this gives a decent approximation guarantee, though.
这篇关于找到不冲突的子集的确定性最好的选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
