2

首先，我是一个 Java 初学者，所以我不确定这是否可能！基本上我有一个巨大的（3+百万）关系数据数据源（即A是B+C+D的朋友，B是D+G+Z的朋友（但不是A - 即不互惠的）等），我想要在这个（不一定是连接的）有向图中找到每个循环。

我找到了Finding all cycles in graph的线程，这让我想到了Donald Johnson 的（基本）循环查找算法，至少从表面上看，它看起来像我所追求的（我要试试当我周二回到工作岗位时 - 认为同时询问不会有什么坏处！）。

我快速浏览了Johnson算法的Java实现代码（在那个线程中），看起来关系矩阵是第一步，所以我想我的问题是：

a) Java 是否能够处理 3+million*3+million 矩阵？（计划用二元稀疏矩阵表示 A-friends-with-B）

b) 我需要找到每个连通子图作为我的第一个问题，还是循环查找算法会处理不相交的数据？

c) 这实际上是解决问题的合适方法吗？我对“基本”周期的理解是，在下图中，不是选择 ABCDEF，而是选择 ABF、BCD 等，但这并不是世界末日。

    E
   / \
  D---F
 / \ / \
C---B---A

d) 如有必要，我可以通过加强关系中的相互性来简化问题 - 即 A-friends-with-B <==> B-friends-with-A，如果真的有必要，我可以减少数据大小，但是实际上，它总是在 100 万左右。

z) 这是 P 任务还是 NP 任务？！我咬得比我能咀嚼的多吗？

谢谢大家，任何帮助表示赞赏！安迪

4

3 回答 3

2

您正在做的事情类似于数据挖掘中一个经过充分研究的问题，称为关联规则挖掘或更普遍的频繁项集挖掘。您可以通过频繁项集挖掘找到的东西比您正在做的更具体，但也更有用。

我们将使用封闭频繁项集挖掘，这将找到所有朋友组，其中每个人都是彼此的朋友。

我现在要说的是，Java 不能做你想让它做的事情。它无法加载那么多内存，并且在任何合理的时间内处理该数据的效率也不够高，您将需要使用 C/C++。我建议使用 LCM，它是一个封闭的频繁项集挖掘器，但由于您拥有的数据量，您还需要将支持设置得相当高。

您可能要考虑的另一件事是阅读大型图挖掘，这也是一个相当大的研究领域，但 Java 不会削减它。此外，您将无法找到数据中的所有循环（除非它非常稀疏），它们将会太多。它们也将重叠并且不是很有意义，您可能会找到几个最大的周期。

于 2010-05-30T17:53:51.617 回答
0

找到每个周期听起来并不合理。将有指数级的循环，所有循环都相互重叠。

至于 P 或 NP，最慢的部分实际上是枚举每个循环（因为它们可能有很多）。如果没有循环，则存在线性算法。

也许您实际上想将图形划分为双连接组件？请参阅http://en.wikipedia.org/wiki/Biconnected_component

此外，将图形存储在矩阵中几乎是不合理的。理论上听起来不错，但在实践中无法扩展，请改用邻接列表（http://en.wikipedia.org/wiki/Adjacency_list）

于 2010-05-30T16:47:22.543 回答
0

c) 这实际上是解决问题的合适方法吗？我对“基本”周期的理解是，在下图中，不是选择 ABCDEF，而是选择 ABF、BCD 等，但这并不是世界末日。

    E
   / \
  D---F
 / \ / \
C---B---A

不。唐纳德约翰逊论文意义上的“基本”意味着简单，即没有节点在圆圈中出现两次。这意味着算法不会选择AFBCDBA，但会选择ABCDEF。

d) 如有必要，我可以通过加强关系中的相互性来简化问题 - 即 A-friends-with-B <==> B-friends-with-A，如果真的有必要，我可以减少数据大小，但是实际上，它总是在 100 万左右。

无向图具有（非简单）循环的向量空间（具有很好的基础等），但我不知道它是否会对您有所帮助。

z) 这是 P 任务还是 NP 任务？

这是一个枚举问题，它本身不能在 P 或 NP 中。

于 2010-05-30T16:33:27.573 回答