0

我有一个巨大的二叉树（每个节点都有一个通过和失败节点），我想遍历这棵树以便使用 DFS 获取所有可能的路径。由于树很大，使用单线程进行 DFS 所花费的时间非常长。所以为了解决这个问题，我现在正在考虑做并行DFS。基本思路如下。

  • 从单个线程开始并执行正常的 DFS，因为这会命中一个节点，生成一个以失败节点作为起始节点的新线程，并将该节点传递给该调用到目前为止
  • 初始线程在 pass 的路径中继续
  • 最后，每个线程都会返回一个它经过的节点列表；因此，我会用多个线程遍历整个树。由于所谓的父线程将其经过的节点的信息传递给子线程，因此每个线程都被称为自给自足

为了实现这一点，我正在考虑这样做

  • 使用 newCachedThreadPool。
  • 在 Main 中，我将创建 Pool，并启动对 Callable DFS 类的初始调用。DFS 类的构造函数也将采用 ExecutorService，以便新生成的 Thread 也可以使用上述规则生成新的 Thread

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) {
      }
   }

问题

  • 这有意义吗？这甚至可能吗？
  • 实现有问题，因为我可以一次又一次地看到同​​一个线程
4

2 回答 2

1

是的，可以编写并行 DFS。也可以使用线程池，但我认为fork/join风格的算法会更“自然”。fork 操作将并行遍历节点的所有子节点，而 join 操作将简单地连接返回的路径列表。

于 2012-04-21T10:49:03.243 回答
-1

好吧，我认为最大的问题是多线程对您没有帮助，因为您永远不会并行执行任何事情。您生成一个线程，然后立即等待，因此只有一个线程可以同时计算任何东西。

要问的另一个问题是为什么（以及是否）您想要所有路径的列表。在树中，来自根的路径由它们的端点唯一标识（并且可以通过遵循“向上”链接从那里重建）。N此外，所有路径的列表具有更大的内存复杂度（在具有节点的完全平衡二叉树中，树的内存复杂度为O(N)，而所有路径列表的内存复杂度为O(N*log(N))，这将是其时间复杂度创造，也是）。即使树中没有提供“向上”链接，您也可以IdentitiyHashMap<Node, Node>在O(N)时间，这将花费您更少的时间（和内存！）而不是构建所有路径的列表。我真的不认为您应该通过将大树转换为浪费的表示来开始处理大树。

于 2012-04-21T11:00:50.183 回答