我有一组子图，我需要在从中提取它们的图上匹配它们。我还需要计算每个子图在此类图中出现的次数（我需要存储所有可能的匹配项）。考虑到子图和图的边标签必须完美匹配，但是顶点标签不需要相互匹配。我使用 JUNG API 构建了我的系统，所以我想要一个可以处理 JUNG 提供的图形结构的解决方案（api、算法等）。有什么想法吗？
问问题
1140 次
2 回答
0
JUNG 功能非常全面，因此如果 JUNG 中没有您需要的图形分析算法，通常有一个强有力的理论原因。对我来说，您的问题听起来像是子图同构问题的一个实例，它是 NP-Complete：
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
NP-Completeness 你可能熟悉也可能不熟悉（我花了 7 年的大学和计算机科学硕士学位才理解它！），所以我将在这里进行高级描述。某些问题，如排序，可以在多项式时间内就其输入大小解决。例如，如果我有一个包含N个元素的列表，我可以按 O( N log( N）） 时间。更具体地说，如果我可以在多项式时间内解决问题，这意味着我可以解决问题而无需穷尽所有可能的解决方案。在排序的情况下，我可以遍历列表的所有可能排列，如果找到已排序列表的排列，则返回它。这显然不是解决问题的最快方法！一些非常聪明的数学家能够将其降低到理论上的最小值 O( N log( N ))，因此我们可以使用今天的计算机非常快速地对非常大的事物列表进行排序。
另一方面，NP-Complete 问题被认为没有多项式时间解（我之所以这么说是因为没有人证明过这一点，尽管有证据表明确实如此）。无论如何，这意味着如果不先用尽所有可能的解决方案，您就无法最终解决 NP-Complete 问题。NP-Complete 问题的时间复杂度总是 O( c ^ N ) 或更糟，其中c是大于 1 的某个常数。这意味着解决问题所需的时间随着问题规模的每一次增量增加而呈指数增长。
所以这跟我的问题有什么关系？？？
我在这里得到的是，如果子图同构问题是 NP 完全的，那么确定一个图是否是另一个图的子图的唯一方法是用尽所有可能的解决方案。所以你可以解决这个问题，但可能最多只有几个节点左右的图（因为问题的时间复杂度随着图大小的每一次增量增加而呈指数增长）。这意味着为您的问题计算解决方案在计算上是不可行的，因为一旦您达到一定的图形大小，就需要很长时间才能找到解决方案。
更实际地，如果你的老板要求你做一些可以证明是 NP-Complete 的事情，你可以简单地说这是不可能的，他将不得不听你的。如果您的教授要求您做一些可证明是 NP-Complete 的事情，请向他展示它是 NP-Complete，您可能会在该课程中获得 A。如果你想自己做一些 NP-Complete 的事情，最好继续下一个项目...... ;)
于 2012-03-23T23:34:50.340 回答
0
好吧，我不得不通过从头开始实现它来解决这个问题。我遵循主题VF2 算法的任何工作示例中建议的策略？. 所以，如果有人也对这个问题有疑问，我建议看看 Rich Apodaca 在上述主题中的回答。
于 2012-03-27T20:36:06.060 回答