深度优先的并行搜索

本文介绍了深度优先的并行搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个巨大的二进制树（每个节点有一个合格和不合格节点），我想遍历该树，以获得使用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.