是否有一种有效的算法来找到 "maximal connected set"？
Is there an efficient algorithm to find the "maximal connected set"?
给定描述节点对之间连接的二维 table 布尔值，是否有一种有效的方法来找到最大的节点子集，其中所有节点都连接到所有节点？
具有 6 个节点的示例：
在这种情况下，"maximal connected set" 是 {node1, node4, node5}。虽然node0和node2、node3相连，但是node2和node3没有相连，所以不构成"connected set".
这是一个小例子，但我对原则上可以应用于非常大的 tables 的通用算法很感兴趣。
如果有帮助，我的 objective 是从 Table 重现 Mn 值本文作者：Sarwate，D.V，和 M.B。 Pursley，"Crosscorrelation Properties of Pseudorandom and Related Sequences," Proc。 IEEE，卷。 68，第 5 期，1980 年 5 月，第 583-619 页。
我将在 MATLAB 中对此进行编码，但我也相当流利地使用 C/C++。
EDIT：这是 table 我想重现以下结果：
- 第一列和第二列在这里并不重要（只是描述代码的长度）。
- 第 3 列是我所说的 "nodes" 的数量。
- 第 4 列是使用所有节点时的误差度量（无论
他们是否 "connected"。
- 如果仅使用 "maximal connected set"，第 6 列是（最小）错误。
- 第5列，Mn描述了最大连通集的节点数
你的问题等同于 - 事实上，它甚至可以被视为 - 图论中的最大团问题 的重述。图论恰好处理您正在谈论的结构：节点连接在一起，称为图，表示它们的一种方法就是上面的方法，称为邻接矩阵。
A "maximal clique" 正是您所描述的：图形节点的最大子集，每个节点都相互连接。
这个问题是 "NP-complete"，它基本上是一整套 class 被广泛推测但未被证明无法解决的问题 "efficiently"：特别是，那是什么意思是，关于以这种方式做出的最强猜想，具有合理性论据，这些问题至少是指数级时间-消费。也就是说，至少在一般情况下，您基本上不能比仅详尽地搜索整个图表做得更好。也就是说，对于 table 这么小的设备，即使对于家用计算机来说，对所有节点和连接的详尽搜索基本上仍然是即时的，但如果超过相对较小的规模，即使对于超级计算机来说也是不可行的。
给定描述节点对之间连接的二维 table 布尔值，是否有一种有效的方法来找到最大的节点子集，其中所有节点都连接到所有节点？
具有 6 个节点的示例：
在这种情况下，"maximal connected set" 是 {node1, node4, node5}。虽然node0和node2、node3相连，但是node2和node3没有相连，所以不构成"connected set".
这是一个小例子，但我对原则上可以应用于非常大的 tables 的通用算法很感兴趣。
如果有帮助，我的 objective 是从 Table 重现 Mn 值本文作者：Sarwate，D.V，和 M.B。 Pursley，"Crosscorrelation Properties of Pseudorandom and Related Sequences," Proc。 IEEE，卷。 68，第 5 期，1980 年 5 月，第 583-619 页。
我将在 MATLAB 中对此进行编码，但我也相当流利地使用 C/C++。
EDIT：这是 table 我想重现以下结果：
- 第一列和第二列在这里并不重要（只是描述代码的长度）。
- 第 3 列是我所说的 "nodes" 的数量。
- 第 4 列是使用所有节点时的误差度量（无论 他们是否 "connected"。
- 如果仅使用 "maximal connected set"，第 6 列是（最小）错误。
- 第5列，Mn描述了最大连通集的节点数
你的问题等同于 - 事实上，它甚至可以被视为 - 图论中的最大团问题 的重述。图论恰好处理您正在谈论的结构：节点连接在一起，称为图，表示它们的一种方法就是上面的方法，称为邻接矩阵。
A "maximal clique" 正是您所描述的：图形节点的最大子集，每个节点都相互连接。
这个问题是 "NP-complete"，它基本上是一整套 class 被广泛推测但未被证明无法解决的问题 "efficiently"：特别是，那是什么意思是，关于以这种方式做出的最强猜想，具有合理性论据，这些问题至少是指数级时间-消费。也就是说，至少在一般情况下，您基本上不能比仅详尽地搜索整个图表做得更好。也就是说，对于 table 这么小的设备，即使对于家用计算机来说，对所有节点和连接的详尽搜索基本上仍然是即时的，但如果超过相对较小的规模，即使对于超级计算机来说也是不可行的。