为什么 BFS 在这种情况下不保证最小成本路径?
Why doesn't a BFS guarantee a minimal cost path in this case?
我正在解决 LeetCode 上的一道题:
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1 (important point).
If input:
[[0,0,0],
[0,1,0],
[1,1,1]]
then output:
[[0,0,0],
[0,1,0],
[1,2,1]]
我写的代码将所有0
s的位置添加到队列中,并从队列中的每个这样的位置执行BFS。不幸的是它超时了。
给出的高度赞成的解决方案是这样的:
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
queue.offer(new int[] {i, j});
}
else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int r = cell[0] + d[0];
int c = cell[1] + d[1];
if (r < 0 || r >= m || c < 0 || c >= n ||
matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
queue.add(new int[] {r, c});
matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
}
}
return matrix;
}
}
虽然我或多或少地了解它是如何工作的,但我有以下问题:
为什么我们必须检查 matrix[r][c] <= matrix[cell[0]][cell[1]] + 1
- BFS 不保证 如果边成本相等,那么它找到的到特定节点的路径是最短的?那为什么还要检查呢?
不保证 matrix[r][c]
只会被 BFS 算法达到一次。事实上,在这个问题中,它 将 达到多次。您所说的保证 仅在 首次达到 matrix[r][c]
时有效。
因此,另一种解决方案是保留另一个 Boolean
值矩阵,标记每个单元格是否已被访问,并将您提到的检查替换为 !visited[r][c]
。然而,保留额外的矩阵需要额外的内存 - 这就是更喜欢当前方法的原因。
执行此检查是为了确保我们不会继续处理无法提供更好结果的路径。
您的 BFS 解决方案很好,但效率不够高。通过提早中止,您可以确保不会执行无用的操作,因此不会超时。
问题也可以在Nlog(N)中轻松解决,其中N是矩阵中的单元格总数,使用Dijkstra算法。
您需要做的唯一更改是,您将将全 0 视为目的地,而不是一个目的地。
所以所有0的初始距离都为零。然后你可以简单地继续使用 Dijkstra。
更新: 你发布的解决方案更好,因为它的时间复杂度是 O(N).
我正在解决 LeetCode 上的一道题:
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1 (important point).
If input:
[[0,0,0],
[0,1,0],
[1,1,1]]
then output:
[[0,0,0],
[0,1,0],
[1,2,1]]
我写的代码将所有0
s的位置添加到队列中,并从队列中的每个这样的位置执行BFS。不幸的是它超时了。
给出的高度赞成的解决方案是这样的:
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
queue.offer(new int[] {i, j});
}
else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int r = cell[0] + d[0];
int c = cell[1] + d[1];
if (r < 0 || r >= m || c < 0 || c >= n ||
matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
queue.add(new int[] {r, c});
matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
}
}
return matrix;
}
}
虽然我或多或少地了解它是如何工作的,但我有以下问题:
为什么我们必须检查 matrix[r][c] <= matrix[cell[0]][cell[1]] + 1
- BFS 不保证 如果边成本相等,那么它找到的到特定节点的路径是最短的?那为什么还要检查呢?
不保证 matrix[r][c]
只会被 BFS 算法达到一次。事实上,在这个问题中,它 将 达到多次。您所说的保证 仅在 首次达到 matrix[r][c]
时有效。
因此,另一种解决方案是保留另一个 Boolean
值矩阵,标记每个单元格是否已被访问,并将您提到的检查替换为 !visited[r][c]
。然而,保留额外的矩阵需要额外的内存 - 这就是更喜欢当前方法的原因。
执行此检查是为了确保我们不会继续处理无法提供更好结果的路径。
您的 BFS 解决方案很好,但效率不够高。通过提早中止,您可以确保不会执行无用的操作,因此不会超时。
问题也可以在Nlog(N)中轻松解决,其中N是矩阵中的单元格总数,使用Dijkstra算法。
您需要做的唯一更改是,您将将全 0 视为目的地,而不是一个目的地。
所以所有0的初始距离都为零。然后你可以简单地继续使用 Dijkstra。
更新: 你发布的解决方案更好,因为它的时间复杂度是 O(N).