c++ - 找到散列映射的最大独立子组的算法

Question

我需要一种算法来找到散列映射的最大独立子组，它在散列映射数组中表示。

我尝试遍历 hashmaps 数组并每次发送和索引，看看数组中的哪些 hashmaps 与该索引中的 hashmaps 不独立，它有效但在

A and B independent  
B and C independent  
but A and C can be not independent

HashMap 的最大独立子群的定义:

我有一个包含 hashmap 的数组，每个 hashmap 包含一个键，如果第一个 hashmap 中的每个键都没有包含在第二个映射中，则每两个 hashmap 称为独立的，所以我必须找到这些 hashmap 的子组，它们都是独立的

Answer 1

首先，这个问题是NP完全的。为了证明这一点，假设有一个带有索引边的图。为每个顶点创建一个 HashMap 并用该顶点的每个事件边的索引填充它。那么如果两个 HashMap 是独立的，则它们不包含相同的边，因此各自的顶点也是独立的。因此，找到这些 HashMap 的最大独立子集可为您提供图中的最大独立集，我们知道它是 NP 完全的。

你可以通过构造一个图来解决这个问题，每个 HashMap 都有一个顶点，每两个依赖的 HashMap 添加一条边，然后使用某种算法来计算独立集。另一种方法是采用补图并找到最大团。

由于这是低效的，您可以考虑使用一些近似算法。