Jaurès Ulm - 1 year ago 50

Java Question

I'm trying to build up a program comparing number of strokes of algorithms BFS, DFS, A* (which has two heuristics) on a game of fifteen.

My counter count the same result for the two arrays of counters of BFS and DFS and both A*. Yet, I'm using actually using four different arrays from a main (class Project) and I'm assigning four different variables for those strokes.

The part of the code that isn't right is, to my mind, a while loop which explores the son of a vertice as far as possible (for BFS) or discovering each following nodes (for BFS). The difference, which is of the utmost importance, is the last line of code which is either frontier.push(child);, for DFS, or frontier.add(child); for BFS.

Each time we enter the loop, the number of strokes is incremented

`number_of_strokes_DFS+=1;`

or

`number_of_strokes_BFS+=1;`

When we find the final state we add the result to the array of the number of strokes:

`array_number_of_strokes_dfs.add(number_of_strokes_DFS);`

or

`array_number_of_strokes_bfs.add(number_of_strokes_BFS);`

Here is the guilty code finally (actually only DFS as far as BFS is really a lookalike except the last line).

`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;

}

Here is the actual problem as far as when I let array_number_of_strokes_dfs.add(number_of_strokes_DFS);, for instance, I always get the same result as BFS in the array. It might happen once, but not every time!!!

Whereas if I add a zero

`array_number_of_strokes_dfs.add(0);`

I do see the difference...

Do you have any ideas?

Here are the result:

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

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

Answer Source

If `frontier`

is a `Stack`

or something similar, than `add`

is analogous to `push`

, so your `BFS`

is in fact also doing a depth-first search. If you actually want to insert at the beginning (something you want to do if you `pop`

elements on each iteration), you want to call `.add(0, elem)`

(note the `0`

-- the index at which to insert) instead of `.add(elem)`

, so that it is actually inserted at the beginning.