Java:由优先队列构成的队列的奇怪顺序 [英] Java: strange order of queue made from priority queue

问题描述

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

I wrote a maze solving program which is supposed to support DFS, BFS, A*, Dijkstra's, and greedy algorithm. Anyway, I chose PriorityQueue for my frontier data structure since I thought a priority can behave like a queue, stack, or priority queue depends on the implementation of the comparator.

这是我如何实现我的比较器将优先级队列转换为队列:

This is how I implemented my comparator to turn the priority queue into a queue:

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

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

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

However, my solution for the maze was not optimal after I did a BFS.

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

The maze starts at top right corner with coordinate (35,1) and my program checks the left, then up, then down, then right neighbour. Here are the println I did:

轮询 (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)，它被放置在队列的头部.

Notice in a BFS (35,3) should be polled out before (32,1) since the former is added into the queue before the latter. What really confused me is that the data structure behaved like a queue--all new members were added from the back--until I added (32,1), which was placed at the head of the queue.

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

I thought my comparator should force the priority queue to put new comers in the back. What is even stranger to me is that the data structure changed its nature from a queue to a stack in the middle.

非常感谢前面的你们，对我糟糕的英语感到抱歉，真挚地，肖恩

Many thanks to you guys ahead and sorry about my poor English, Sincerely, Sean

推荐答案

您实施 compare 的方式是错误的，只有在您以非常特定的方式调用它时才有效重新假设.但是，您不知道 PriorityQueue 在什么上下文中实际调用 compare.compare 函数很可能在数据结构内的现有元素上调用，而不是在新元素上调用，反之亦然.

The way you've implemented compare is wrong, and would only work if it's called only in a very specific way that you're assuming. However, you have no idea in what context the PriorityQueue actually calls compare. The compare function might well be called on an existing element inside the data structure, instead of the new one, or vice versa.

(即使您确实阅读了源代码并对其进行了跟踪并发现此特定实现以某种方式工作，如果您希望代码可维护，您也不应该依赖它.至少，您会通过解释它的工作原理来让自己更有效率.)

(Even if you did read the source code and traced it and found that this particular implementation works in a certain way, you shouldn't depend on that if you want your code to be maintainable. At the least, you'd be making yourself more work by having to explain why it works.)

您可以使用某种计数器并将其分配为每个添加项目的值，然后根据该值正确实施compare.

You could just use some sort of counter and assign it as the value for each added item, then implement compare correctly based on the value.

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

A correct implementation of compare might look like this:

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

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

Note that if you switch the order of the parameters, the answer will change as well. No, the int returned does not necessarily have to come from {-1, 0, 1}. The spec calls for 0, or a negative or positive integer. You can use any one you wish, so long as it's the correct sign.

这篇关于Java:由优先队列构成的队列的奇怪顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！