0 
fringe = new PriorityQueue<Node>(10,new Comparator<Node>(){
            @Override
            public int compare(Node node1,Node node2)
            {
                if (f(node1)>f(node2))
                    return 1;
                else
                    return -1;
            }
        });

いくつかのノードを格納するためにPQを宣言し、f値に従って降順ではない順序でノードを格納したい。functionf（Node node）は、ノードのf値を計算することです。コンパレータをオーバーライドしますが、現在、f値が大きいノードがキュー内のf値が小さいノードの前に配置されていることがわかりました。全体をチェックしましたが、何が問題なのかを見つけることができません。おそらく、PQ宣言の問題。誰でも私を助けることができますか？前もって感謝します！

4

3 に答える 3

6

ここを参照してください。私は引用します：

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

保証されているのは、最上位要素が Comparator による最小要素であることだけです。

于 2012-04-11T06:55:00.167 に答える
1

@izomorphius が述べたように、PriorityQueue は完全な順序付けを保証するものではなく、ヘッドが常に最小限であることのみを保証します。

完全な注文が必要な場合は、次の可能性のいずれかを選択することをお勧めします。

  1. -を使用しますTreeSetが、重複が許可されないことに注意してください。equals()また、@ JoonasPulakka が述べているように、ここではおそらくオーバーライドしたいと思うでしょうhashCode()。
  2. 使用List- [順不同] に入力してCollections.sort(List,Comparator)から、コンパレーターに従って並べ替えるために使用します
  3. 配列 [ Node[]] を使用し、[順不同] に入力してArrays.sort()から、コンパレータに従って並べ替えます。

編集:編集
された Comparator は完全な順序付けを強制しないため、それを使用した結果は未定義です:
let a、bbe two Nodes そのようなものf(a) == f(b)

compare(a,b) == compare(b,a) == -1

しかし、javadocには次のように記載されています。

実装者は、すべての x と y に対して sgn(compare(x, y)) == -sgn(compare(y, x)) であることを確認する必要があります。

したがって、この [編集された] コンパレータを使用した結果は未定義です。

EDIT2：
あなたのコメントは、「時間を追加する」という2番目の基準を探していることを示唆しています。オブジェクトに別のフィールドlong timestampを追加して、このフィールドに基づく結果を返すことができるのは、. これにより、一貫性が保証され、必要な機能が実現されます。NodeComparatorf(node1) == f(node2)

注: このフィールドは、最初に要素をキューに追加するとき [またはオプションの場合はオブジェクトが作成されるとき] に一度だけ初期化されます。

于 2012-04-11T07:00:59.313 に答える
0

あなたもオーバーライドしましたequals()か？Comparator docsで指摘されているように、

並べ替えられたセット (または並べ替えられたマップ) を並べ替えるために equals と矛盾する順序付けを課すことができる比較演算子を使用する場合は、注意が必要です。明示的なコンパレータ c を持つソート済みセット (またはソート済みマップ) が、セット S から引き出された要素 (またはキー) で使用されているとします。c によって S に課された順序付けが equals と矛盾する場合、ソート済みセット (またはソート済みマップ) は次のようになります。 「奇妙」に振る舞う。特に、ソートされたセット (またはソートされたマップ) は、セット (またはマップ) の一般的な契約に違反します。これは、等しいという観点から定義されています。

また、 Object docsで指摘されてequals()いるように、オーバーライドする場合はオーバーライドする必要があることにも注意してください。hashCode()

コメントで指摘されているように、（ソートされた）セットではありませPriorityQueueんが、データ構造を特定の順序で反復できるものに切り替えたい場合（キューはできない、ソートされたセットはできます）compare()、、、、equals()およびhashCode()推奨どおりに実装されました。

于 2012-04-11T06:53:55.003 に答える