깊이 우선 병렬 검색

Question

거대한 이진 트리 (각 노드에 통과 및 실패 노드가 있음)가 있으며이 트리를 통과하여 DFS를 사용하여 가능한 모든 경로를 얻으려고합니다. 트리가 크기 때문에 DFS가 단일 스레드를 사용하는 데 걸리는 시간은 매우 오래 걸립니다. 그래서이 문제를 해결하기 위해 병렬 DFS를 고려하고 있습니다. 기본 아이디어는 다음과 같습니다. 이 노드 안타

• 단일 스레드로 시작하고 정상적인 DFS를 할 수는 시작 노드로 실패 노드로 시작하는 새로운 스레드를 생성하고 전달할 호출 노드는 지금까지
• 여행 초기 스레드는 패스 패스에서 계속됩니다.
• 결국 모든 스레드는 이동 한 노드 목록을 반환합니다. 나는 여러개의 Thread를 가지고 전체 Tree를 가로 질렀을 것입니다. 소위 부모 스레드가 자식 스레드로 여행 한 노드의 정보를 전달하기 때문에, 각 스레드는 그래서이를 구현하기 위해 자급 자족

라고,이

을하고 생각하고
• newCachedThreadPool을 사용하십시오.
• 메인에서는 풀을 만들고 호출 가능 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) { 
        } 
       } 
      } 
  

  }

  DFS의

코드 구현 전술 한 바와 같이, 새로 만들어지는 스레드는 규칙을 사용하여 새 스레드를 생성 할 수 있도록 DFS 클래스의 생성자는 또한 ExecutorService에 걸릴 것입니다

메인 클래스

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

,개

질문

• 이 메이크업 감각을합니까? 이것은 가능한가? 내가 다시 같은 스레드를 볼 수 있습니다 다시

Answer 1

예, 병렬 DFS를 작성할 수 있습니다로

는 구현에 문제가 있습니다. 스레드 풀을 사용하는 것도 가능하지만, fork/join- 스타일 알고리즘은 더 자연 스럽다고 생각합니다. 포크 작업은 노드의 모든 자식을 병렬로 통과하는 반면 조인 작업은 반환 된 경로 목록을 간단히 연결합니다.

Answer 2

글쎄,이게 가장 큰 문제는 멀티 스레드가 도움이되지 않는다는 것입니다. 아무 것도 병렬로 실행하지 않기 때문입니다. 하나의 스레드를 생성 한 다음 즉시 대기하므로 한 순간에 하나의 스레드 만 계산할 수 있습니다.

또 다른 질문은 모든 경로의 목록을 원하는 이유입니다. 트리에서 루트의 경로는 끝점에 의해 고유하게 식별됩니다 ("위쪽"링크를 따라 가면서 재구성 될 수 있음). 더욱이, 모든 경로의리스트는 더 큰 메모리 복잡성을 갖는다 (N 노드를 갖는 완전한 평형 이진 트리에서, 트리의 메모리 복잡도는 O(N) 임), 모든 경로의리스트의 메모리 복잡도는 O(N*log(N)) 일 수있다. 창조의 복잡성도).트리에서 "위로"링크가 제공되지 않은 경우에도 O(N) 시간에 (아마도 IdentitiyHashMap<Node, Node>으로) 다시 구성 할 수 있습니다. 그러면 모든 경로 목록을 구성하는 것보다 시간과 메모리가 절약됩니다. 정말 큰 나무를 낭비 적 표현으로 변환하여 처리해야한다고 생각하지 않습니다.