最短路径深度优先搜索

huangapple
go评论74阅读模式
英文:

Shortest Path DFS

问题

继续我的图论学习，我开始解决迷宫II问题。

有一个球在一个迷宫里，迷宫由空格（表示为0）和墙壁（表示为1）组成。球可以通过向上、向下、向左或向右滚动穿过空格，但它不会停止滚动直到撞到墙。当球停下时，它可以选择下一个方向。

给定m x n迷宫，球的起始位置和目的地，其中start = [startrow, startcol]，destination = [destinationrow, destinationcol]，返回球停在目标位置的最短距离。如果球无法停在目标位置，返回-1。

距离是球从起始位置（不包括）到目的地（包括）经过的空格数量。

为了开始，我基于深度优先搜索（DFS）编写了一个算法，对每个单元格检查每个方向，并在可能的情况下以深度优先的方式继续寻找“路径”，每次保持步数的计数。我有一个全局变量来检查当前计数是否较小，然后替换该值。然而，我的最短路径并不总是正确的。有人能解释我做错了什么吗？我确实理解BFS可以产生最短路径，但我在想象不同方向上的BFS时遇到了困难。

基本上，我只有在撞到墙时才改变方向，每次计数都会从递归函数开始的计数开始。例如，运行下面的算法应该产生一个最短路径为12，但我的算法却输出16。

英文:

Continuing my education of graph theory, I started to tackle the Maze II problem

> There is a ball in a maze with empty spaces (represented as 0) and
> walls (represented as 1). The ball can go through the empty spaces by
> rolling up, down, left or right, but it won't stop rolling until
> hitting a wall. When the ball stops, it could choose the next
> direction.
>
> Given the m x n maze, the ball's start position and the destination,
> where start = [startrow, startcol] and destination = [destinationrow,
> destinationcol], return the shortest distance for the ball to stop at
> the destination. If the ball cannot stop at destination, return -1.
>
> The distance is the number of empty spaces traveled by the ball from
> the start position (excluded) to the destination (included).

To get my feet wet, I wrote an algorithm based on DFS to check each direction for each cell and continue in a depth first manner if possible to find "paths", each time keeping count of the number of steps. I have a global variable that checks if the current count is less and then replaces the value. However, my shortest path isn't always right. Can anyone explain what I am doing wrong? I do understand that BFS yields a shortest path but I have having trouble visualizing the BFS done in different directions.

Basically, I change direction only when I hit a wall and each time the count would start off with the count that the recursive function would have started with. As an example, running the algorithm below should produce a shortest path of 12 but my algorithm spits out 16

public class MazeII {
	int shortest = Integer.MAX_VALUE;
	int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) {
		int[][] maze = {{0,0,1,0,0},{0,0,0,0,0},{0,0,0,1,0},{1,1,0,1,1},{0,0,0,0,0}};
		int[] start = {0,4};
		int[] destination = {4,4};
		MazeII mii = new MazeII();
		System.out.println(mii.shortestDistance(maze, start, destination));
	}

	public int shortestDistance(int[][] maze, int[] start, int[] destination) {
		int count = 0;
		boolean[][] visited = new boolean[maze.length][maze[0].length];
		dfs(maze, start[0], start[1], destination, visited, count);
		return shortest == Integer.MAX_VALUE? -1 : shortest;
		
	}
	
	private void dfs(int[][] maze, int i, int j, int[] destination, boolean[][]visited, int count) {
		if( visited[i][j]) {
			return;
		}
		if (i == destination[0] && j == destination[1]) {
			shortest = Math.min(shortest, count);
			return;
		}
		
		visited[i][j] = true;

		for (int[] dir : dirs) {
			int x = i;
			int y  = j;
			int newcount = count;
			while (x + dir[0] >= 0 && x + dir[0] < maze.length &&
					y + dir[1] >= 0 && y + dir[1] < maze[0].length &&
					maze[x + dir[0]][y + dir[1]] == 0) {
				x+=dir[0];
				y+=dir[1];
				newcount++;
			}
			dfs(maze, x , y, destination, visited, newcount);
		}
	}

}

答案1

得分: 1

以下是我尝试解释的部分：

public class MazeII {
    int shortest = Integer.MAX_VALUE;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        int[][] maze = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}};
        int[] start = {0, 4};
        int[] destination = {4, 4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int count = 0;
        boolean[][][] visited = new boolean[maze.length][maze[0].length][4];
        dfs(maze, start[0], start[1], destination, visited, count);
        return shortest == Integer.MAX_VALUE ? -1 : shortest;
    }

    private void dfs(int[][] maze, int i, int j, int[] destination, boolean[][][] visited, int count) {
        if (i == destination[0] && j == destination[1]) {
            shortest = Math.min(shortest, count);
            return;
        }

        for (int k = 0; k < dirs.length; k++) {
            int[] dir = dirs[k];
            int x = i;
            int y = j;
            int newcount = count;
            while (x + dir[0] >= 0 && x + dir[0] < maze.length &&
                    y + dir[1] >= 0 && y + dir[1] < maze[0].length &&
                    maze[x + dir[0]][y + dir[1]] == 0) {
                x += dir[0];
                y += dir[1];
                newcount++;
            }
            if (!visited[x][y][k]) {
                visited[x][y][k] = true;
                dfs(maze, x, y, destination, visited, newcount);
                visited[x][y][k] = false;
            }
        }
    }
}

