0

述べたように、ArrayDeque のイテレーターである fringe を使用して、ノードのパス コストが最も低いタイルを見つけています。コードは次のとおりです。

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();
4

1 に答える 1

0

私はこう思います：

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;   
    }
}
于 2012-10-01T04:08:05.373 に答える