可以在并行环境下运行递归函数吗？

Question

我有一个findAllPaths()函数，用于查找图中所有可能的路径（存储在matrix中）：

    public void findAllPaths(final Matrix matrix, final Index s, final Index d, HashMap <Index , Boolean> isVisited, Collection localPathList)
    {
        // Mark the current node
        isVisited.put(s, true);
        if (s.equals(d)) {
            this.pathsList.add(new ArrayList<>(localPathList));
            // if match found no need to traverse more till depth
            isVisited.put(s, false);
            return;
        }

        // Recur for all the vertices neighbors to current index
        for (Index i : matrix.getNeighbors(s)) {
            if (!isVisited.get(i)) {
                // store current node in path[]
                localPathList.add(i);
                findAllPaths(matrix, i, d, isVisited, localPathList);
                // remove current node in path[]
                localPathList.remove(i);
            }
        }

        // Mark the current node
        isVisited.put(s, false);
    }

我想尽可能地让它并行运行。

有人有什么办法可以实现吗？

- Tamir Hen

---

使用 ExecutorService 将递归调用作为任务而不是直接调用，然后使代码线程安全。同时将 localPathList 复制一份而非共享它。 - Andreas

Answer 1

您可能希望使用java.util.concurrent包的RecursiveTask或RecursiveAction，并在ForkJoinPool中运行它。这些类的一般思路是，在代码中决定哪些工作应该在一个线程中完成。如果工作量超过了这个部分，就将工作的一部分分离出来，并在新线程中执行。要获取所有线程的结果，请使用join()。这些类使用工作窃取算法：当一个线程完成时，它可以偷另一个线程的工作，因此这对于像这样的大量数字计算非常高效。

RecursiveTask或RecursiveAction的一个先决条件是，您应该能够将工作分成若干部分，并知道如何将完成的部分组合为最终结果。阶乘是可以使用RecursiveTask计算的一个例子：10！可以分为(1 * 2 * 3 * 4 * 5)和(6 * 7 * 8 * 9 * 10)。两个子结果可以相乘得到最终结果。

- Marko

---

您能否使用您的建议更改原帖作者的代码？这将极大地提高您的回答质量。 - rajah9