2つの異なるアルゴリズムのカウンタの2つの同じ結果

Question

私は15のゲームでアルゴリズムBFS、DFS、A *（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] 

Answer 1

frontier場合addがpushに似ているので、あなたのBFSが実際にも、深さ優先探索をやっているよりも、Stackまたは類似のものです。実際に最初に挿入する場合（各反復でpopの要素がある場合）、.add(elem)の代わりに.add(0, elem)（挿入するインデックスは0になります）を呼び出して、実際には最初に挿入されます。