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 条路径。当然，并行化只会带来恒定的时间改进。