深度优先的并行搜索 [英] Depth First Search in Parallel

问题描述

我有一个巨大的二进制树（每个节点有一个合格和不合格节点），我想遍历该树，以获得使用DFS所有可能的路径。由于该树是巨大的，用一个单独的线程采取DFS的时间正在很长的时间。因此，为了解决这个问题，我现在考虑做平行DFS。其基本思想是如下。

I have a huge binary Tree (each Node has a Pass and Fail Node) and I want to traverse this Tree in order to get all possible Paths using DFS. Since the tree is huge, the time taken to DFS using a single thread is taking very long time. So in order to solve this problem, I am now considering doing parallel DFS. The basic idea is below.

• 在开始使用一个线程，做一个正常的DFS，因为这打一个结，产生一个新的线程开始与失败节点作为起始节点，并传递给调用节点走了这么远
• 在初始线程继续在通
的路径
• 在结束每一个线程将返回节点，它已经行进的列表;因为这样我会遍历整个树与多个主题。由于所谓的父线程通过它前往子线程的节点的信息，每个线程是所谓的自足

为了实现这一点，我想这样做的

In order to implement this, I am thinking of doing this

• 使用newCachedThreadPool。
• 在主，我将创建池，并开始给可调用DFS一类初始调用。在DFS类的构造函数也将采取的ExecutorService因此使用该规则的新生成的线程也可以产生新的主题如上面所讨论

code DFS的实施

    public class DFS implements Callable<List<List<TestNode>>> {
        private Node node = null;
        private List<TestNode> testNodeList = new ArrayList<TestNode>();
        private List<List<TestNode>> returnNodeList = new ArrayList<List<TestNode>>();
        private ExecutorService service = null;

        public DFS(ExecutorService service, Node node, List<TestNode> initList) {
           this.node = node;
           this.service = service;
           if (initList != null && initList.size() > 0) {
              testNodeList.addAll(initList);
        }
    }

    public List<List<TestNode>> call() throws Exception {
         performDFS(this.node);
         returnNodeList.add(testNodeList);
         return returnNodeList;
    }

    private void performDFS(Node node) {
         TestNode testNode = new TestNode();
         testNode.setName(node.getName());
         Thread t = Thread.currentThread();
         testNode.setThreadName(t.getName());
         testNodeList.add(testNode);

         if (node.getPass() != null) {
            performDFS(node.getPass());
         }
         if (node.getFail() != null) {
             Callable<List<List<TestNode>>> task = new DFS(service, node.getFail(),         
             this.testNodeList);
             Future<List<List<TestNode>>> returnList = service.submit(task);
             try {
                 returnNodeList.addAll(returnList.get());
             }
             catch (InterruptedException e) {
             }
             catch (ExecutionException e) {
             }
       }
    }

}

主类

    public static void main(String[] args) {
          Main main = new Main();
          Node root = main.createTree();
          ExecutorService service = Executors.newCachedThreadPool();
          Callable<List<List<TestNode>>> task = new DFS(service, root, null);

          Future<List<List<TestNode>>> returnList = null;
          try {
             returnList = service.submit(task);
         }
         catch (Exception e) {
         }
         try {
            main.displayTestNode(returnList.get());
            service.shutdown();
         }
         catch (InterruptedException e) {
        }
        catch (ExecutionException e) {
      }
   }

问题

• 这是否有道理？这甚至可能？
• 在有问题的执行情况，我可以一次又一次地看到相同的线程

推荐答案

是的，这是可以编写一个平行的DFS。这或许还可以使用线程池，但叉/加入 - 风格的算法，我会觉得更自然。叉操作将遍历并行节点的所有孩子，而join操作将只是在连接的路径列表返回。

Yes, it is possible to write a parallel DFS. It might also be possible using thread pools, but a fork/join-style algorithm would I think be more "natural". The fork operation would traverse all children of a node in parallel, while the join operation would simply concatenate the lists of paths returned.

这篇关于深度优先的并行搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！