嘗試使用ArrayDeque迭代器來制定統一的成本搜索方法

Question

如前所述，我正在使用ArrayDeque邊緣的迭代器來查找具有最低路徑代價節點的圖塊。下面的代碼：

public static void UCS(String filename) 
{ 
    //a double-ended queue, when used with "addFirst" and "remove", it's a LIFO queue 
    ArrayDeque<Node> fringe = new ArrayDeque<Node>(); 
    //initial tile set 
    ArrayList<Tile> tileSet = getTilesFromFile(filename); 
    //start state has no placed tiles, and all tiles are in the unplaced list 
    State startState = new State(new ArrayList<Tile>(),tileSet); 
    //the node that goes with the start state, it has 0 path and step cost, and a null parent 
    Node root = new Node(startState,0.0,0.0,null); 
    //the fringe starts with just the root node 
    fringe.addFirst(root); 

    //These are for keeping track of the best solution since 
    //we don't just need /a/ solution, we need the best one 
    //after generating the whole tree 
    double bestCost = Double.MAX_VALUE; 
    State bestSolution = null; 

    Iterator itr = fringe.iterator(); 

    //we go until there are no nodes left to be expanded 
    while(!fringe.isEmpty()) 
    { 
     double lowestCost = Double.MAX_VALUE; 
     Node lowestCostNode = root; 

     for (int i = 0; i < fringe.size(); i++) 
     { 
      if (((Node) itr.next()).getPathCost() < lowestCost) 
      { 
       lowestCost = ((Node) itr.next()).getPathCost(); 
       lowestCostNode = ((Node) itr.next()); 
      } 
     } 
     //grab the node at the front of the FIFO queue 
     Node currNode = lowestCostNode; 
     fringe.remove(currNode); 
     //if it is a goal state and the path cost is better than the best 
     //goal state we've seen so far, it's the new best 
     if(currNode.getState().isGoal() && currNode.getPathCost() < bestCost) 
     { 
      bestCost = currNode.getPathCost(); 
      bestSolution = currNode.getState(); 
     } 

     //generate all child nodes and put them in the fringe 
     //at the back of the FIFO queue 
     ArrayList<Node> childNodes = currNode.expand(); 
     for(Node c : childNodes) 
     { 
      fringe.addFirst(c); 
     } 
    } 

    //print the solution along with the cost 
    //you should also print the number of nodes generated and the amount of time it took 
    //to perform the search 
    System.out.println(bestSolution); 
    System.out.println("Cost of best solution: "+bestCost); 
} 

一些邏輯很可能還是走了，我知道，但我會明白這一點，當我解決此問題得到。同樣忽略奇怪的評論和類似的東西，其中很多都是從BFS方法複製粘貼的。我得到的問題是與線：

lowestCost = ((Node) itr.next()).getPathCost(); 

Answer 1

我想這：

for (int i = 0; i < fringe.size(); i++) 
{ 
    if (((Node) itr.next()).getPathCost() < lowestCost) 
    { 
     lowestCost = ((Node) itr.next()).getPathCost(); 
     lowestCostNode = ((Node) itr.next()); 
    } 
} 

應該是：

while (itr.hasNext()) 
{ 
    Node next = (Node) itr.next(); 
    if (next.getPathCost() < lowestCost) 
    { 
     lowestCost = next.getPathCost(); 
     lowestCostNode = next; 
    } 
}