14

如果这是一个尝试过的问题，请原谅我，但我很难弄清楚。

我目前有一个类节点，每个“节点”都是迷宫中的一个正方形。我正在尝试实现 A* 算法，因此每个节点内部都有一个 f-cost (int) 数据成员。我想知道是否有一种方法可以创建这些节点的优先级队列，并将 f-cost 变量设置为比较器？

我看过网上的例子，但我能找到的只是字符串优先级队列。我可以为 Node 类实现 Comparator 吗？这是否允许我访问存储在其中的数据成员？

非常感谢！

4

5 回答 5

27

绝对地。

您可以使用PriorityQueue基于匿名Comparator传递给构造函数：

int initCapacity = 10;
PriorityQueue<Node> pq = new PriorityQueue<Node>(initCapacity, new Comparator<Node>() {
    public int compare(Node n1, Node n2) {
        // compare n1 and n2
    }
});
// use pq as you would use any PriorityQueue

如果您的Node类已经实现Comparable，您甚至不需要定义 new Comparator，因为默认情况下将使用该顺序。除非使用任何其他方法，否则将使用对象之间的自然排序。

于 2010-03-31T18:09:23.277 回答
4

这个问题在不久前得到了回答，我想提供一些可用的新选项。

1）如果您的Node类没有实现 Comparator 接口并且您不想（或不能）添加它，请使用 lambda：

  new PriorityQueue<>((node1, node2) -> Integer.compare(node1.getCost(), node2.getCost()));

2）简单的逆序方法（需要Node实现Comparator接口）：

  new PriorityQueue<>(Comparator.reverseOrder());

3）使用效用函数：

  new PriorityQueue<>(NodeUtil::customCompare);

  public static int customCompare(Node n1, Node n2) {
       return Integer.compare(n1.getCost(), n2.getCost());
  }
于 2019-10-18T19:33:50.217 回答
1

来自 Javadocs：

基于优先级堆的无界优先级队列。此队列根据构造时指定的顺序对元素进行排序，该顺序根据其自然顺序（参见 Comparable）或根据 Comparator 指定

此外，PriorityQueues 支持通用数据类型。因此，如果您Comparable在 Node 类中实现，那么您可以创建PriorityQueue<Node>并正常使用它。

或者，有一个构造函数PriorityQueue(int initialCapacity, Comparator<? super E> comparator)将 Comparator 作为PriorityQueue构造函数的一部分。如果您更喜欢这种方法，您的节点类不需要包含继承时所需的额外代码Comparable。

于 2010-03-31T18:07:28.213 回答
1 
public class Node implements Comparable<Node>{

    public int compareTo(Node o) {
         // your comparative function
         return 0;
    }

}

如果 compareTo 返回负整数，表示“小于”，0 表示“等于”，1 表示“大于”

只需一个功能即可使用 PriorityQueue。

编辑：比较是另一种方式，我搞砸了。-1 < | 0 = | 1 > 由于某种原因，我已经从右到左阅读这些内容。

于 2010-03-31T18:12:53.393 回答
0

java.util 中有一个 PriorityQueue 类。您可以使用它，它将使用自然排序（Node 实现 Comparable）或构造函数中提供的比较器（如果您不希望在 Node 类中使用该代码）。任何类都可以访问另一个类中的任何数据，只要您通过使字段为非私有（可能是糟糕的 OOP 样式）或提供访问器方法 public int getG()、public int getH()、public int getF() 来允许它.

于 2010-03-31T18:09:03.637 回答