Я использую DFS и BFS, чтобы решить мышь в лабиринте, где мышь может двигаться либо вправо, либо вверх. Поскольку коэффициент ветвления равен двум, а лабиринт представляет собой матрицу 5x5, я ожидал, что BFS будет намного быстрее, чем DFS, но, как оказалось, все наоборот. DFS занимает 6793300 нано секунд BFS занимает 26359600 нано секунд
Что может объяснить эту разницу? Вызывает ли дополнительная структура данных, используемая в BFS, такие издержки?
DFS:
int performMazeSearchDFS(int i, int j, int[][] maze, int destI, int destJ, int size, int moveCount)
{
int result = moveCount;
if (i == destI && j == destJ) {
return moveCount;
}
if(j+1 < size && maze[i][j+1] != 1) {
result = performMazeSearchDFS(i, j + 1, maze, destI, destJ, size, moveCount+1);
if(result > moveCount) {
return result;
}
}
if (i-1 >= 0 && maze[i-1][j] != 1) { // no improvement from previous moves
result = performMazeSearchDFS(i - 1, j, maze, destI, destJ, size, moveCount+1);
if(result > moveCount) {
return result;
}
}
moveCount = moveCount -1;
return moveCount;
}
BFS:
private class Coordinates{
private int i;
private int j;
public Coordinates(int iCord, int jCord){
i= iCord;
j=jCord;
}
public int getI(){return i;}
public int getJ(){return j;}
public boolean equals(Object toCompare){
if(toCompare instanceof Coordinates ){
Coordinates coOrdX = (Coordinates)toCompare;
if(this.i == coOrdX.getI() && this.j == coOrdX.getJ()){
return true;
}
}
return false;
}
}
private class History{
private Coordinates parent;
private Coordinates current;
public History(Coordinates par, Coordinates curr){
parent = par;
current = curr;
}
public Coordinates getParent(){return parent;}
public Coordinates getCurrent(){return current;}
}
public boolean performMazeSearchBFS(int i, int j, int[][] maze, int destI, int destJ, int size) {
LinkedList<History> nodeQ = new LinkedList<>();
HashMap<Coordinates,Boolean> visitedNode = new HashMap<>();
boolean found = false;
nodeQ.add(new History(new Coordinates(-1,-1),(new Coordinates(i,j))));
while(!nodeQ.isEmpty()) {
History currNode = nodeQ.poll();
visitedNode.put(new Coordinates(currNode.getCurrent().getI(),
currNode.getCurrent().getJ()),true);
int m = currNode.current.getI();
int n = currNode.current.getJ();
if(currNode.current.getI() == destI && currNode.current.getJ() == destJ) {
found = true;
break;
}
if (m - 1 >= 0 && maze[m - 1][n] == 0
&& !visitedNode.containsKey(new Coordinates(m - 1, n))) {
if (m - 1 >= 0 && maze[m - 1][n] == 0 ) {
nodeQ.add(new History(new Coordinates(m, n), new Coordinates(m - 1, n)));
}
if (n + 1 < size && maze[m][n] == 0
&& !visitedNode.containsKey(new Coordinates(m, n + 1))) {
nodeQ.add(new History(new Coordinates(m, n), new Coordinates(m, n + 1)));
}
}
return found;
}