DFS for a maze...what is the Big O, does it go exponential?
Ok I have this DFS algorithm that I wrote for a maze (a 2-D array of what Cells, Cells extend Point, and that is what they basically are).
Here is my code. You won't be able to run it, because of all the other missing classes.
package Grid;
import java.util.*;
import java.awt.*;
import java.io.*;
publicclass TraverseMaze
{
privatestaticboolean solutionFound =false;
privatestaticboolean stackInitialized =false;
static Stack solutionStack =new Stack();
/**
*Returns the stack with the solution to the maze, where the last cell
*is at the top of the stack.
*/
publicstaticboolean getPath(Maze _mazeArray)
{
if (!stackInitialized)
{
System.err.println("Stack Initialized");
initializeStack(_mazeArray);
}
if (!solutionFound || !solutionStack.empty())
{
Cell currentCell = (Cell)solutionStack.peek();
if (currentCell.equals(_mazeArray.getEndPos()))
{
solutionFound =true;
}
else
{
if (_mazeArray.isRightActive(currentCell) && !solutionFound)
{
solutionStack.push(_mazeArray.getRightCell(currentCell));
getPath(_mazeArray);
}
if (_mazeArray.isLeftActive(currentCell) && !solutionFound)
{
solutionStack.push(_mazeArray.getLeftCell(currentCell));
getPath(_mazeArray);
}
if (_mazeArray.isUpActive(currentCell) && !solutionFound)
{
solutionStack.push(_mazeArray.getUpCell(currentCell));
getPath(_mazeArray);
}
if(_mazeArray.isDownActive(currentCell) && !solutionFound)
{
solutionStack.push(_mazeArray.getDownCell(currentCell));
getPath(_mazeArray);
}
if (!solutionFound)
{
Cell popCell = (Cell)solutionStack.pop();
popCell.setCellUnvisited();
popCell =null;
}
}
}
return solutionFound;
}
/**
*Initializes solution stack by placing the starting position at the
*top of the stack
*/
privatestaticvoid initializeStack(Maze _mazeArray)
{
if (!stackInitialized)
{
solutionStack.push(_mazeArray.getStartPos());
stackInitialized =true;
}
}
}
The code seems to run fine...however, there is this one line near the bottom that reads popCell.setCellUnvisited().
When I have that line commented out, the code seems to work fine. When I have the line in, it seems to run into some infinite loop. Either it is an infinite loop, or the other possibility I thought was that it is just exponentially more operations. But I don't know. And I can't understand why that is? So perhaps somebody can tell me. If I leave that line in there and I have a 20x15 maze, does it increase the number of operations, so exponentially large, that it is impossible to get a solution, I don't think so. So why does that line have such an effect.
Since the code you've given doesn't seem to actually <i>use</i> cell.isVisited() or whatever, it's not clear. However, I would guess it is making things exponentially worse.
I did spot one bug in your code. The line if (!solutionFound || !solutionStack.empty())
should almost certainly read if (!solutionFound && !solutionStack.empty())
Sorry my code doesn't show it here, but where I write isRightActive() or isLeftActive() that is where it checks whethere it isVisted() or not. The only reason it makes me confused whether it is exponential or not, is because even for very small mazes, maybe 10x10 or less like 7x7, even if it was exponential, I've only set the probability of a cell being open for travel 70% of the time. So only really 70 cells are open. So basically, I would think that even if it was exponential some of these smaller maze sizes would still yield a result, because it was small enough. But sure enough it doesn't.
Also your second comment about the || instead of the &&, I think you are right, though I have to think about it more. I had it as && at first, then changed it, I've thought it through, and I think I came to the conclusion that they either both have to be true, or both have to be false, just because of how the program is laid out. But I have to think about it more. Statement wise, it is probably more accurate as an && though. Though I have to say it still works either way.
> Also your second comment about the || instead of the &&, I think you are right, though I have to think about it more.
I should have explained my reasoning. If solutionStack.empty(), then the call to solutionStack.peek() in the next line will throw an exception.
Thinking about it some more, you probably have an infinite loop in addition to the exponential running cost, because if you don't check whether you've visited a square there's nothing to stop you going NSNSNSNSNSNSNSNSNS...
Problem no. 1: never in the given code is a cell actually set to visited (that's the major cause why it does not work)
Problem no. 2: while entering a "new" cell you should take a look whether you had been there before or not (already stated by the other guy - check isVisited)
Problem no. 3: while leaving a cell from which no successful way to the solution has been found why you set it to unvisited? (I think that was also mentioned)
Consider what you do:
1) you enter a room
2a) if you have not been there you mark it as visited (you can do it always, btw.)
3a) reached your aim? no -> take the first possible way out the the next new room
2b) if you have been there before (you reached a dead end), turn, and go back
2c) you have been there before but you are returning from a dead end -> take another possible way (if exist, otherwise keep on returning)
Now, if you decided to use recursion you needn't implement the stack.
static boolean throughMaze(int cell) {
if (visited[cell]) return false;
visited[cell] = true;
if (cell == aim) {
print "Solution found!";
return true; //stopping the recursion
}
if (throughMaze(cell, right)) print cell;
if (throughMaze(cell, left)) print cell;
if (throughMaze(cell, up)) print cell;
if (throughMaze(cell, down)) print cell;
if (throughMaze(cell, forth)) print cell;
if (throughMaze(cell, back)) print cell;
return false;
}//throughMaze
If you want to keep the visited values on a stack (the advantage: now are the visited rooms in the reverted order) you actually need no entry parameters like entered room, actually, no recursion (simple while can do it): it is stored on the top of the stack. You need, however, consider whether you go forward or backward (as mentioned in the narrative before)
Here I've included the Maze class, the only parts you need to look at are the isCellActive() and getCell() methods really...if you add this to the source above you will see that the isCellActive() type methods that are written here, actually check to see if the cell is visited...and then the getCell() methods do the setting to cellVisited(). So though it wasn't in the traverseMaze() class, it is in the Maze() class. I'm taking all your points into consideration, thank you. However also keep this in mind. I am not saying the code doesn't work at all. I am saying it does work when I have the line to unvisitCell() commented out, when I have that line to unvisitCells() in there, it does not work...and not only that, it still does work for mazes up to 10x10, after that point either a solution will be found which will happen in about 1 second, or when I can see on the maze, there is no solution, the program will think for about infinity (by that I mean longer than 20 seconds, at which point, I don't think it is working anymore). And even for mazes that are very very big, if the algorithm finds that there is no solution very fast it will work. E.G. in the case that my starting solution is surrounded by non-active cells, so that I can't move, either anywhere from my start position, or only to a handful of spots. So that is the weird thing, it is this one line that is making all the difference.
package Grid;
import java.awt.*;
class Maze implements ConstantsBase
{
private Cell startPos= new Cell();
private Cell endPos= new Cell();
private Cell[][] mazeArray = new Cell[GRID_ROWS][GRID_COLS];
/**
*Maze Constructor
*/
public Maze(int rows, int cols)
{
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
mazeArray[i][j] = new Cell(i,j);
}
}
}
/**
*Maze Constructor
*/
public Maze()
{
for (int i = 0; i < GRID_ROWS; i++)
{
for (int j = 0; j < GRID_COLS; j++)
{
mazeArray[i][j] = new Cell(i,j);
}
}
}
/**
* Returns the end position as a Cell.
*/
public Cell getEndPos()
{
return endPos;
}
/**
*Prints the Maze, by calling the cell print function.
*/
public void printMaze()
{
for (int i = 0; i < GRID_ROWS; i++)
{
for (int j = 0; j < GRID_COLS; j++)
{
mazeArray[i][j].printCell();
}
System.out.println();
}
}
/**
*Returns whether the Point specified by nextCell is a valid
*move on the maze.
*/
private boolean validMove(int x, int y)
{
if (x < 0 || x >= GRID_ROWS || y < 0 || y >= GRID_COLS)
{
return false;
}
else
{
Cell nextCell = mazeArray[x][y];
return ( nextCell.cellActive() && !nextCell.cellVisited() );
}
}
/**
*Initializes the position variables. The current position and the
*start position will be the same.
*/
public boolean initPositions()
{
int i = 0;
boolean startSet = false;
boolean endSet= false;
while(i < GRID_ROWS)
{
if (mazeArray[i][0].cellActive() && !startSet)
{
startPos = mazeArray[i][0];
startSet = true;
}
if (mazeArray[i][GRID_COLS - 1].cellActive() && !endSet)
{
endPos.setLocation(mazeArray[i][GRID_COLS - 1]);
endSet = true;
}
i++;
}
return (endSet && startSet);
}
/**
*Moves the current position to the right and returns true if the move is
* legitimate. Will return false otherwise.
*/
public boolean isRightActive(Cell _currentCell)
{
int x = _currentCell.x;
int y = _currentCell.y + 1;
if (this.validMove(x, y))
{
return true;
}
else
{
return false;
}
}
/**
*Moves the current position to the left and returns true if the move is
* legitimate. Will return false otherwise.
*/
public boolean isLeftActive(Cell _currentCell)
{
int x = _currentCell.x;
int y = _currentCell.y - 1;
if (this.validMove(x, y))
{
return true;
}
else
{
return false;
}
}
/**
*Moves the current position up and returns true if the move is
* legitimate. Will return false otherwise.
*/
public boolean isUpActive(Cell _currentCell)
{
int x = _currentCell.x - 1;
int y = _currentCell.y;
if (this.validMove(x, y))
{
return true;
}
else
{
return false;
}
}
/**
*Moves the current position down and returns true if the move is
* legitimate. Will return false otherwise.
*/
public boolean isDownActive(Cell _currentCell)
{
int x = _currentCell.x + 1;
int y = _currentCell.y;
if (this.validMove(x, y))
{
return true;
}
else
{
return false;
}
}
/**
*Returns the start position as a Cell.
*/
public Cell getStartPos()
{
startPos.setCellVisited();
return startPos;
}
public Cell getRightCell(Cell _currentCell)
{
int x = _currentCell.x;
int y = _currentCell.y + 1;
mazeArray[x][y].setCellVisited();
return mazeArray[x][y];
}
public Cell getLeftCell(Cell _currentCell)
{
int x = _currentCell.x;
int y = _currentCell.y - 1;
mazeArray[x][y].setCellVisited();
return mazeArray[x][y];
}
public Cell getUpCell(Cell _currentCell)
{
int x = _currentCell.x - 1;
int y = _currentCell.y;
mazeArray[x][y].setCellVisited();
return mazeArray[x][y];
}
public Cell getDownCell(Cell _currentCell)
{
int x = _currentCell.x + 1;
int y = _currentCell.y;
mazeArray[x][y].setCellVisited();
return mazeArray[x][y];
}
}
I don't want to leave you unanswered, even though there's not much new to be said.
1) OK the algorithm works because in the method getXXXCell you actually call setCellVisited. I'd do it differently, but it's your choice.
If you want to accept more little recommendations about writing good codes:
- since the array mazeArray is a private attribute of an instance of Maze it would be probably nice to have initial parameters rows, cols stored as private attributes as well
- the code in your constructors is almost the same - why not to have it in one method? (either an extra method, or call the specific one from the general one providing the default entry parameters)
2) now, to your problem with unvisitCell. I think it has already been posted by the other guy - try to imagine what it means in the real situation: your visit flag signifies that you had been to the room you just entered before (meaning: no way, turn back). If you unvisit a room when you tried all the possibilities, you actually lose a piece of information. To make it simple: imagine that your starting room is A, and from A you can get to B and C. Now from B you can only get to a maze with no end, or back to A. You will investigate it and find: B is of no use - return to A. Now from C you can get to solution and to B (this is a bit strange, because there is only one-way entrance from C to B, and not vice-versa, but for the purpose of the example, why not). Let's imagine that you will first try from C to B. Then, since B is unvisited you try to find (again) all the dead ends you could have known about. You again realize - no way, return to C and only then you find the way to the solution.
Note that the simplification does not invalidate the argument (one could easily construct an example from the real world, where the argument is valid as well).
