1

DFS、BFS、A*、ダイクストラ、貪欲なアルゴリズムをサポートするはずの迷路を解くプログラムを書きました。とにかく、優先度はキュー、スタック、または優先度キューのように動作する可能性があると考えたので、フロンティア データ構造に PriorityQueue を選択しました。これは、コンパレータの実装に依存します。

これは、プライオリティ キューをキューに変換するコンパレータを実装する方法です。

/プライオリティ キューの「自然な順序付け」では先頭に最小の要素があり、従来のコンパレータは最初の要素が 2 番目の要素よりも小さい場合に -1 を返すため、ハッキングされたコンパレータは常に 1 を返すため、現在の (最後の) 2 乗は次のようになります。末尾に配置 (これは再帰的に機能するはずです) /

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 に答える