实现算法中的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);
}

这只会跟随最小成本节点的分支。