我正在使用相对较小的有向图（~10 个节点），每个有~10,000 个简单的路径和循环。我想维护一个总成本的排序列表，以遍历所有这些简单的路径和周期。我的边有几个不同的权重，但聚合函数对于所有这些都是可交换的/关联的（例如总和和乘积）。
现在，我正在使用 rethinkdb（一个 nosql 数据库）和 python。我正在预先计算所有可能的简单路径，将它们存储在哈希图中，并且每次更新边缘权重时，只需蛮力重新计算遍历就会花费它们。我的哈希图将给定的边（其权重刚刚更新）指向它所属的所有简单路径和循环。然后我去重新计算每一个的遍历成本。
好吧，我发现这非常慢并且无法扩展！我知道这是一个难题，但希望它适用于我相对较小的图表。
我最初的方法的一个低效率似乎在于每条路径的浪费冗余计算，即使有些是彼此的聚合。例如，A→B→C→D→E 的成本是 A→B→C 和 C→D→E 的组合。那么为什么不巧妙地计算它们呢？我想出了一种方法来做到这一点，但它似乎没有一点帮助，这让我觉得我真的需要退后一步。
所以我上网搜索了一下，偶然发现了这篇很有帮助的文章： https ://blog.blazegraph.com/?p=628 。它说：
大图反模式是“将所有内容放入大图中，然后使用为我们提供水平缩放以解决其他问题的相同工具：map/reduce 和键值存储。”</p>
令我震惊的是，这正是我一直在做的（错误的）。
似乎 GPU 是文章中提到的内存带宽问题的正确解决方案......除了我不确定如何并行处理这个问题。
问题：
如何并行处理这个问题？收集-应用-分散是正确的方向吗？以前在哪里做过？
我如何在不并行的情况下有效地优化当前方法？
作为参考，这是我当前算法的草图：
- 枚举我的图表中的所有简单路径和循环
保留边缘及其权重的字典。例如，如果
('A','B')是从节点A到节点的边B，edges_weights[('A','B')] # -> {'x': 1.3, 'y': 32, 'z': 0.231232}保留每条边所涉及的所有简单路径和循环的字典，例如：
paths_containing_edges[('A','B')] # -> # [ # (('A','B'), ('B','C')), # (('A','B'), ('B','C'), ('C','D')), # (('A','B'), ('B','C'), ('C','A')), # ... # (('A','B'), ('B','C'), ('C','D'), ('D','A')) # ]此外，初始化路径字典及其成本：
paths_costs = { (('A','B'), ('B','C')): {'x': ..., 'y': ..., 'z': ...} }更新边缘时：
一世。更新其权重
edges_weightsii. 查找包含这条边的所有简单路径并更新它们：
fn = lambda p,q: p+q # the cost aggregation function weight_keys = ['x','y','z'] for path in paths_containing_edges[updated_edge]: # path is a tuple of edge tuples, i.e. (('A','B'),('B','C'),('C','D')) for w in weight_keys: paths_costs[path][w] = reduce(fn,[edges_weights[e][w] for e in path])
显然有很多嵌套循环和查找正在发生......但我正在努力了解如何以不同的方式做事。