树结构中的recursion回溯

我有这个algorithm，我想实现一个图search，使用recursion回溯。

首先我的代码：

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

这是迄今为止的代码。 它永远构build了树。 树中的每个节点都是可能的解决scheme，按启发式成本函数sorting。 前两个if-条款是终止和返回的条件。 如果有解决scheme，它发现很顺利。 但是，如果没有快速解决scheme，我需要撤消最后一步，尝试其他组合。 在最坏的情况下，每一个组合都应该被testing。

孩子childlist保存每个孩子节点，按其成本函数sorting。 成本函数最小的那个，将被选中进行扩展。 构build树是recursion地完成的，但是我有回溯的问题。 我没有得到search回去一步，尝试第二个最好的节点，等等。 该graphics每一步都用新计算的openList 。 我保存了对父节点的引用，如果这可能是一个帮助。

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

也许这张照片能更好地解释我的问题： 这或多或less是我想要实现的search。 但是直到现在的代码，在休假结束的时候，无论是否find解决scheme。 我尝试了很多不同的东西，但是这种回溯似乎不起作用，因为我的这种问题，或者至less我不能得到它。

Answer 1

如果我理解正确的话，这需要一个预订树形图 。

我忽略了一些细节，但我认为这个代码会帮助你（我没有testing它）：

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

我主要删除了第一个，而删除了最后一个。