Recursive Backtracking in tree structure

Question

I have this algorithm and I want to implement a graph search, using recursive backtracking.

First of all my code:

 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
             }

         }

Thats the code I have so far. It builds the tree in everystep. Every node in the tree is a possible solution, ordered by a heuristic costfunction. The first 2 if-clauses are the conditions to terminate and return. If there is a solution, it finds it pretty smoothly. But if there is no quick solution, I need to undo the last step and try some other combinations. In the worst case, every combination should be tested.

The childlist holds every child nodes, ordered by their costfunction. The one with the least costfunction, will be chosen for expansion. Building the tree is done recursively, but I have problems with the backtracking. I dont get the search to go back a step and try the second best node and so on. The graph is expanded every step with the new calculated openList. I saved a reference to the parent node, if that could be a help.

The openlist is a list, which holds every possible next step -> nodes.

Maybe this picture will help explaining my problem better: thats more or less the search I wanted to realize. But the code i have till now, stucks at the end of a leave, no matter if a solution is found or not. I tried many different things, but this backtracking dont seem to work, for my kind of problem or at least I cant get it going.

Answer 1

If I understood correctly, this needs a pre-order tree vist.

I ommited some details, but I think this code will help you (I haven't test it):

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

I mainly deleted the first while, and deleted the last else.