0

グラフにBFSを実装しています。ここで、ノードはStateクラスのオブジェクトによってマークされています（比較のために暗黙のequals toメソッドを実装しました）。

プログラムを拡張してDFS、Astarなどを処理したいので、1を返すコンパレータを備えたPriorityQueueを使用してキューを実装しました。これは、コンパレータ内のロジックを変更するだけで実行できます。

関連するコードは次のとおりです。

//BFSComparator.java

import java.util.Comparator;

public class BFSComparator implements Comparator<State>{
    @Override public int compare(State x, State y) {
       return 1;
    }
}

//solver.java

Comparator comparator = new BFSComparator();
PriorityQueue<State> frontierList = new PriorityQueue<State>(500,comparator); //List of nodes to be expanded
frontierList.add(seed state0);
while (!frontierList.isEmpty()){
        curState = frontierList.poll();
        //handle, expand and add child states to frontierList

リストを繰り返し処理し、存在する要素を印刷しているときに、一部の要素がランクを上げないことがわかりました（たとえば、pollの{a、b、c、d、e}はpoll（の{b、e、c、d}になります） ）{b、c、d、e}）ではなく、したがって、FIFOを実行しません。

for(State x:frontierList) {
             //print x
}

1）コンパレータに問題がありますか？

2）これを一般的に行うためのより良い方法はありますか？つまり、プッシュやポップなどの異なる呼び出し名を持つキューやスタックを使用するのではなく、並べ替えの背後にあるロジックを変更しながら追加できる優先キューよりも優れたコンテナですか？これは、後でヒューリスティックに基づいて並べ替えるときに役立ちます。または、リンクリストを使用して、挿入ソートベースのアプローチを実行する必要がありますか？

編集：もう少し明確にしたいと思います。DFSまたはBFS（FIFOまたはLIFO）、またはA-Starやビームサーチなどの他の優先度ベースのアルゴリズムに関係なく、共通のadd（State）またはState x = remove（）で物事をスローできるコレクションを実装しようとしています。 。

私はおそらくコレクションを拡張し、addや他のメソッドを実装するつもりです。

4

1 に答える 1

1 
public int compare(State x, State y)

このメソッドは、正の値は x > y を意味し、負の値は x < y を意味し、0 は x==y を意味します。

代わりに Queue を使用して frontierList を宣言する必要があると思います

DFS が必要な場合は、LinkedList<State> を使用します

BFS が必要な場合は、PriorityQueue<State> と Comparator<State> を使用して、必要な最小または最大の状態を返します

于 2013-02-23T08:51:21.147 に答える