I have a Depth First Search exercise.
The goal of this exercise is to find a valid path from the beginning of the maze to the end.
This is my code:
public class Node
{
private int position;
private int type;
private boolean IsExit;
public Node(int position,int type,boolean IsExit)
{
this.position = position;
this.type = type;
this.IsExit = IsExit;
}
public int getPosition()
{
return position;
}
public int getType()
{
return type;
}
public boolean getIsExit()
{
return IsExit;
}
public void setIsExit(boolean b)
{
IsExit = b;
}
}
import java.util.Random;
import java.lang.System;
public class SearchAlgorithm
{
protected int gridSize;
protected int gridLength;
protected Node[][] grid;
public SearchAlgorithm(int gridSize)
{
int gridLength = (int) Math.sqrt(gridSize);
this.gridSize = gridSize;
this.gridLength = gridLength;
Node[][]arr = new Node[gridLength][gridLength];
Random r = new Random();
for(int i=0;i<gridSize;i++)
{
Node n;
if(i==0)
{
n= new Node(i,0,false);
arr[i][i] = n;
}
else if(i==gridSize-1)
{
n = new Node(i,0,true);
arr[gridLength-1][gridLength-1] = n;
}
else
{
int x = i%gridLength;
int y = i/gridLength;
n = new Node(i,r.nextInt(2),false);
arr[x][y] = n;
}
}
this.grid = arr;
}
public void print()
{
for(int i=0;i<gridLength;i++)
{
for(int j=0;j<gridLength;j++)
{
System.out.print("Position:"+grid[j][i].getPosition()+" Type:"+grid[j][i].getType()+" ");
}
System.out.println();
}
}
}
The grid is a 2 dimensional array of the class Node: It has 2 coordinates x and y. X is found by Node.position%i and Y is found by Node.position/i.
import java.lang.System;
public class DeepFirstSearch extends SearchAlgorithm {
private int[] position;
public DeepFirstSearch(int gridSize) {
super(gridSize);
position = new int[2];
position[0]=0;
position[1]=0;
}
public int calc(int[]position)
{
System.out.println(grid[position[0]][position[1]].getPosition());
if(grid[position[0]][position[1]].getType()==1)
{
System.out.println("Path been blocked!Exit status:"+1);
return 1;
}
else if(grid[position[0]][position[1]].getIsExit())
{
System.out.println("Path been found");
return 0;
}
else
{
if(position[0]<gridLength-1)
{
position[0]++;
calc(position);
}
if(position[0]>0)
{
position[0]--;
calc(position);
}
if(position[1]<gridLength-1)
{
position[1]++;
calc(position);
}
if(position[1]>0)
{
position[1]--;
calc(position);
}
}
return -1;
}
}
The int[] position stores the position of the current Node. If we hit a Node with Node.getType()==1 then the path is not valid. A Node with getIsExit()==true is the desired destination (it is only 1 in my example).
public class Main {
public static void main(String[] args) {
DeepFirstSearch sch = new DeepFirstSearch(9);
sch.print();
int[]pos = {0,0};
sch.calc(pos);
}
}
I set up the initial position to {0,0} in the main function.
The issue is that when I run the program I get this output:
Position:0 Type:0 Position:1 Type:0 Position:2 Type:1
Position:3 Type:1 Position:4 Type:1 Position:5 Type:1
Position:6 Type:0 Position:7 Type:1 Position:8 Type:0
0
1
2
Path been blocked!Exit status:1
1
2
Path been blocked!Exit status:1
1
2
Path been blocked!Exit status:1
1
2
Path been blocked!Exit status:1
1
2
...
and so it continues on until a StackOverflowException is thrown. Why does the algorithm keep on visiting the same nodes?
You have not implemented the notion of "visited". Positions that you have visited, should not be visited again. This is a basic principle in search algorithms. A node is called "visited" when you are ready to look at its neighbors. As you make a recursive call for a neighbor, that neighbor gets visited. If that neighbor is found to already have been visited, that indicates that neighbor is on the path you have already traversed, and so it should not be visited again. If you would, you would run in cycles, which is the problem you have encountered.
So you need to maintain a visited status somewhere. There are many ways to do that. One is to add a boolean field to Node.
public class Node
{
private int position;
private int type;
private boolean IsExit;
private boolean isVisited; // See also getter & setter
public Node(int position,int type,boolean IsExit)
{
this.position = position;
this.type = type;
this.IsExit = IsExit;
this.isVisited = false;
}
public int getPosition()
{
return position;
}
public int getType()
{
return type;
}
public boolean getIsExit()
{
return IsExit;
}
public void setIsExit(boolean b)
{
IsExit = b;
}
public boolean getIsVisited() {
return isVisited;
}
public void setIsVisited(boolean b) {
isVisited = b;
}
}
I would also suggest to have calc return a boolean instead of int, since that is really what you do there: either the search succeeds, or it doesn't.
Another problem is that the change you make to position just before making the recursive call, should be reverted once you are back. Otherwise the calculation for the next neighbor position will be wrong.
So for example this:
{
position[0]++;
calc(position);
}
should become:
{
position[0]++;
calc(position);
position[0]--; // Bring position back to the original
}
This is quite cumbersome. Moreover, position should not be a field; it is just a local piece of information that is passed along with each recursive call.
It will also be easier if you don't pass position as an array of two, but pass two separate ints, one for row, one for col.
Here is the updated calc method:
import java.lang.System;
class DeepFirstSearch extends SearchAlgorithm {
public DeepFirstSearch(int gridSize) {
super(gridSize);
}
public boolean calc(int row, int col)
{
// Perform all validity checks here, and test node was not yet visited
if ( row >= gridLength
|| row < 0
|| col >= gridLength
|| col < 0
|| grid[row][col].getIsVisited()
) {
return false; // Target was not found here
}
Node node = grid[row][col];
node.setIsVisited(true); // Mark as visited
System.out.println(node.getPosition());
if (node.getType() == 1)
{
System.out.println("Path been blocked!Exit status: false");
return false; // Target was not found here
}
else if(node.getIsExit())
{
System.out.println("Path been found");
return true; // Target found!
}
else
{
// Use short circuit evaluation: as soon as one of the calls
// returns true, no further calls will be made, and the return
// value will be true if and only when that happens.
return calc(row + 1, col) || calc(row - 1, col)
|| calc(row, col + 1) || calc(row, col - 1);
}
}
}
The initial call should then be:
class Main {
public static void main(String[] args) {
DeepFirstSearch sch = new DeepFirstSearch(9);
sch.print();
sch.calc(0, 0);
}
}