algorithm - 在旅游中容纳最多的人

Question

我得安排一次旅行。有N个人想参加旅游。但他们中的一些人是彼此的敌人。 (敌人的敌人可能是也可能不是你的敌人。如果 A 是 B 的敌人，那么 B 也是 A 的敌人) 如果我在我的旅行中容纳一个人，我就不能容纳他的敌人。

现在我想在游览中容纳尽可能多的人数。我怎样才能找到这个号码？

例如:如果有 5 个游客，我们称他们为 A-E。 A与B、D为敌，B与E为敌，C与D为敌。

   A    B   C   D   E
  +---+---+---+---+---+
A | - | X |   | X |   |
  +---+---+---+---+---+
B | X | - |   |   | X |
  +---+---+---+---+---+
C |   |   | - | X |   |
  +---+---+---+---+---+
D | X |   | X | - |   |
  +---+---+---+---+---+
E |   | X |   |   | - |
  +---+---+---+---+---+

在这种情况下，以下行程是可能的:空、A、B、C、D、E、AC、AE、BC、BD、ACE、CE、DE 等。其中，最好的行程是 ACE，因为它可容纳 3游客，因此答案 3。

我的方法:

• 我尝试循环并尝试与位图组合，但它们是 很慢。
• 我目前正在使用 DFS，但正在尝试寻找更好的 方法。
• 我尝试通过创建友谊图来工作并准备一些
  生成树。但这是行不通的，因为 A 可以和 B 一起旅行，B 也可以
  与 C 一起旅行并不能保证 A 和与 C 一起旅行。
• 我尝试创建敌对图并找到一些薄弱环节 但最终一无所知。

如果有人能给我提示或指出解决此问题的好资源，我将不胜感激。

Answer 1

根据游客创建图表:

• 每个节点都是游客
• 如果两个游客是敌人，则在他们之间划清界限
• 找到最大独立集

这篇论文中有非常详细的寻找最大独立集的算法: Algorithms for Maximum independent Sets

此方法提供了一种并行方法:Lecture Notes on a Parallel Algorithm for Generating a Maximal Independent Set

和this是java实现。