Java - 在比较器中进行排序以在优先级队列中使用

Question

我对如何根据比较器中的实现确定优先级队列的排序方式有点困惑。在这里，我想根据 FScore 降序排序，这意味着最低的 FScore 将位于队列的顶部。我不确定我是否正确执行了此操作(我将其用于 A * 算法)。

private class puzzleStateComparator implements Comparator<PuzzleState> {

    @Override
    public int compare(PuzzleState o1, PuzzleState o2) {
        //TODO

        int[] goalState = FastPuzzleSolver.this.initialState.getStateArray();

        int o1GScore = PuzzlePropertyUtility.numBlocksOutOfPlace(o1.getStateArray(), goalState);
        int o2GScore = PuzzlePropertyUtility.numBlocksOutOfPlace(o2.getStateArray(), goalState);

        int o1HScore = PuzzlePropertyUtility.calcManhattanDistanceSum(o1.getStateArray(), goalState);
        int o2HScore = PuzzlePropertyUtility.calcManhattanDistanceSum(o2.getStateArray(), goalState);

        int o1FScore = o1GScore + o1HScore;
        int o2FScore = o2GScore + o2HScore;

        return o1FScore - o2FScore;


    }

Answer 1

一件重要的事情，比较两个整数的正确方法是这样的:

//ascending order
return Integer.compare( o1Fscore, o2Fscore );

//descending order
return Integer.compare( o2Fscore, o1Fscore );

将整数与减法进行比较可能会导致上溢/下溢问题。

如果您使用 java.util.PriorityQueue，那么您肯定需要降序版本，如 API 文档所述:

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements -- ties are broken arbitrarily. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.

顺便说一句:如果 PuzzleState 是不可变的(可能应该如此)，那么每个状态只计算一次 G 和 H 分数是值得的。