私は15のゲームでアルゴリズムBFS、DFS、A *(2つのヒューリスティックスを持つ)のストローク数を比較するプログラムを構築しようとしています。2つの異なるアルゴリズムのカウンタの2つの同じ結果
私のカウンタは、BFSとDFSの両方のカウンタの2つのアレイと同じ結果をカウントします。しかし、実際には、メイン(クラスProject)から4つの異なる配列を使用しています。これらのストロークに対して4つの異なる変数を割り当てています。
私の考えでは、頂点の息子をできるだけ遠くに(BFSのために)探索したり、後続ノード(BFSのために)をそれぞれ発見するwhileループです。最も重要な違いは、frontier.push(子)、DFS、frontier.add(子)のいずれかのコードの最後の行です。 BFSの場合
我々は最終状態を見つけた場合、我々はループに入るたびに、ストローク数が
number_of_strokes_DFS+=1;
または
number_of_strokes_BFS+=1;
をインクリメントされ、私たちは、ストローク数の配列に結果を追加:
array_number_of_strokes_dfs.add(number_of_strokes_DFS);
または
array_number_of_strokes_bfs.add(number_of_strokes_BFS);
最終的に有罪判決のコードがあります(実際には、BFSが本当に最後の行を除いてlookalikeである限り、実際にはDFSのみです)。
while(!frontier.isEmpty()){
number_of_strokes_DFS+=1;
if(System.currentTimeMillis()-startTime>10000)break;
// We remove the current state from the frontier
current_state = frontier.pop();
// We get all possible actions from the current state
actions = current_state.getActions();
// We add the current state to already explored nodes
explored_nodes.add(current_state);
//System.out.println(current_state);
path.add(current_state);
// we found the goal
if(goal_test(current_state)){
/*for(State visited :path){
System.out.println(visited);
}*/
array_number_of_strokes_dfs.add(number_of_strokes_DFS);
System.out.println("nombres de coups DFS"+number_of_strokes_DFS);
number_of_strokes_DFS=0;
return current_state;
}
// We create every child
for (Action action : actions){
//System.out.println("action : " + action);
// we get a child from the execution of the current_state
State child = current_state.execute(action);
//System.out.println("we executed the action");
if(!explored_nodes.contains(child)&&!frontier.contains(child)){
// This child not being already explored nor int the frontier we add it to the last one
frontier.push(child);
}
}
}
array_number_of_strokes_dfs.add(-1);
return finalState;
}
は、ここに私の知る限り;,(number_of_strokes_DFS)array_number_of_strokes_dfs.add例えば、私は常に配列にBFSと同じ結果を取得してみましょうするときのように実際の問題です。一度は起こるかもしれませんが、毎回ではありません! 私が追加した場合、一方ゼロ
array_number_of_strokes_dfs.add(0);
私は違いを参照しています...
あなたが任意のアイデアを持っていますか?ここで
は結果である:
strokes BFS : [3, 27, 27, 26, 26, 2631, 7]
strokes DFS[3, 27, 27, 26, 26, 2631, 7]
「フロンティア」の種類は? – Ishamael
@Ishamaelこんにちは!それは国家のスタック 'Stackフロンティア=新しいスタック();'私はアルゴリズム関数内で示したループの上に少し書かれています。 –
Marine1