0

我有一个巨大的节点有向图（100M+ 个节点），节点集之间有多个路径实例记录。任何两个节点之间的路径可能会有所不同，但我想找到的是共享多个中间节点的路径，除了主要偏差。

例如，我在节点 A 和节点 H 之间有 10 个路径实例。这 10 个路径实例中有 9 个经过节点 c、d、e、f - 但其中一个实例经过 c、d、z、e、f - 我想找到那个“奇怪”的实例。

有什么想法我什至会开始解决这样的问题吗？可能适合该任务的现有分析框架？

基于评论的详细信息：

  • PIR（路径实例记录）是经过的节点列表，每个边具有相关的边遍历时间。
  • 目前，原始 PIR 记录采用纯字符串格式 - 显然，我希望根据我最终选择分析它的方式以不同方式存储它。
  • 这不是一个解决路径的问题——我永远不需要找到所有可能的路径；我只需要分析采用的路径（每个路径都是 PIR）。
  • 需要从 PIR 生成子路径列表。

PIR 的示例类似于：nodeA;300;nodeB;600;nodeC;100;nodeD;100;nodeF

这转化为 A->BC->D->F 的路径；每个顶点的成本/时间是一个数字——例如，从 A->B 出发花费 300，从 B->C 出发花费 600，从 D->F 出发花费 100。每次进行遍历时，每次遍历的成本/时间都会有所不同。因此，例如，在一个 PIR 中，从 A->B 出发可能花费 100，但在下一个 PIR 中，从 A->B 出发可能花费 150。

4

1 回答 1

1

浏览路径列表并根据起始节点和结束节点将它们分解为集合。例如，以节点 A 开始并以节点 B 结束的所有路径都在同一个集合中。然后你可以对这些路径的子序列做同样的事情。因此，例如，具有子序列 a、b、c、d 的每条路径以及起始节点 y 和结束节点 k 都在同一个集合中。还可以根据需要反转路径，例如，您没有路径 k 到 y 的集合和路径 y 到 k 的集合。然后，您可以检查一个子序列是否足够常见，然后检查没有该子序列的路径是否有一个基于编辑距离的路径中的子序列与原始序列足够接近. 如果你只是对路径感兴趣，那么你可以简单地计算路径和子序列的编辑距离，减去长度的差异，然后检查结果是否足够低。最好使用路径的子序列，使其以与所需子序列相同的节点开始和结束。

对于您的示例，该算法最终将到达包含子序列 c、d、e、f 的路径集，并发现其中有 9 个。这超过了子序列足够常见（并且足够长，可能需要至少长度为 k 的序列）所需的数量，然后它将检查未包含的路径。在这种情况下，只有一个。然后它会直接或间接地注意到，只有删除 z 才会使序列 c,d,z,e,f 变为 c,d,e,f。这通过了“奇数”的（当前模糊的）要求，因此包含 c,d,z,e,f 的路径被添加到要返回的路径列表中。

于 2013-05-10T12:11:38.913 回答