1

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

这就是我实现比较器以将优先级队列转换为队列的方式：

/由于优先级队列的“自然排序”在头部具有最少元素，并且传统比较器在第一个小于第二个时返回 -1，因此被破解的比较器总是返回 1，因此当前（最后一个）方格将是放在尾部（这应该递归地工作） /

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

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

非常感谢你们，并为我糟糕的英语感到抱歉，真诚的，肖恩

4

1 回答 1

4

您实现的方式compare是错误的，并且仅当仅以您假设的非常特定的方式调用它时才会起作用。但是，您不知道PriorityQueue实际调用compare. 该compare函数很可能在数据结构内的现有元素上调用，而不是在新元素上调用，反之亦然。

（即使您确实阅读了源代码并跟踪它并发现此特定实现以某种方式工作，如果您希望您的代码可维护，您也不应该依赖它。至少，您会让自己通过解释它为什么起作用来做更多的工作。）

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

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

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

请注意，如果您切换参数的顺序，答案也会发生变化。不，返回的 int不一定来自 {-1, 0, 1}。规范要求 0，或者一个负整数或正整数。你可以使用任何你想要的，只要它是正确的标志。

于 2012-10-04T04:36:38.560 回答