01 Matrix es demasiado lento cuando se resuelve utilizando DFS -- python campo con time-limit-exceeded campo con complexity campo con breadth-first-search campo con depth-first-search camp codereview Relacionados El problema

01 Matrix is too slow when solved using DFS


6
vote

problema

Español

Probé la resolución de leetcode 01 Matrix problema. Se está ejecutando demasiado lento cuando se resuelve utilizando el enfoque DFS.

Dada una matriz consta de 0 y 1, encuentre la distancia del 0 más cercano para cada celda.

La distancia entre dos células adyacentes es 1.

Ejemplo 1

  Input: [[0,0,0],  [0,1,0],  [0,0,0]]  Output: [[0,0,0],  [0,1,0],  [0,0,0]]   

NOTA:

  • El número de elementos de la matriz dada no excederá de 10,000.
  • Hay al menos uno 0 en la matriz dada.
  • Las células están adyacentes en solo cuatro direcciones: arriba, abajo, izquierda y derecha.
  class Solution(object):     def updateMatrix(self, matrix):         if not matrix or not matrix[0]:             return []         m, n = len(matrix), len(matrix[0])         op = [[-1 for _ in range(n)] for _ in range(m)]         directions = [(1,0), (-1,0), (0, 1), (0, -1)]         def dfs(i,j):             if matrix[i][j] == 0:                 return 0              if op[i][j] != -1:                 return op[i][j]              matrix[i][j] = -1             closest_zero = float('inf')             for direction in directions:                 x,y = direction[0] + i , direction[1] + j                 if 0 <= x < m and 0 <= y < n and matrix[x][y] != -1:                     closest_zero = min(dfs(x,y), closest_zero)             closest_zero += 1             matrix[i][j] = 1             return closest_zero          for i in range(m):             for j in range(n):                 if matrix[i][j] == 1 and op[i][j] == -1:                     op[i][j] = dfs(i,j)                 elif matrix[i][j] == 0:                     op[i][j] = 0         return op    

Se está ejecutando demasiado lentamente y no entiendo cuál es la razón de eso. La solución más optimizada ha resuelto esto utilizando BFS.

Original en ingles

I tried solving Leetcode 01 Matrix problem. It is running too slow when solved using DFS approach.

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.

Example 1

Input: [[0,0,0],  [0,1,0],  [0,0,0]]  Output: [[0,0,0],  [0,1,0],  [0,0,0]] 

Note:

  • The number of elements of the given matrix will not exceed 10,000.
  • There are at least one 0 in the given matrix.
  • The cells are adjacent in only four directions: up, down, left and right.
class Solution(object):     def updateMatrix(self, matrix):         if not matrix or not matrix[0]:             return []         m, n = len(matrix), len(matrix[0])         op = [[-1 for _ in range(n)] for _ in range(m)]         directions = [(1,0), (-1,0), (0, 1), (0, -1)]         def dfs(i,j):             if matrix[i][j] == 0:                 return 0              if op[i][j] != -1:                 return op[i][j]              matrix[i][j] = -1             closest_zero = float('inf')             for direction in directions:                 x,y = direction[0] + i , direction[1] + j                 if 0 <= x < m and 0 <= y < n and matrix[x][y] != -1:                     closest_zero = min(dfs(x,y), closest_zero)             closest_zero += 1             matrix[i][j] = 1             return closest_zero          for i in range(m):             for j in range(n):                 if matrix[i][j] == 1 and op[i][j] == -1:                     op[i][j] = dfs(i,j)                 elif matrix[i][j] == 0:                     op[i][j] = 0         return op  

It is running too slowly and I don't understand what is the reason for that. Most optimised solution have solved this using BFS.

              
   
   

Lista de respuestas

1
 
vote

El algoritmo es lento ya que crea caminos en las 4 direcciones en las 4 direcciones. cada paso. El algoritmo también está utilizando la recursión, que también es más lenta. que un simple $screen5 .

Considerar un 5x5 Matrix $screen6 :

  $screen7  

Para encontrar la distancia de la celda superior izquierda, el algoritmo se mueve primero Abajo, luego, entonces, entonces, y luego se fue. Marca las células que tiene Ya visitado por A -1 para evitar los bucles infinitos. Así que los primeros cinco Los pasos se moverán hacia abajo:

  $screen8  

