树结构中的递归回溯-Java 学习之路

我有这个算法，我想使用递归回溯实现图搜索 .

首先我的代码：

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
             }

         }

那是我到目前为止的代码 . 它在everystep中构建树 . 树中的每个节点都是一个可能的解决方案，按启发式成本函数排序 . 前两个if子句是终止和返回的条件 . 如果有解决方案，它会很顺利地找到它 . 但如果没有快速解决方案，我需要撤消最后一步并尝试其他一些组合 . 在最坏的情况下，应该测试每种组合 .

childlist 保存每个子节点，按其成本函数排序 . 成本函数最小的那个将被选择用于扩展 . 构建树是递归完成的，但我有回溯的问题 . 我没有得到搜索返回一步并尝试第二个最好的节点，依此类推 . 使用新计算的 openList ，每个步骤都会扩展图表 . 我保存了对父节点的引用，如果这可能是一个帮助 .

openlist 是一个列表，它包含每个可能的下一步 - >节点 .

也许这张照片将有助于更好地解释我的问题：
enter image description here
这或多或少是我想要实现的搜索 . 但是，到目前为止，无论是否找到解决方案，我都会在休假结束时停留 . 我尝试了许多不同的东西，但这种回溯似乎不起作用，因为我的问题或至少我不能让它继续下去 .

1 回答

如果我理解正确，这需要pre-order tree vist .

我省略了一些细节，但我认为这段代码会对你有帮助（我没有测试过）：

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;
}

我主要删除了第一个，并删除了最后一个 .

回复于 2024-04-20T19:04:36+08:00

树结构中的递归回溯

1 回答

相关问题