DFS кратчайшего пути
Продолжая свое обучение теории графов, я начал решать задачу Maze II
В лабиринте с пустыми местами (обозначенными 0) и стены (обозначены цифрой 1). Мяч может проходить через пустые места, катится вверх, вниз, влево или вправо, но не перестанет катиться, пока удар в стену. Когда мяч останавливается, он может выбрать следующий направление.
Учитывая лабиринт m x n, начальную позицию мяча и пункт назначения, где start = [startrow, startcol] и пункт назначения = [destinationrow, destinationcol], вернуть кратчайшее расстояние, на котором мяч остановится. назначение. Если мяч не может остановиться в пункте назначения, вернуть -1.
Расстояние – это количество пустых клеток, пройденных мячом от от начальной позиции (исключено) до места назначения (включено).
Чтобы намочить ноги, я написал алгоритм, основанный на DFS, чтобы проверять каждое направление для каждой ячейки и, если возможно, продолжать в глубину, чтобы найти «пути», каждый раз подсчитывая количество шагов. У меня есть глобальная переменная, которая проверяет, меньше ли текущий счет, а затем заменяет значение. Однако мой кратчайший путь не всегда правильный. Кто-нибудь может объяснить, что я делаю неправильно? Я понимаю, что BFS дает кратчайший путь, но у меня возникли проблемы с визуализацией BFS, выполненной в разных направлениях.
По сути, я меняю направление только тогда, когда натыкаюсь на стену, и каждый раз счет начинается с того счета, с которого начиналась рекурсивная функция. Например, при выполнении приведенного ниже алгоритма кратчайший путь должен быть равен 12, но мой алгоритм выдает 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);
}
}
}
Вы должны опубликовать воспроизводимый пример — это означает полный код приложения, входные данные, демонстрирующие проблему, и объяснение того, чем она отличается от ожидаемой.
См. Алгоритм Дейкстры.
Но мой код не использует Дейкстр
В общем, Дейкстра используется для решения лабиринтов. Однако в этой проблеме есть одна изюминка, которая усложняет ситуацию: «не перестанет катиться, пока не врежется в стену».
Точно! Но спасибо вам обоим за этот совет ... в целом dfs медленнее, но теоретически возможно, верно?
Я думаю, что вам придется использовать для этого A *, используя Дейкстру в качестве эвристики для выбора следующего шага.
@Spindoctor, visited[i][j] = true; - это, кажется, типичная ошибка: вы помечаете ячейку как посещенную, прежде чем выяснять, является ли текущий путь оптимальным или нет. Решение bfs доступно здесь
Спасибо. Вы предлагаете перенести чек на посещение после того, как чек прибыл в пункт назначения?
в вашем алгоритме цель массива boolean[][] visited состоит в том, чтобы предотвратить бесконечные циклы в пределах одного пути, однако, поскольку этот массив является глобальным, запись в него не позволяет вашему алгоритму учитывать другие пути - вам нужно по крайней мере установить visited[i][j] в true после цикла for, кроме того, вы нигде не обращайте внимания на направление, в котором вы увидели ячейку, так что boolean[][] visited там не очень хорошая структура, boolean[M][N][4] visited кажется более подходящей. Кстати, после исправления вы получите ошибку TLE
Помимо начального и конечного квадратов сетки, имеют значение только квадраты граничной сетки, верно (потому что в противном случае ваше направление полностью определяется тем, в каком направлении вы путешествовали с того момента, когда вы в последний раз были на граничном квадрате)? При этом необходимо только O(R + C) узлов, соответствующих граничным квадратам, где R и C — количество строк и столбцов сетки соответственно. Затем, как упоминалось ранее, для этой задачи подходит алгоритм Дейкстры, потому что ребра (соединения между узлами) взвешены (разные расстояния) и положительны.
@AndreyB.Panfilov, я не понимаю. Можете ли вы привести пример?
Большое спасибо за модификации. Теперь я понимаю, что я выполнял dfs, но это был один путь, поскольку я отметил все посещенные как истинные, но то, что вы сделали, это для каждого изменения направления, вы рассматриваете его как новый путь, и все узлы открыты для повторного посещения но из-за другого направления. Это правильная интерпретация?
"либо другой, либо более оптимальный"
спасибо за помощь в использовании моей логики и внесении изменений, я многому научился благодаря тому, что вы нашли время для этого. очень ценю это
Ответы 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);
}
}
}
}
Ваш dfs рекурсивен. Не хорошая идея. У вас закончится стек на любом графе значительного размера. Конечно, у вас не должно быть так много параметров для рекурсивной функции - у вас закончится память стека даже быстрее, чем необходимо.