Même résultat pour deux tableaux de compteurs d'algorithmes différents

Question

J'essaye de construire un programme comparant le nombre de coups d'algorithmes BFS, DFS, A * (qui a deux heuristiques) sur un jeu de quinze. Mon compteur compte le même résultat pour les deux tableaux de compteurs de BFS et DFS et les deux A *. Pourtant, j'utilise actuellement quatre tableaux différents d'un main (classe Project) et j'assigne quatre variables différentes pour ces traits.

La partie du code qui n'est pas correcte est, selon moi, une boucle while qui explore autant que possible les fils d'un vertice (pour BFS) ou découvre chaque noeud suivant (pour BFS). La différence, qui est de la plus haute importance, est la dernière ligne de code qui est soit frontier.push (enfant) ;, pour DFS, soit frontier.add (enfant); pour BFS.

Chaque fois que nous entrons dans la boucle, le nombre de coups est incrémentée

number_of_strokes_DFS+=1; 

ou

number_of_strokes_BFS+=1; 

Quand nous trouvons l'état final nous ajoutons le résultat au tableau du nombre de coups :

array_number_of_strokes_dfs.add(number_of_strokes_DFS); 

ou

array_number_of_strokes_bfs.add(number_of_strokes_BFS); 

Voici enfin le code coupable (en réalité seulement DFS tant que BFS est vraiment un sosie sauf la dernière ligne).

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; 

} 

Voici le problème réel autant que quand je laisse array_number_of_strokes_dfs.add (number_of_strokes_DFS) ;, par exemple, je reçois toujours le même résultat que BFS dans le tableau. Cela peut arriver une fois, mais pas à chaque fois !!! Alors que si j'ajoute un zéro

array_number_of_strokes_dfs.add(0); 

Je vois la différence ...

Avez-vous des idées?

Voici le résultat:

strokes BFS : [3, 27, 27, 26, 26, 2631, 7] 
strokes DFS[3, 27, 27, 26, 26, 2631, 7] 

Answer 1

Si frontier est un Stack ou quelque chose de similaire, que add est analogue à push, de sorte que votre BFS est en fait aussi faire une recherche en profondeur d'abord. Si vous voulez réellement insérer au début (quelque chose que vous voulez faire si vous pop éléments à chaque itération), vous voulez appeler .add(0, elem) (notez le 0 - l'index auquel insérer) au lieu de .add(elem), de sorte qu'il est effectivement inséré au début.