执行算法的Java递归

Question

我想实现一个使用递归方法的搜索算法。

该算法应扩大startnode到其相邻节点，然后选择具有最小成本的相邻节点，然后将该成本添加到pathcost（其最初是0），并且至少所选择的成本的节点将变为startnode和继续搜索再次递归直到找到goalnode。

下面是我实现这种递归的代码。这不是给我任何错误，但它并没有给我预期的解决方案。 INSTEAD它增加了每个相邻节点的成本（我只需要它添加最小成本节点）。我一直在努力去做，但似乎无法找到任何线索如何去做。

Queue<String> frontierNodes = new PriorityQueue<String>(); 
Queue<Node1> frontierCosts = new PriorityQueue<Node1>(); // here Node1 is class storing the start, end and cost of the map. 

public void Search(Node1[] nodes, String startnode, String goalnode, int size, double pathcost){ 

    for(int i=0; i<size;i++) {    
     if(startnode.equalsIgnoreCase(nodes[i].getStartNode())) {    
      frontierNodes.add(nodes[i].getEndNode()); 
      frontierCosts.add(new Node1(nodes[i].getCost())); 

      System.out.println("Frontier Nodes are " +frontierNodes); 
      System.out.println("Path cost till now "+pathcost); 
      // Something should be implemented here to add only the least cost 
      pathcost += frontierCosts.peek().toCostString(); 
      System.out.println("Path cost till now "+pathcost); 

     }  
    } 
    System.out.println("Expanding node... " +frontierNodes.peek()); 
    //Recursive call 
    Search(nodes, frontierNodes.poll(), goalnode, nodes.length-(frontierNodes.size()), pathcost); 

} 

Answer 1

我不确定为什么要使用PriorityQueue。您应该将所有内容都放在递归方法的范围内。对于树的遍历递归，你要遵循的一般模式（伪代码）

int sumOfLeastCost(Node node){ 
    if(node == null){ return 0; } 
    int sum = 0; 
    Node min = null; 
    for each child{ 
     if(min == null){ 
      min = currentChild; 
     }else if(currentChild.getCost() < min.getCost()){ 
      min = currentChild; 
      sum = min.getCost(); 
     } 
    } 

    return sum + sumOfLeastCost(min); 
} 

这只会遵循最低成本节点的分支。

Answer 2

这更贴近您的需求吗？

public double Search(ArrayList<Node1> nodes, String startnode, String goalnode, double pathcost){ 

    //Probably needs a better data structure to hold these 
    ArrayList<String> neighbours = new ArrayList<>(); 
    ArrayList<Double> neighbourPathCosts = new ArrayList<>(); 

    int i; 
    for(i=0; i<nodes.size();i++) {    
     if(startnode.equalsIgnoreCase(nodes.get(i).getStartNode())) {    
      neighbours.add(nodes.get(i).getEndNode()); 
      neighbourPathCosts.add(nodes.get(i).getCost()); 
     } 
    } 

    int indexOfCheapest = -1; 
    double cheapest = Double.MAX_VALUE; 
    for(int j = 0; j < neighbours.size(); j++){ 
     if(cheapest > neighbourPathCosts.get(i)){ 
      cheapest = neighbourPathCosts.get(i); 
      indexOfCheapest = i; 
     } 
    } 

    pathcost += neighbourPathCosts.get(indexOfCheapest); 
    System.out.println("Path cost till now " + pathcost); 

    String nextNode = neighbours.get(indexOfCheapest); 
    System.out.println("Expanding node... " + nextNode); 

    if(startNode.equals(goalNode)){ 
     return pathcost; 
    }else{ 
     nodes.remove(i); 
     //Recursive call 
     return Search(nodes, nextNode, goalnode, pathcost); 
    } 
}