如何并行这个dfs?

bq3bfh9z  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(354)

我有一个二叉树,其中每个节点的值为0或1,从根节点到叶节点的每个路径表示一个特定长度的二进制字符串。程序的目的是找到所有可能的二进制字符串(即从根到叶的所有可能路径)。现在我想把它并行化,这样它就可以使用多个核。我假设我需要以某种方式在分支节点上分配工作负载,但是我不知道从哪里开始。我正在研究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("");
    }
}
t98cgbkg

t98cgbkg1#

您可以使用线程池在不同的线程之间有效地分配负载。
一种可能的方法:

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是一种严格的线性方法,因此不能完全并行(尽管可以在评论中纠正我)。

相关问题