Java 优先级队列中的节点比较

Question

我在优先添加节点时遇到错误我猜错误是在比较方法中，我已经用谷歌搜索了很多并找到了一个解决方案来扩展它具有可比性但仍然没有成功，得到以下

Exception in thread "main" java.lang.ClassCastException: Node cannot be cast to java.lang.Comparable
    at java.util.PriorityQueue.siftUpComparable(Unknown Source)
    at java.util.PriorityQueue.siftUp(Unknown Source)
    at java.util.PriorityQueue.offer(Unknown Source)
    at java.util.PriorityQueue.add(Unknown Source)

以下是我的节点class

class Node<T,Q extends Comparable<Q>>{

    T obj;
    private Node<T, Q> parent;

    public final Node<T, Q> getParent()
    {
        return parent;
    }
    public final void setParent(Node<T, Q> value)
    {
        parent = value;
    }


    private int cost;

    public final int getCost()
    {
        return cost;
    }
    public final void setCost(int value)
    {
        cost = value;
    }


    private T state;

    public final T getState()
    {
        return state;
    }
    public final void setState(T value)
    {
        state = value;
    }


    private Q aciton;

    public final Q getAciton()
    {
        return aciton;
    }
    public final void setAciton(Q value)
    {
        aciton = value;
    }


    public final int compareTo(Object obj)
    {
        Node<T, Q> node = (Node<T, Q>)obj;
        if (node.cost > this.cost)
        {
            return -1;
        }
        else if (node.cost < this.cost)
        {
            return 1;
        }
        else if (node.cost == this.cost)
        {
            return 0;
        }
        return 0;
    }
}

这是调用它的片段

explored.add(n2);
                     ArrayList<Integer> stlist = expandStates(n2.getState(), transitions);
                    int ac = 0;
                    for (int i : stlist)
                    {
                        Node<Integer, Integer> n3 = new Node<Integer, Integer>();
                        n3.setState(i);
                        n3.setCost(1 + n2.getCost());
                        n3.setParent(n2);
                        n3.setAciton(ac);
                        ac++;

                        if (isExplored(i, explored) == true)
                        {

                        }
                        else
                        {
                            frontier.add(n3);
                        }

Answer 1

Node 没有实现 Comparable。您需要：class Node<T,Q extends Comparable<Q>> implements Comparable<Node<T , Q>>{

Answer 2

您的 class Node 没有实现 Comparable 接口。所以 PriorityQueue 不知道两个节点之间，哪个有更高的优先级。您可以像这样更改 class 的签名：

class Node<T, Q extends Comparable<Q>> implements Comparable<Node<T, Q>> {
    ...
    public final int compareTo(Node<T, Q> node)
    {
        if (node.cost > this.cost)
        {
            return -1;
        }
        else if (node.cost < this.cost)
        {
            return 1;
        }
        else if (node.cost == this.cost)
        {
            return 0;
        }
        return 0;
    }
}

请注意，compareTo 的定义也已更改为将节点作为参数而不是通用对象。

Java 优先级队列中的节点比较

Comparison of Nodes in Java For Priority Qeue

java

nodes

priority-queue