Ahora el algoritmo no puede moverse hacia abajo, ya que ha alcanzado el Número máximo de fila, y trata de moverse en la siguiente dirección que es hacia arriba Aquí, encuentra un A -1 y se da por vencido en esa dirección desde A -1 indica que ya ha visitado esa celda. Ahora trata de Mover a la derecha en lugar:

  $screen9  

en celular foreach $screens0 (I.E. Fila inferior, segunda columna) Hace lo mismo comprueba y encuentra que no puede moverse hacia abajo, entonces intenta moverse hacia arriba y encuentra un 0 en celular foreach $screens1 . En este punto, Somos 6 niveles profundamente en la recursión y la distancia de foreach $screens2 a foreach $screens3 es, por lo tanto, se encuentra 6 por ahora. Tan idealmente, el algoritmo ahora debería rechazar cualquier camino adicional que exceda los 6 niveles de recursión. Desafortunadamente, este no es el caso; Primero los pasos del algoritmo Volver a la recursión Nivel 5 en celular foreach $screens4 y continúa con la celda foreach $screens5 :

  foreach $screens6  

De esta celda se mueve hacia arriba todo el camino hasta la célula foreach $screens7 :

  foreach $screens8  

alcanza un nivel de recursión de 11. Aquí puede moverse ya sea a la derecha o A la izquierda. Dado que el algoritmo siempre intenta justo antes de la izquierda, Se mueve a la celda foreach $screens9 y luego continúa hacia abajo a la celda $callback_args0 :

  $callback_args1  

El nivel de recursión es ahora 16. Luego se mueve hacia el derecho a la celda $callback_args2 y Luego, hacia arriba a la celda $callback_args3 .

  $callback_args4  

