Java:由优先队列组成的奇怪队列顺序

Question

我写了一个解迷宫的程序，应该支持 DFS、BFS、A*、Dijkstra 和贪心算法。无论如何，我选择 PriorityQueue 作为我的前沿数据结构，因为我认为优先级可以像队列、堆栈或优先级队列一样运行，具体取决于比较器的实现。

这就是我实现比较器以将优先级队列变成队列的方式:

/由于优先级队列的“自然排序”在头部的元素最少，而传统的比较器在第一个小于第二个时返回 -1，被黑的比较器总是返回 1，以便当前(last) square 将放在尾部(这应该递归工作)/

public int compare(Square square1, Square square2)
{
    return 1;
}

但是，在我进行了 BFS 之后，我的迷宫解决方案并不是最优的。

迷宫从坐标 (35,1) 的右上角开始，我的程序检查左边，然后向上，然后向下，然后是右边的邻居。这是我做的 println:

投票结果 (35,1)

添加 (34,1)

添加 (35,2)

投票结果 (34,1)

添加 (33,1)

添加 (34,2)

投票结果 (35,2)

添加 (35,3)

投票结果 (33,1)

添加 (32,1)

添加 (33,2)

投票结果 (34,2)

添加 (34,3)

轮询 (32,1)

……

BFS (35,3) 中的通知应该在 (32,1) 之前被轮询，因为前者在后者之前被添加到队列中。真正让我感到困惑的是，数据结构的行为就像一个队列——所有新成员都是从后面添加的——直到我添加 (32,1)，它被放在队列的头部。

我认为我的比较器应该强制优先队列将新来者放在后面。更让我感到奇怪的是，数据结构在中间从队列变成了栈。

非常感谢前面的你们，抱歉我的英语不好，真挚地，肖恩

Answer 1

您实现 compare 的方式是错误的，并且只有在以您假设的非常具体的方式调用它时才会起作用。但是，您不知道 PriorityQueue 实际上在什么上下文中调用了 compare。 compare 函数可能会在数据结构中的现有元素而不是新元素上调用，反之亦然。

(即使您确实阅读了源代码并对其进行了跟踪并发现这个特定的实现以某种方式工作，如果您希望您的代码可维护，您也不应该依赖它。至少，您会必须解释它为什么有效，从而让自己做更多的工作。)

您可以只使用某种计数器并将其分配为每个添加项的值，然后根据该值正确实现比较。

compare 的正确实现可能如下所示:

int compare(Object x, Object y){
    return x.getSomeProperty() - y.getSomeProperty();
}

请注意，如果您调换参数的顺序，答案也会随之改变。不，返回的 int 不一定必须来自 {-1, 0, 1}。规范要求 0，或者负整数或正整数。您可以使用任何您想要的符号，只要它是正确的符号即可。