트리 구조의 재귀 역 추적

Question

이 알고리즘이 있으며 재귀 적 역 추적을 사용하여 그래프 검색을 구현하려고합니다. 내 모든 코드의

첫째 : 코드 그게 전부

public static boolean buildTree(GenericTreeNode<String> inputNode){ 

    while(!interruptFlag) 
    { 
     try { Thread.sleep(200); } catch(InterruptedException e) {} 

     gui.frame.MainWindow.progress.setText("Iterations Deployment: " + c); 
     gui.panel.ResultMatrix.setResult(mappingList); 
     Multimap<String,String> openList = LinkedHashMultimap.create(); 

     openList = UtilityClasses.getOpenList.getOpenList(dataMap, ApplicationList, HardwareList, mappingList); 

    if(openList.isEmpty() && !mappingList.keySet().containsAll(XMLParser.ApplicationsListGUI)) 
      { 
       gui.frame.MainWindow.labelSuccess.setText("Mapping not succesful!"); 
       return false; 

      } 
    if(openList.isEmpty() && mappingList.keySet().containsAll(XMLParser.ApplicationsListGUI)) 
      { 
       System.out.println(calculateOverallCost.getOverallCosts()); 
       System.out.println("Mapping done:" + " " + mappingList); 
       gui.panel.ResultMatrix.setResult(mappingList); 

       return true; 
      } 

    if(!openList.isEmpty() && (!mappingList.keySet().containsAll(XMLParser.ApplicationsListGUI))) 
     { 

      for(String s : openList.keySet()) 
      { 
       for(String h : openList.get(s)) 
       { 
       GenericTreeNode<String> child = new GenericTreeNode<String>(s + ":" + h); 
       inputNode.addChild(child); 
       child.setCosts(UtilityClasses.CostFunction.calculateCostFunction(s, h)); 
       } 
      } 
      List<GenericTreeNode<String>> childlist = inputNode.getChildren(); 
      Collections.sort(childlist); 

      for(int i = 0; i < childlist.size() ; i++) 
     {    
      inputNode = childlist.get(i); 
        // do something  
      if (buildTree(inputNode)) 
       { 
       return true; 
       } 
      else 
      { 
      // undo something 
      } 

     } 

는 지금까지 있습니다. 그것은 영원히 나무를 만듭니다. 나무의 모든 노드가 가능한 해결책이며, 경험적 비용 함수에 의해 정렬됩니다. 첫 번째 2 if-clause은 종료 및 반환 조건입니다. 해결책이 있다면 꽤 원활하게 찾을 수 있습니다. 그러나 빠른 해결책이 없으면 마지막 단계를 실행 취소하고 다른 조합을 시도해야합니다. 최악의 경우 모든 조합을 테스트해야합니다.

childlist은 모든 하위 노드를 비용 기능으로 정렬하여 유지합니다. 가장 적은 비용 기능을 가진 제품이 확장을 위해 선택됩니다. 트리를 만드는 것은 재귀 적으로 이루어 지지만 백 트랙킹에 문제가 있습니다. 나는 한 걸음 뒤로 가서 두 번째로 좋은 노드를 시도하는 등의 검색을받지 못한다. 그래프는 매 단계마다 확장되어 새로 계산 된 openList으로 계산됩니다. 부모 노드에 대한 참조를 저장했습니다 (도움이 될 수있는 경우).

openlist은 가능한 모든 다음 단계 -> 노드를 포함하는 목록입니다.

어쩌면이 그림이 내 문제를 더 잘 설명하는 데 도움이됩니다. 어쩌면 내가 알고 싶었던 검색이 그 이상입니다. 그러나 해결책이 있는지 없는지 상관없이 지금까지 가지고있는 코드는 휴가가 끝날 때까지 붙어 있습니다. 나는 많은 다른 일을 시도했지만,이 되돌아 오는 추적은 작동하지 않는 것 같습니다. 제 종류의 문제 또는 적어도 그럴 수는 없습니다.

Answer 1

정확하게 이해했다면, 이 필요합니다.

나는 몇 가지 세부 사항을 ommited, 그러나 나는 (내가 그것을 테스트하지 않은)이 코드는 당신을 도울 것입니다 생각 :

public static boolean buildTree(GenericTreeNode<String> inputNode) { 
    if (interruptFlag) { 
     // search was interrupted 
     // answer has not be found yet 
     return false; 
    } 

    boolean something = openList.isEmpty() && !mappingList.keySet().containsAll(XMLParser.ApplicationsListGUI); 
    if (something) { 
     // ... Mapping not succesful! 
     // answer can't be found 
     return false; 

    } 

    boolean answerFound = openList.isEmpty() && (mappingList.keySet().containsAll(XMLParser.ApplicationsListGUI)); 
    if (answerFound) { 
     // ... 
     return true; 
    } 

    // answer has not been found 
    // visit each children 
    // order children list by cost 
    // ... 
    List<GenericTreeNode<String>> childlist = // ... 
    Collections.sort(childlist); 

    for (int i = 0; i < childlist.size(); i++) { 
     inputNode = childlist.get(i); 
     // do something 
     boolean childHasAnswer = buildTree(inputNode); 
     if (childHasAnswer) { 
      // answer was found 
      return true; 
     } // else: our children do not have the answer 
    } 

    // neither we or our children have the answer, let's go to the parent 
    return false; 
} 

내가 주로 첫번째 동안을 삭제하고, 마지막으로 다른 삭제.