El nivel de recursión es ahora 21. Un cero es Finalmente se encuentra en la celda $callback_args5 que indica una distancia de 21 de la celda $callback_args6 . Aún así, el Algoritmo continúa investigando caminos inútiles (es decir: caminos con el nivel de recursión más que 6 (recuerda que ya hemos encontrado un cero en la distancia 6) y se mueve de nuevo a la celda $callback_args7 en la recursión Nivel 20. Aquí intenta las instrucciones restantes (izquierda y derecha), pero Ninguna de esas obras, por lo que se realiza el nivel 20. Luego entra de nuevo en Nivel 19, 18, 17, 16, 15:

  $callback_args8  

Observe que reemplaza al -1 con 1 a medida que completa un nivel. Y ahora $callback_args9 , $callback0 , $callback1 , $callback22 y 99887766555443343 se restablecen al valor 1. en Nivel 15, es decir, celular $callback4 , ya ha intentado moverse, así que ahora trata de subir, pero eso no funciona ya que la celular $callback5 tiene un -1. Luego trata de moverse a la derecha, a la celda $callback6 , que funciona Dado que $callback7 es ahora 1 (y no -1). De la celda $callback8 primero intenta Mueve hacia abajo y alcanza la celda $callback9 . De esa celda la única alternativa es moverse a la izquierda y en el nivel de recursión 17 alcanza la celda $metaboxes0 :

  $metaboxes1  

En esta celda no puede ingresar, hay un -1 en todas las direcciones, y se rinde en el nivel 17, (y se mueve de nuevo a nivel ...).

El procedimiento debe ser claro a estas alturas. No continuaré más lejos con este ejemplo, el punto era solo para Ilustra por qué el algoritmo es tan lento.

De hecho, para encontrar la distancia para $metaboxes2 en este 5x5 Ejemplo de matriz ¡Ejecuta un método recursivo de 22254 (!) al método recursivo $metaboxes3 . Esto simplemente para determinar que la distancia es 4 (que BTW se encuentra fácilmente Al moverse horizontalmente al cero en celular $metaboxes4 ).

Creo que es una feria supuesta que el algoritmo tiene una complejidad exponencial. Y debería llevar para siempre correr casos con más de lo que dicen 100 células (es decir, 10x10 matriz).

Finalmente, aquí hay un ejemplo de un algoritmo mucho más rápido que debería ser capaz de encontrar una solución para una matriz de 100x100 en una fracción de segundo:

  99887766 5443355  

 

The algorithm is slow since it creates paths in all 4 directions at each step. The algorithm is also using recursion, which is also slower than a simple for loop.

Consider a 5x5 matrix A:

[[1 1 1 1 0]  [1 1 1 1 1]  [1 1 1 1 1]  [1 0 1 1 1]  [1 1 1 1 1]] 

to find the distance of the top-left cell, the algorithm first moves down, then up, then right, and then left. It marks the cells it has already visited by a -1 to avoid infinite loops. So the first five steps will move down:

[[-1  1 1 1 0]  [-1  1 1 1 1]  [-1  1 1 1 1]  [-1  0 1 1 1]  [-1  1 1 1 1]] 

now the algorithm cannot move further down since it has reached the maximum row number, and it tries to move in the next direction which is upwards. Here, it encounters a -1 and gives up on that direction since a -1 indicates that it has already visited that cell. Now it tries to move to the right instead:

[[-1  1  1  1  0]  [-1  1  1  1  1]  [-1  1  1  1  1]  [-1  0  1  1  1]  [-1 -1  1  1  1]] 

In cell A(4,1) (i.e. bottom row, second column) it does the same checks and finds that it cannot move down, then it tries to move upwards and encounters a 0 in cell A(3,1). At this point, we are 6 levels deep into the recursion and the distance from A(0,0) to A(3,1) is hence found to be 6 for now. So ideally the algorithm should now reject any further paths that exceeds 6 levels of recursion. Unfortunately this is not the case; first the algorithm steps back to recursion level 5 in cell A(4,1) and continues with cell A(4,2):

[[-1  1  1  1  0]  [-1  1  1  1  1]  [-1  1  1  1  1]  [-1  0  1  1  1]  [-1 -1 -1  1  1]] 

from this cell it moves upwards all the way up to cell A(0,2):

[[-1  1 -1  1  0]  [-1  1 -1  1  1]  [-1  1 -1  1  1]  [-1  0 -1  1  1]  [-1 -1 -1  1  1]] 

reaches a recursion level of 11. Here it can move either to the right or to the left. Since the algorithm always tries right before left, it moves to cell A(0,3) and then continues downward to cell A(4,3) :

[[-1  1 -1 -1  0]  [-1  1 -1 -1  1]  [-1  1 -1 -1  1]  [-1  0 -1 -1  1]  [-1 -1 -1 -1  1]] 

The recursion level is now 16. Then it moves to right to cell A(4,4) and then upwards to cell A(0,4).

[[-1  1 -1 -1  0]  [-1  1 -1 -1 -1]  [-1  1 -1 -1 -1]  [-1  0 -1 -1 -1]  [-1 -1 -1 -1 -1]] 

The recursion level is now 21. A zero is finally found in cell A(0,4) indicating a distance of 21 from cell A(0,0). Still, the algorithm continues to investigate useless paths (that is: paths with recursion level more that 6 (remember that we have already found a zero at distance 6) and moves back to cell A(1,4) at recursion level 20. Here it tries the remaining directions (left and right) but none of those works, so level 20 is done. Then it enters back into level 19, 18, 17, 16, 15:

[[-1  1 -1 -1  0]  [-1  1 -1 -1  1]  [-1  1 -1 -1  1]  [-1  0 -1 -1  1]  [-1 -1 -1  1  1]] 

notice that it replaces the -1 with 1 as it completes a level. So now A(1,4), A(2,4), A(3,4), A(4,4), and A(4,3) are all reset to value 1. At level 15, i.e. cell A(3,3), it has already tried to move down, so now it tries to move up, but that does not work since cell A(3,2) has a -1. Then it tries to move to the right, to cell A(3,4), which works since A(3,4) is now 1 (and not -1). From cell A(3,4) it first tries to move down and reaches cell A(4,4). From that cell the only alternative is to move left and at recursion level 17 it reaches cell A(4,3):

[[-1  1 -1 -1  0]  [-1  1 -1 -1  1]  [-1  1 -1 -1  1]  [-1  0 -1 -1 -1]  [-1 -1 -1  1 -1]] 

In this cell it cannot get further, there is a -1 in all directions, and it gives up on level 17, (and moves back to level ...).

The procedure should be clear by now. I will not continue further with this example, the point was just to illustrate why the algorithm is so slow.

In fact, in order to find the distance for A(0,0) in this 5x5 matrix example it executes a whopping 22254 (!) calls to the recursive dfs() method. This simply to determine that the distance is 4 (which btw is found easily by moving horizontally to the zero in cell A(0,4)).

I think it is a fair guess that the algorithm has an exponential complexity. And it should take forever to run cases with more than say 100 cells (i.e. a 10x10 matrix).

Finally, here is an example of a much faster algorithm that should be able to find a solution for a 100x100 matrix in a fraction of a second:

import numpy as np  class Solution:     """ Solution to leetCode problem 542. 01 Matrix     Given a matrix consisting of 0 and 1, find the distance of the     nearest 0 for each cell. The distance between two adjacent cells is 1.     """     def __init__(self, A):         self.A = A      def get_dist(self):         """ Get the distance matrix for self.A as defined in the         problem statement for problem 542. 01.         """         A = self.A         (N, M) = A.shape         B = np.zeros(A.shape, dtype=int)         for i in range(N):             for j in range(M):                 if A[i,j] == 1:  # if A[i,j] == 0, B[i,j] is already set to 0                     dist = 1                     found = False                     while not found:                         for (x,y) in self.points(i, j, dist):                             if A[x,y] == 0:                                 B[i,j] = dist                                 found = True                                 break                         if not found:                             dist = dist + 1                             if dist > M+N:                                 raise Exception('Unexpected')         return B      def points(self, i, j, dist):         """ Generate all valid points a distance 'dist' away from (i,j)         The valid points will lie on the edge of a diamond centered on         (i,j). Use a generator to avoid computing unecessary points.         """         (N, M) = self.A.shape         for k in range(dist):             if (i+k < N) and (j-dist+k >= 0):                 yield (i+k, j-dist+k)             if (i+dist-k < N) and (j+k < M):                 yield (i+dist-k, j+k)             if (i-k >= 0) and (j+dist-k < M):                 yield (i-k, j+dist-k)             if (i-dist+k >= 0) and (j-k >= 0):                 yield (i-dist+k, j-k) 
 
 

Relacionados problema

7  Árboles binarios equivalentes (un recorrido por go)  ( Equivalent binary trees a tour of go ) 
Cualquier sugerencia sobre cómo mejorar el código que se muestra a continuación para la Ejercicio de go-tour ? < / p> Descripción del ejercicio: Puede ha...

6  BFS / DFS Web Crawler  ( Bfs dfs web crawler ) 
He construido un rastreador web que comienza en una URL de origen y rastrea la web con un método BFS o DFS. Todo está funcionando bien, pero la actuación es h...

12  Método de búsqueda de primera profundidad para buscar todos los "superpalindromos" cuyos factores primos son todos <= n  ( Depth first search method for searching for all superpalindromes whose prime f ) 
Se solicitó una pregunta en math.se ( aquí ) sobre si hay o no infinitamente muchosDerromas de superpalindros. Voy a reformular la definición a uno más adecua...

4  Profundidad Primera búsqueda usando Stack en Python  ( Depth first search using stack in python ) 
He implementado una primera búsqueda de profundidad usando una pila (en una clase separada). Cualquier sugerencia por favor en las mejoras para el siguiente c...

2  Implementación dirigida al gráfico en Java  ( Directed graph implementation in java ) 
Aquí he adjuntado mi implementación de Java de un gráfico dirigido. He usado un mecánico de lista de adyacencia modificada para utilizar un mapa en lugar de u...

2  Un generador de laberinto Scala en estilo funcional  ( A scala maze generator in functional style ) 
Me pregunto si hay más que puedo hacer para incorporar más principios de programación de Scala y funcionales idiomáticos. Sé que el laberinto es silencioso, p...

1  Algoritmo de Minesweeper que funciona dentro de O (1) complejidad espacial  ( Minesweeper algorithm that works within o1 space complexity ) 
Para el algoritmo de minasweeper, en lugar de la solución BFS o DFS más obvia, quiero una solución espacial O (1). En primer lugar, le explicaré cómo funcio...

9  Rango de hackers: viaje a la luna (teoría del gráfico)  ( Hacker rank journey to the moon graph theory ) 
Estoy intentando completar el problema "Viaje a la luna" Descrito a continuación: Hay n astronautas entrenados numerados de 0 a N-1. Pero aquellos en E...

5  HEURRÍSTICAS DEL PARE CERCANO, GRÁFICO CON MATRIX DE ADJUSTAJE EN C ++ 17  ( Closest pair heuristics graph with adjacency matrix in c17 ) 
Estaba tratando de resolver un problema que se mencionó brevemente al comienzo del "Manual de diseño del algoritmo" por Steven Skiena (CH 1, Problema 26). M...

8  Profundidad-Primera búsqueda en Python  ( Depth first search in python ) 
Escribí este DFS en Python y me preguntaba si es correcto. De alguna manera, parece demasiado simple para mí. Cada nodo es una clase con atributos: vis...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos