Discussion :

[AntoineCompagnie]

Je suis en train de mettre en place un programme comparant les nombres de coup de BFS, DFS, A* avec deux heuristiques pour résoudre le jeu du taquin.

J'ai un problème stupide... Mon programme compte le même nombre de coups pour BFS et DFS ensemble d'une part et les deux A* d'autre part...

Pourtant, j'affiche à chaque fois quatre tableaux bien différents à partir du main dans une classe Project et j'affecte des valeurs différentes à partir d'une classe Problem

La partie du code qui fait défaut est celle qui suit chez DFS (mais est équivalente à celle de BFS sauf la fin ou j'ai utilisé un frontier.add(child); pour mettre les fils en bas de la liste), je pense.

En gros c'est une boucle while qui va explorer les fils d'un père aussi loin que possible dans la généalogie avant de revenir.
A chaque tour les fils sont ajoutés en haut de la frontière grâce à frontier.push(child);
A chaque tour le compteur du nombre de coup est incrémenté.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
    	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;
 
    }

En effet, quand je laisse array_number_of_strokes_dfs.add(number_of_strokes_DFS); j'obtiens dans le fichier resultats_strokes créé dans le main deux mêmes résultats pour les tableaux de nombres de coups pour DFS et le nombre de coup pour BFS. Ceci peut arriver une fois mais ce n'est pas vraisemblable pour tous les cas quand même!
Alors que si je le change en

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
array_number_of_strokes_dfs.add(0);

J'obtiens une liste de zéro.
J'imagine que ce doit être la même chose pour les A*.

C'est une approche chirurgicale très "vétérinaire", de cause à effet, mais je pense être sur la bonne voie.

Auriez vous une idée?

J'ai mis mon projet en pièce jointe. Il se compose de trois classes dont les deux mentionnées ci dessus sont vraiment importantes, une interface et un truc marqué "E"

[joel.drigo]

Salut,

Ton problème est que les deux méthodes, BFS et DFS, font exactement la même chose avec les mêmes données. Donc ce n'est pas étonnant d'obtenir le même résultat. Tu penses avoir un code différent à cause de l'utilisation de push() dans un cas et de add() dans l'autre, mais si tu regardes le code de push() et de add() de Stack, l'un appelle addElement() et l'autre add(), respectivement, de Vector, et le code de ces deux méthodes est le même.

Utilise plutôt un Deque pour ta pile (un ArrayDeque, ou une LinkedList) : le push() fait un addFirst() et le add() fait un addLast(), ce qui correspond mieux à ton besoin. D'ailleurs, tu peux appeler plutôt directement ces méthodes, afin que le code soit plus explicite. Tu pourras par ailleurs analyser l'impact sur les performances d'utiliser une LinkedList ou un ArrayDeque.

Enfin, je dis ça, vu l'usine à gaz que c'est, ce ne sera pas suffisant. Déjà, au lieu de duppliquer du code identique (sauf les entrées et les sorties), une méthode réduirait nettement le code, et simplifierait sa compréhension. Et puis, un peu d'objet ne ferait pas de mal (pour les DFS, BFS et autre A*).