动态规划过程

Question

我正在尝试实施这个问题的解决方案，但我遇到了一些问题。

问题是：

“在r行和c列的网格的左上角有一个机器人。机器人只能向右或向下移动，某些单元格是“禁止”的，这意味着机器人不能踩它们。设计一个算法来为机器人找到从左上角到右下的路径。”

解决方案如下所示：

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

让我困惑的是动态编程的尝试。

if（failedPoints.contains（p））从不计算为true。

我已经覆盖了Point类中的equals和hashCode方法，所以失败了。只要所比较的对象具有相同的行和列值，contains（对象）就会计算为true。

也许这与我使用的迷宫输入有关：

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

但我不确定。最后，我看不出是如何失败的。包含（p）正在保存我的计算机的任何执行步骤

这是点类：

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

Answer 1

这是你迷宫的设计。

这是你的迷宫，根据你在问题中的输入：

E O O O

O O O O

O O X X

O O X S

你从S开始，试图到达E，而X是超限位置。

所以，你可以看到，随着S被完全覆盖了超限点，你不可能到达E。因此，第一个点S是一个失败点，它永远不会被重复使用，因为算法在计算S后停止。

如果您将0^th行和1^st列中的点设置为off-limit，您将有多个探索到达该点，并利用缓存来确定该点不能进一步用于探索迷宫。

更新：

在你更新了迷宫之后，我意识到你的实现有两个问题，而不是一个。

换线，

if（isAtOrigin | | getPath（迷宫，行，列-1，路径，失败点）| | getPath（迷宫，行-1，列，路径，失败点））

到

if（isAtOrigin||getPath（迷宫， row-1， coll， path，失败点）||getPath（迷宫， row， col-1， path，失败点））

这段代码将实际用于新的迷宫。

问题是您一找到路径就从getPath（）返回。因为您首先向左然后向上，所以点[0,2]（这是一个失败的点）根本没有命中，因此没有缓存，因此也没有使用。

更改if条件会导致算法先向上搜索，然后向左搜索。这会导致您多次点击[0,2]，导致它被缓存，并在进一步的路径搜索中重复使用。