1

好的......所以我有一个棘手的问题(至少对我来说)。

我有一个简单对象的列表,我需要弄清楚如何找到利用最大数量的组合。这些对象的类中的每一个都有一个属性(字符串)作为它们的名称,一个属性(列表)用于它们喜欢与之结合的其他元素的名称,以及一个属性(列表)用于它们所使用的其他元素的名称不喜欢绑定。

如果一个元素被添加到一个集合中,其中该特定元素“喜欢”该集合中已经存在的一个(或多个)其他元素,则添加的元素为它喜欢的集合中的每个项目返回 +1 的分数。同样,对于添加的元素不喜欢的集合中的每个其他元素,都会返回 -1 的分数。将所有元素添加到最终集合后,每个元素的分数必须 >= 0。

我将如何找到可以使用的元素组合来返回最大的集合?如果多个组合返回相同数量的元素,则应返回所有可能的组合。

我希望这是有道理的......另外,我使用的是 C#(.NET 4.0),但可以使用任何编程语言,我只需要弄清楚它背后的逻辑。

在此先感谢,
桑尼

4

1 回答 1

2

我认为你说这是一个棘手的问题是对的。我认为对象是图中的节点,而喜欢/不喜欢的信息则为节点之间的链接赋予权重。忽略“like”字段并为所有链接赋予权重 0 或权重 -1。在这种情况下,您的问题是找到最大节点数,以使它们之间的所有链接的权重为 0,并且没有一个链接的权重为 -1。假设您有一个程序可以有效地执行此操作。

现在看看问题http://en.wikipedia.org/wiki/Clique_problem,这是一个已知的难题。如果您有最大集团问题,则在所有节点之间创建链接。如果两个节点在最大 clique 中链接,则权重为 0。如果链接不存在,则权重为 -1。现在运行一个程序来解决你的问题,你已经解决了 max clique。所以我认为你的问题是 NP-Complete,并且不太可能有一个有效的解决方案。

于 2011-10-21T04:17:38.637 回答