執行算法的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); 
    } 
}