标签: independent-set

我需要一个算法来查找树中的最大独立集.我想从所有叶节点开始,然后删除直接父节点到这些叶节点,然后选择我们删除的父节点的父节点,递归地重复这个过程,直到我们到达root.这是在O(n)时间内完成的吗？任何回复表示赞赏.谢谢.

并且有人可以请指出一个算法来找到树中的最大支配集.

我不相信存在一种算法,用于在二分图中找到最大独立顶点集,而不是在所有可能的独立集中找到最大值的强力方法.

我想知道找到所有可能的顶点集的伪代码.

假设给出了一个带有4个蓝色顶点和4个红色的二分图.目前我会的

Start with an arbitrary blue,
  find all red that don't match this blue
  put all these red in Independent Set
  find all blue that dont match these red
  put these blue in Independent Set
  Repeat for next vertex in blue

Repeat all over again for all blue then all vertices in red.

我知道这种方式根本不能给我所有可能的独立集合组合,因为在第一步之后我选择了所有不匹配的颜色顶点而不是逐步完成所有可能性.

例如,给出具有匹配的图表

B  R
1  1
1  3 
2  1
2  3
3  1
3  3
4  2
4  4

Start with blue 1
  Choose …

所以我正在练习一些编程面试问题,并偶然发现了这个样本pdf,它推荐"了解如何使用蒙版并以独立于机器的方式创建它们".但它没有阐明机器相关和机器独立掩模之间的区别.

我通常只计算出提供我想要的掩码的整数,例如,如果我只想要最后4位,我会做:

int y = x & 15;

我不明白为什么这会依赖于机器,如果是的话.

那么创建一个与机器无关的掩码的例子是什么？什么是创建依赖于机器的掩码的示例？

也许他们正在谈论的是如果你需要一个不是整数的东西的掩码,在这种情况下我的方法是行不通的(除了整数之外我什么都不需要掩码)？

考虑包含n个2D点的单位正方形.如果它们之间的欧几里德距离大于1,我们说两个点p和q在一个正方形中是独立的.单位正方形最多可以包含3个相互独立的点.我想在给定的单位平方中找到O(n log n)中的那3个相互独立的点.可能吗？请帮我.

在不使用任何空间数据结构(如Quadtree,kd-tree等)的情况下,可以在O(n ^ 2)中解决此问题吗？

给出二分图.每个顶点都有一些整数值 - 权重.

是否有可能在多项式时间内在此图中找到最大加权独立顶点集？

如果存在这样的解决方案,这个问题的算法是什么？

我正在从这里（第 8、9 页）阅读有关 NP 硬度的信息，并且在注释中，作者将 3-SAT 形式的问题简化为可用于解决最大独立集问题的图形。

在示例中，作者将以下 3-SAT 问题转换为图形。3-SAT 问题是：

(a ? b ? c) ? (b ? ~c ? ~d) ? (~a ? c ? d) ? (a ? ~b ? ~d)

生成的等效图为：

作者指出，如果满足以下条件，则两个节点通过边连接：

1. 它们对应于同一子句中的文字
2. 它们对应于一个变量及其逆。

我无法理解作者是如何提出这些规则的。

• 为什么我们需要在变量和它的逆之间画边？
• 假设有两个子句，子句 1 有 (a,b,~c) 和子句 2 有 (~a,b,c) 连接子句 1 到子句 2，为什么我们必须连接 a 和 ~a？为什么我们不能将 a（第 1 条）与 c（第 2 条）连接起来？

我有一个图像名称列表和一个（阈值）相似度矩阵。相似关系是自反的和对称的，但不一定是传递的，即如果image_i与image_j和相似image_k，那么它不一定意味着image_j和image_k是相似的。

例如：

images = ['image_0', 'image_1', 'image_2', 'image_3', 'image_4']

sm = np.array([[1, 1, 1, 0, 1],
               [1, 1, 0, 0, 1],
               [1, 0, 1, 0, 0],
               [0, 0, 0, 1, 0],
               [1, 1, 0, 0, 1]])

相似度矩阵sm解释如下：如果sm[i, j] == 1然后image_i和image_j相似，否则它们不相似。在这里我们看到image_0与image_1and相似image_2，但image_1和image_2不相似（这只是非传递性的一个例子）。

我想保留最大数量的唯一图像（根据给定的sm矩阵，它们都是成对非相似的）。对于这个例子，它是[image_2, image_3, image_4]或[image_1, image_2, image_3]（通常有多个这样的子集，但我不介意保留哪个，只要它们是最大长度）。我正在寻找一种有效的方法来做到这一点，因为我有成千上万的图像。

编辑 …