1

对于我作为一名实用程序员的明显数学缺陷,我向这个问题表示歉意。自从我在高中代数上表现出色,然后在任何更高的科目上都失败了,已经有 40 多年了。“NP-complete”和“NP-hard”问题的概念一直很难掌握,但我试过了。我什至购买并研究了似乎是这类问题的原始指南,计算机和难处理性: Michael R. Garey 和 David S. Johnson的 NP 完备性理论指南。

https://goodreads.com/book/show/284369.Computers_and_Intractability/

不管怎样。希望问题本身足够清楚。迄今为止,对于从任何地方提取所有唯一的完整子图(其中所有不同的节点(顶点)相互连接(通过唯一的边))的特定问题,什么是最好的公开可用的蛮力算法(具有有效的分支修剪)随机无向图?也就是说,该算法应该能够首先提取最大的唯一完整子图,无论可能有多少子图,然后按此顺序提取所有较小的唯一完整子图,这些子图(根据定义,我认为)包含在任何更大的唯一完整子图,从而避免重复产生非唯一(隐含)结果。

哎呀,像这样用清晰的英语拼出来让我有点头疼。希望这个描述仍然足够简单。一个标准的 C/C++/(甚至是 Python)库来为这个功能提供合理的计算资源,比如带有 64GB/128GB DRAM 的 Ryzen 5 3600 盒子会很棒,特别是如果可以在 1,024 个节点的完整分析中完成一两天,但我会尽我所能,非常感谢。

如果网络上某处有一个常见问题解答或文章,用英语涵盖了这个主题,并且可以被非数学家理解,那就更好了!

编辑:以下论文中的语言确实有点超出我的想象,但对于你们那里的计算数学家来说,你能确认它实际上确实解决了核心问题本身吗?如果是这样,我可以开始英勇地努力理解这个“Bron-Kerbosch”算法,并相信它是正确的道路。-_-

生成所有最大团和计算实验的最坏情况时间复杂度”,作者:Etsuji Tomita、Akira Tanaka 和 Haruhisa Takahashi

(电子通信大学信息与通信工程系,Chofugaoka 1-5-1, Chofu, Tokyo 182-8585, Japan)(Toyota Techno Service Corporation, Imae 1-21, Hanamotocho, Toyota, Aichi 470-0334 , 日本)

https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf

4

1 回答 1

1

是的,Bron--Kerbosch 就是你想要的。NetworkX中有一个实现,维基百科上有一些可读的伪代码,如果你知道你的集合运算符,还有一个你真正的Python 实现,并且可以通过搜索发现更多。

于 2021-01-28T13:47:37.027 回答