algorithm - 寻找长度为 k 的路径

Question

给定具有 n 个节点的图，有许多串行方法可以增加复杂性并降低复杂性，以在图中找到长度为 k 的简单路径。目前最著名的渐近复杂度是O(2^k poly(n,k)) time。另一方面，一个简单的算法只是枚举所有长度为 k 的路径并花费 O(n^k) 时间（至少）。

您如何将朴素的算法转换为在 MapReduce 范式中有效工作？是否有此类东西的现有库？

Answer 1

MapReduce 是一个并行化框架，因此算法在一定程度上必须对并行化敏感，即我们可以将解空间的处理划分为独立的集合。我猜对于朴素算法，您可以告诉每个节点找到以固定图节点开头的 k-1 长路径。为简单起见，如果我们有 n 台机器，每台机器都可以搜索以 1、2、...、n 开头的 k-1 条路径。当然，并行化只提供恒定的时间改进。