Dynamic programming process

John

I'm trying to implement a solution to this problem but I am having some problems.

The problem is:

"There is a robot in the upper left hand corner of a grid with r rows and c columns. The robot can only move right or down and certain cell's are "off limits" meaning the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right."

The solution looks like this:

public static ArrayList<Point> getPath(boolean[][] maze){
   if(maze == null || maze.length==0) return null;
      ArrayList<Point> path = new ArrayList<Point>();
      HashSet<Point> failedPoints = new HashSet<Point>();
   if(getPath(maze, maze.length-1,maze[0].length-1,path,failedPoints)){
      return path;
   }
   return null;
}

public static boolean getPath(boolean[][] maze, int row, int col, 
   ArrayList<Point> path, HashSet<Point> failedPoints){
   /*if out of bounds or not available, return*/
   if(col<0 || row<0 || !maze[row][col]){
      return false;
   }
   Point p = new Point(row,col);
   /*If we've already visited this cell return*/
   if(failedPoints.contains(p)){
      System.out.println("Worked");
      return false;
   }

   boolean isAtOrigin = (row == 0) && (col == 0);

   /*If there's a path from start to my current location, add my location.*/

   if(isAtOrigin || getPath(maze,row,col -1, path, failedPoints) || getPath(maze,row-1, col, path,failedPoints)){
      path.add(p);
      return true;
   }
   failedPoints.add(p); //Cache result
   return false;
}

What's confusing to me is the attempt at Dynamic Programming.

if(failedPoints.contains(p)) never evaluates to true.

I have overridden the equals and hashCode methods in my Point class so failedPoints.contains(object) evaluates to true whenever the object compared has the same row and col values.

Perhaps it has to do with the maze input i'm using:

    boolean[][] maze = new boolean[4][4];
    java.util.Arrays.fill(maze[0],true);
    java.util.Arrays.fill(maze[1],true);
    java.util.Arrays.fill(maze[2],true);
    java.util.Arrays.fill(maze[3],true);

    maze[0][1] = false;
    maze[3][2] = false;
    ArrayList<Point> path =  getPath(maze);

But I'm not sure. In the end I don't see how failedPoints.contains(p) is saving my computer any execution steps

Here is the point class:

public class Point {
    int row;
    int col;

    Point(int row1,int col1) {
        row = row1;
        col = col1;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Point)) return false;
        Point comp = (Point) o;
        return comp.row == row && comp.col == col;
    }

    public int hashCode() {
        return row;
    }
}
displayName

It's your maze's design.

This is your maze, according to the input you have written in the question:

E O O O

O O O O

O O X X

O O X S

You start at S and are trying to reach E, with X being off limit locations.


So, you see that with S being entirely covered with off limit points, there is no way you can reach E. And hence the very first point S is a failed point which is never re-used because the algorithm halts after the evaluation of S.

Perhaps if you would set the point in 0th row and 1st column as off limit, you will have multiple explorations that will reach this point and take advantage of caching to ascertain that this point cannot be used any further for exploring the maze.


UPDATE:

After you updated the maze, I realized that there are two issues with your implementation, not one.

Change the line,

if(isAtOrigin || getPath(maze,row,col -1, path, failedPoints) || getPath(maze,row-1, col, path,failedPoints))

to

if(isAtOrigin || getPath(maze,row-1,col, path, failedPoints) || getPath(maze,row,col-1, path,failedPoints))

and the code will actually work with the new maze.

The issue is that you are returning from the getPath() as soon as you find a path. And because you are first going to left and then going up, the point [0, 2] (which is a failed point) is not hit at all, and therefore not cached, and therefore not used either.

Changing the if condition causes your algorithm to first search up and then search left. This causes you to hit [0, 2] multiple times, resulting in it being cached as well as re-used in further path searches.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related