我想在无向图中找到所有 k-clique。因此，我需要基于蚁群的精确算法来查找图中的所有 k-clique。例如，考虑这个相邻矩阵：
0 1 1 0 0
1 0 1 1 0
1 1 0 1 1
0 1 1 0 1
0 0 1 1 0
在这个相邻的矩阵中，我们有三个 3-clique：(1,2,3),(2,3,4),(3,4,5)
我想在每个图中找到这个 k-clique。note=K 是 K-clique 算法的输入。
问问题
262 次
2 回答
2
只要K是任意值作为问题输入，k-clique 问题就是NP-complete，这意味着没有什么比暴力算法更好的了 - 获取K节点的每个子图并检查它是否代表一个 clique。通过回溯实现这个想法的细节可以在这里找到。
于 2012-04-14T15:31:59.160 回答
1
重新标记以包含蚁群标签，但 Andrei 是正确的——蚁群优化不会打破 NP-Complete 障碍，尤其是 k-clique 问题甚至没有近似算法。（如果我没记错的话，近似算法不存在，除非 P=NP。）
我碰巧知道的关于 ACO 和集团问题的最新调查大约有六年的历史，链接如下。这是一项非常好的研究，包括针对四种独立技术的详尽模拟/基准测试，一个直接的结论是，在 2006 年，即使是最先进的 ACO 方法也不能保证在基准问题中获得实际的最大集团。
于 2012-04-14T16:24:26.643 回答