我想知道一种快速算法,只找到大约 100 个顶点的图的团数(实际上没有找到团)。
我正在尝试解决以下问题。 http://uva.onlinejudge.org/external/1/193.html
我想知道一种快速算法,只找到大约 100 个顶点的图的团数(实际上没有找到团)。
我正在尝试解决以下问题。 http://uva.onlinejudge.org/external/1/193.html
这是 NP 完全的,你不能比实际找到最大团并计算它的顶点更好。来自维基百科:
集团问题包括:
- 解决测试图是否包含大于 N 的团的决策问题
这些问题都很困难:集团决策问题是完全
NP
的(卡普的 21 个NP
完全问题之一),
如果您可以在 中找到团数P
,则决策问题在 中是可回答的P
(您只需计算团数并将其与 进行比较N
)。
既然决策问题是NP-Complete
,求一般图的团数必然是NP-Hard
。
尽管问题是 NP 难题,但您提到的图形大小对于当今最快的最大团精确求解器(对于任何配置)来说都不是问题。
如果您准备好实现代码,那么我建议您阅读与算法系列 MCQ、MCR 和 MCS 以及系列 BBMC、BBMCL 和 BBMCX 相关的论文。一个有趣的起点是 Prosser [Prosser 12]的比较调查。它包括对这些算法的 Java 实现的解释。
正如其他人已经说过的,这可能真的很难。
但就像许多理论上的难题一样,如果有好的算法和合适的数据,它在实践中可能会很快。如果你实现了类似 Bron-Kerbosch 的方法来寻找派系,同时跟踪你迄今为止找到的最大派系大小,那么你可以回溯到没有结果的搜索树。
例如,如果您发现其中有 20 个节点的团,并且您的网络中有大量度数小于 20 的节点,您可以立即将这些节点排除在进一步考虑之外。另一方面,如果度数分布更均匀,那么这可能与找到所有派系一样慢。