0

我有以下问题：给定一组男性和一组女性，任何两个人之间的等级等于 0 或 1。选择一个人的子集，这样：

  • 我想最大化被喜欢的人的数量（子集中任何两个人之间所有等级的总和）超过子集中的总人数。

  • 在挑选出来的人群中，男性和女性的数量必须相等。

我的问题是：为了显示这个问题的 np 完整性，我知道可以使用 clique 问题减少......有没有人可以提供一个关于如何进行这种减少的例子？我需要减少 FROM 或 TO 集团问题吗？非常感谢

4

2 回答 2

0

要回答您的问题，您需要将 FROM clique 问题简化为您当前正在处理的问题，因为 clique 是一个已知的 NP 完全问题。

至于您对转换过程的提示（从已知的 Clique 问题到您的 Ranking 问题），考虑这一点的一个好方法是如何将 clique 的场景减少到您的问题。我假设在您的问题中 1 表示“关联的人”，而 0 表示“不喜欢的人”。

将每个人作为我们在图 G 中的顶点（假设在集团问题中给定图）。为了区分男性和女性，我们将男性组标记为 A1,A2,A3...Am，将女性组标记为 B1,B2,B3...Bf。现在我们可以为他们之间排名为 1 的每一对人（喜欢的人）绘制边缘。假设在图完成后形成 N(N>=1) 个团。

现在，我们删除每个 clique 中使 clique 具有不相等数量的 As 和 Bs 的顶点（以提供两个性别的相同数量的顶点）。现在，编号为 K 的最大集团就是您要寻找的集团。

这种转换应该在多项式时间内完成，因为我们正在做的是完全重建我们的团图并标记它们（并删除它们）。执行这种转换将是 O(V+E)。

稍后，如果您想证明您的问题是 NP 完全的，您将需要证明您的问题答案和集团问题答案之间的答案都有效。

于 2019-04-22T22:20:46.923 回答
0

我不会为您写出实际的证明，但我希望以下关于如何构建证明的大纲有助于回答您的问题。

使用归约证明问题是 NP 完全的第一步是实际证明问题在 NP 中。也就是说，问题可以在多项式时间内得到验证。

你是怎样做的？ 您的问题能否转化为决策问题（如是/否问题） 该决策问题能否得到认证？您的决策问题是否有答案/解决方案？你能验证决策问题的证书可以在多项式时间内完成吗？如果是，那么您已经证明您的问题出在 NP 中。

现在您知道问题在 NP 中，您可以使用归约来证明问题是 NP-complete 或 NP-hard。（如果问题出在 NP 中，那么进行归约步骤绝对没有用，因为如果问题不在 NP 中，问题就不可能是 NP 完全的。）

为了减少，您应该将集团问题转换为您的问题。 你是怎样做的？好吧，考虑一下集团问题的哪些元素可以转化为你的问题的元素。您的问题中有男性/女性，但集团问题中有节点/顶点。在您的问题中存在等于 0（不喜欢）或 1（喜欢）的连接，但在 clique 问题中存在加权（或未加权的边）。您试图找到他们之间点赞数最多的人的子集，但在 clique 问题中，您正在最大化 clique 中的顶点数。在大多数情况下，它几乎看起来像是一对一的转换。你的问题的棘手部分是必须有偶数的男性和女性。为此，您需要更有创意，并找到改变集团问题的方法。

一旦你将问题从派系转换为你的问题，你就可以简单地证明对派系问题的回答就是对你的问题的回答，反之亦然。

这是证明问题是 NP-hard 的结构。最难的部分是转型过程。然而，关键是，如果你思考得足够深入，可以操纵集团问题，从而将其转化为你的问题。

希望有帮助！

于 2019-04-23T04:53:36.320 回答