时间戳

首页 > 解决方案 > 我如何并行化这个 DFS？

java - 我如何并行化这个 DFS？

问题描述

我有一棵二叉树，其中每个节点的值为 0 或 1，从root叶节点到叶节点的每条路径都代表一个一定长度的二进制字符串。该程序的目的是找到所有可能的二进制文件（即从到叶子String的所有可能路径）。root现在我想将它并行化，以便它可以使用多个内核。我假设我需要以某种方式拆分分支节点上的工作负载，但我不知道从哪里开始。我正在查看ForkJoin功能，但我不知道如何拆分工作然后将其组合起来。

public class Tree{
  Node root;
  int levels;

  Tree(int v){
    root = new Node(v);
    levels = 1;
  }
  Tree(){
    root = null;
    levels = 0;
  }
  public static void main(String[] args){
    Tree tree = new Tree(0);
    populate(tree, tree.root, tree.levels);
    tree.printPaths(tree.root);
  }

  public static void populate(Tree t, Node n, int levels){
    levels++;
    if(levels >6){
      n.left = null;
      n.right = null;
    }
    else{
      t.levels = levels;
      n.left = new Node(0);
      n.right = new Node(1);
      populate(t, n.left, levels);
      populate(t, n.right, levels);
    }
  }
  
  void printPaths(Node node)
   {
       int path[] = new int[1000];
       printPathsRecur(node, path, 0);
   }

  void printPathsRecur(Node node, int path[], int pathLen)
    {
        if (node == null)
            return;

        /* append this node to the path array */
        path[pathLen] = node.value;
        pathLen++;

        /* it's a leaf, so print the path that led to here  */
        if (node.left == null && node.right == null)
            printArray(path, pathLen);
        else
        {
            /* otherwise try both subtrees */
            printPathsRecur(node.left, path, pathLen);
            printPathsRecur(node.right, path, pathLen);
        }
    }

    /* Utility function that prints out an array on a line. */
    void printArray(int ints[], int len)
    {
        int i;
        for (i = 0; i < len; i++)
        {
            System.out.print(ints[i] + " ");
        }
        System.out.println("");
    }
}

标签： javaparallel-processingtreebinarydepth-first-search

解决方案

您可以使用线程池在单独的线程之间有效地分配负载。

一种可能的方法：

ExecutorService service = Executors.newFixedThreadPool(8);

Runnable recursiveRunnable = new Runnable() {

    @Override
    public void run() {
        //your recursive code goes here (for every new branch you have a runnable (recommended to have a custom class implementing Runnable))
    }
};
service.execute(recursiveRunnable);

但是，这种方法不再是第一次深度搜索，因为您在搜索第一个之前列出了您职位的子分支。据我了解，DFS 是一种严格的线性方法，因此不能完全并行化（尽管请在评论中纠正我）。

推荐阅读