然而，为了使遍历算法更加高效，您需要消除次优路径，例如在选择特定方向时存储从单元格到目标的距离：

public class MazeII {
    int shortest = Integer.MAX_VALUE;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        int[][] maze = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}};
        int[] start = {0, 4};
        int[] destination = {4, 4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int count = 0;
        int[][][] visited = new int[maze.length][maze[0].length][4];
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                Arrays.fill(visited[i][j], Integer.MAX_VALUE);
            }
        }

        dfs(maze, start[0], start[1], destination, visited, count);
        return shortest == Integer.MAX_VALUE ? -1 : shortest;
    }

    private void dfs(int[][] maze, int i, int j, int[] destination, int[][][] visited, int count) {
        if (i == destination[0] && j == destination[1]) {
            shortest = Math.min(shortest, count);
            return;
        }

        for (int k = 0; k < dirs.length; k++) {
            int[] dir = dirs[k];
            int x = i;
            int y = j;
            int newcount = count;
            while (x + dir[0] >= 0 && x + dir[0] < maze.length &&
                    y + dir[1] >= 0 && y + dir[1] < maze[0].length &&
                    maze[x + dir[0]][y + dir[1]] == 0) {
                x += dir[0];
                y += dir[1];
                newcount++;
            }
            if (newcount < visited[x][y][k]) {
                visited[x][y][k] = newcount;
                dfs(maze, x, y, destination, visited, newcount);
            }
        }
    }
}
英文:

Below is what I was trying to explain in comments:

public class MazeII {
    int shortest = Integer.MAX_VALUE;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        int[][] maze = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}};
        int[] start = {0, 4};
        int[] destination = {4, 4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int count = 0;
        boolean[][][] visited = new boolean[maze.length][maze[0].length][4];
        dfs(maze, start[0], start[1], destination, visited, count);
        return shortest == Integer.MAX_VALUE ? -1 : shortest;

    }

    private void dfs(int[][] maze, int i, int j, int[] destination, boolean[][][] visited, int count) {
        if (i == destination[0] &amp;&amp; j == destination[1]) {
            shortest = Math.min(shortest, count);
            return;
        }

        for (int k = 0; k &lt; dirs.length; k++) {
            int[] dir = dirs[k];
            int x = i;
            int y = j;
            int newcount = count;
            while (x + dir[0] &gt;= 0 &amp;&amp; x + dir[0] &lt; maze.length &amp;&amp;
                    y + dir[1] &gt;= 0 &amp;&amp; y + dir[1] &lt; maze[0].length &amp;&amp;
                    maze[x + dir[0]][y + dir[1]] == 0) {
                x += dir[0];
                y += dir[1];
                newcount++;
            }
            if (!visited[x][y][k]) {
                visited[x][y][k] = true;
                dfs(maze, x, y, destination, visited, newcount);
                visited[x][y][k] = false;
            }
        }
    }

}

However, in order to make traversal algorithm more optimal, you need somehow eliminate sub-optimal paths, for example store distance from cell to the destination when particular direction has been chosen:

public class MazeII {
    int shortest = Integer.MAX_VALUE;
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) {
        int[][] maze = {{0, 0, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 0}};
        int[] start = {0, 4};
        int[] destination = {4, 4};
        MazeII mii = new MazeII();
        System.out.println(mii.shortestDistance(maze, start, destination));
    }

    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int count = 0;
        int[][][] visited = new int[maze.length][maze[0].length][4];
        for (int i = 0; i &lt; maze.length; i++) {
            for (int j = 0; j &lt; maze[0].length; j++) {
                Arrays.fill(visited[i][j], Integer.MAX_VALUE);
            }
        }

        dfs(maze, start[0], start[1], destination, visited, count);
        return shortest == Integer.MAX_VALUE ? -1 : shortest;

    }

    private void dfs(int[][] maze, int i, int j, int[] destination, int[][][] visited, int count) {
        if (i == destination[0] &amp;&amp; j == destination[1]) {
            shortest = Math.min(shortest, count);
            return;
        }

        for (int k = 0; k &lt; dirs.length; k++) {
            int[] dir = dirs[k];
            int x = i;
            int y = j;
            int newcount = count;
            while (x + dir[0] &gt;= 0 &amp;&amp; x + dir[0] &lt; maze.length &amp;&amp;
                    y + dir[1] &gt;= 0 &amp;&amp; y + dir[1] &lt; maze[0].length &amp;&amp;
                    maze[x + dir[0]][y + dir[1]] == 0) {
                x += dir[0];
                y += dir[1];
                newcount++;
            }
            if (newcount &lt; visited[x][y][k]) {
                visited[x][y][k] = newcount;
                dfs(maze, x, y, destination, visited, newcount);
            }
        }
    }

}

huangapple
  • 本文由 发表于 2023年5月15日 02:32:38
  • 转载请务必保留本文链接：https://go.coder-hub.com/76249093.html
  • algorithm
  • depth-first-search
  • graph-theory
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定