algorithm - español - qgis girona

Encontrar la matriz secundaria de tamaño máximo de todos los 1 en una matriz con 1 y 0

Question

Supongamos que le dan un mapa de bits mXn, representado por una matriz M [1..m, 1 .. n] cuyas entradas son todas 0 o 1. Un bloque todo en uno es un subarreglo de la forma M [i .. i0, j .. j0] en el que cada bit es igual a 1. Describa y analice un algoritmo eficiente para encontrar un bloque todo en M con área máxima

Estoy tratando de hacer una solución de programación dinámica. Pero mi algoritmo recursivo se ejecuta en tiempo O (n ^ n), e incluso después de la memorización no puedo pensar en ponerlo por debajo de O (n ^ 4). ¿Puede alguien ayudarme a encontrar una solución más eficiente?

Answer 1

Aquí hay un O(numCols*numLines^2) . Sea S[i][j] = sum of the first i elements of column j.

Trabajaré el algoritmo en este ejemplo:

M
1 1 0 0 1 0
0 1 1 1 0 1
1 1 1 1 0 0
0 0 1 1 0 0 

Tenemos:

S
1 1 0 0 1 0
1 2 1 1 1 1
2 3 2 2 1 1 
2 3 3 3 1 1

Ahora considere el problema de encontrar la subarregla máxima de todas las unidades en una matriz unidimensional. Esto se puede resolver usando este algoritmo simple:

append 0 to the end of your array
max = 0, temp = 0
for i = 1 to array.size do
  if array[i] = 1 then
    ++temp
  else
    if temp > max then
      max = temp
    temp = 0

Por ejemplo, si tienes esta matriz 1d:

1 2 3 4 5 6
1 1 0 1 1 1

harías esto

Primero agrega un 0 :

1 2 3 4 5 6 7
1 1 0 1 1 1 0

Ahora, observe que cada vez que alcanza un 0 , sabe dónde termina una secuencia de contiguos. Por lo tanto, si mantiene un total temp (variable temp ) del número actual de unidades, puede comparar ese total con el máximo hasta el momento (variable max ) cuando llega a cero, y luego restablecer el total acumulado. Esto le dará la longitud máxima de una secuencia contigua de unos en la variable max .

Ahora puede usar este subalgoritmo para encontrar la solución a su problema. En primer lugar, agregue una columna 0 a su matriz. Entonces calcula S

Entonces:

max = 0
for i = 1 to M.numLines do
  for j = i to M.numLines do
    temp = 0
    for k = 1 to M.numCols do
      if S[j][k] - S[i-1][k] = j - i + 1 then
        temp += j - i + 1
      else
        if temp > max then
          max = temp
        temp = 0

Básicamente, para cada altura posible de un subarreglo (hay O(numLines^2) alturas posibles), encuentra el que tiene el área máxima que tiene esa altura aplicando el algoritmo para la matriz unidimensional (en O(numCols) ).

Considere la siguiente "imagen":

   M
   1 1 0 0 1 0 0
i  0 1 1 1 0 1 0
j  1 1 1 1 0 0 0
   0 0 1 1 0 0 0

Esto significa que tenemos la altura j - i + 1 fija. Ahora, tome todos los elementos de la matriz que están entre i y j inclusive:

0 1 1 1 0 1 0
1 1 1 1 0 0 0

Observe que esto se parece al problema unidimensional. Sumemos las columnas y veamos lo que obtenemos:

1 2 2 2 0 1 0

Ahora, el problema se reduce al caso unidimensional, con la excepción de que debemos encontrar una subsecuencia de valores j - i + 1 contiguos (que son 2 en este caso). Esto significa que cada columna en nuestra "ventana" j - i + 1 debe estar llena de unas. Podemos verificar esto de manera eficiente utilizando la matriz S

Para comprender cómo funciona S , considere un caso unidimensional nuevamente: sea s[i] = sum of the first i elements of the vector a . Entonces, ¿cuál es la suma de la subsecuencia a[i..j] ? Es la suma de todos los elementos hasta e incluyendo a[j] , menos la suma de todos los elementos hasta e incluyendo a[i-1] , lo que significa s[j] - s[i-1] . El caso 2d funciona de la misma manera, excepto que tenemos una s para cada columna.

Espero que esto quede claro, si tiene más preguntas por favor pregunte.

No sé si esto se ajusta a sus necesidades, pero creo que también hay un algoritmo O(numLines*numCols) , basado en la programación dinámica. Todavía no puedo entenderlo, excepto en el caso de que el subarreglo que está buscando es cuadrado. Sin embargo, alguien podría tener una mejor perspectiva, así que espera un poco más.

Answer 2

Aquí hay una implementación O (N) en C #.

La idea es utilizar una programación dinámica para construir una matriz acumulada que tenga el tamaño de la submatriz más grande, incluida la celda actual.

    public static int LargestSquareMatrixOfOne(int[,] original_mat)
    {
        int[,] AccumulatedMatrix = new int[original_mat.GetLength(0), original_mat.GetLength(1)];
        AccumulatedMatrix[0, 0] = original_mat[0, 0];
        int biggestSize = 1;
        for (int i = 0; i < original_mat.GetLength(0); i++)
        {
            for (int j = 0; j < original_mat.GetLength(1); j++)
            {
                if (i > 0 && j > 0)
                {
                    if (original_mat[i, j] == 1)
                    {
                        AccumulatedMatrix[i, j] = Math.Min(AccumulatedMatrix[i - 1, j - 1], (Math.Min(AccumulatedMatrix[i - 1, j], AccumulatedMatrix[i, j - 1]))) + 1;
                        if (AccumulatedMatrix[i, j] > biggestSize)
                        {
                            biggestSize = AccumulatedMatrix[i, j];
                        }
                    }
                    else
                    {
                        AccumulatedMatrix[i, j] = 0;
                    }
                }
                else if ( (i > 0 && j == 0) || (j > 0 && i == 0))
                {
                    if (original_mat[i, j] == 1) { AccumulatedMatrix[i, j] = 1; }
                    else { AccumulatedMatrix[i, j] = 0; }
                }
            }
        }
        return biggestSize;
    }

Answer 3

Defina una nueva matriz A que almacenará en A [i, j] dos valores: el ancho y la altura de la submatriz más grande con la esquina superior izquierda en i, j, rellene esta matriz comenzando desde la esquina inferior derecha, por filas abajo hasta arriba. Encontrará cuatro casos: realice estos casos cuando se le dé una matriz en [i, j] = 1

caso 1: ninguno de los elementos vecinos derechos o inferiores de la matriz original es igual al actual, es decir: M [i, j]! = M [i + 1, j] y M [i, j]! = M [i, j + 1] siendo M la matriz original, en este caso, el valor de A [i, j] es 1x1

caso 2: el elemento vecino a la derecha es igual al actual pero el de abajo es diferente, el valor de A [i, j] .width es A [i + 1, j] .width + 1 y A [i , j] .height = 1

caso 3: el elemento vecino al fondo es igual pero el derecho es diferente, A [i, j] .width = 1, A [i, j] .height = A [i, j + 1] .height + 1

caso 4: ambos vecinos son iguales: se consideran tres rectángulos:

1. A [i, j] .width = A [i, j + 1] .width + 1; A [i, j]. Height = 1;

2. A [i, j]. Altura = A [i + 1, j]. Altura + 1; a [i, j] .width = 1;

3. A [i, j] .width = min (A [i + 1, j] .width + 1, A [i, j + 1] .width) y A [i, j] .height = min (A [i , j + 1] + 1, A [i + 1, j])

Se considerará que el que tiene el área máxima en los tres casos anteriores representa el rectángulo en esta posición.

El tamaño de la matriz más grande que tiene la esquina superior izquierda en i, j es A [i, j] .width * A [i, j] .height para que pueda actualizar el valor máximo encontrado mientras calcula el A [i, j ]

Los elementos de la fila inferior y de la columna de la derecha se tratan como si sus vecinos al fondo y a la derecha, respectivamente, fueran diferentes.

Answer 4

Una solución O (N) (número de elementos):

A
1 1 0 0 1 0
0 1 1 1 1 1
1 1 1 1 1 0
0 0 1 1 0 0 

Genere una matriz C donde cada elemento represente el número de 1s de arriba e incluyéndolo, hasta el primer 0.

C
1 1 0 0 1 0
0 2 1 1 2 1
1 3 2 2 3 0
0 0 3 3 0 0 

Queremos encontrar la fila R , y los índices izquierdo, derecho l , r que maximizan (r-l+1)*min(C[R][l..r]) . Aquí hay un algoritmo para inspeccionar cada fila en tiempo O (cols):

Mantenga una pila de pares (h, i) , donde C[R][i-1] < h ≤ C[R][i] . En cualquier posición cur, deberíamos tener h=min(C[R][i..cur]) para todos los pares (h, i) en la pila.

Para cada elemento:

• Si h_cur>h_top
• • Empuje (h, i) .
• Más:
• • Mientras h_cur<h_top :
• • • Pop de la parte superior de la pila.
• • • Compruebe si sería una mejor (i_cur-i_pop)*h_pop > best , es decir, (i_cur-i_pop)*h_pop > best .
• • Si h_cur>h_top
• • • Empuje (h, i_lastpopped) .

Un ejemplo de esto en ejecución para la tercera fila en nuestro ejemplo:

  i =0      1      2      3      4      5
C[i]=1      3      2      2      3      0
                                 (3, 4)
 S=         (3, 1) (2, 1) (2, 1) (2, 1)
     (1, 0) (1, 0) (1, 0) (1, 0) (1, 0)    
     (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) (0,-1) 

i=0, C[i]=1 ) Empuje (1, 0) .
i=1, C[i]=3 ) Empuje (3, 1) .
i=2, C[i]=2 ) Pop (3, 1) . Compruebe si (2-1)*3=3 es un nuevo mejor.
La última vez que estallé fue 1, así que empuja (2, 1) .
i=3, C[i]=2 ) h_cur=h_top así que no haga nada.
i=4, C[i]=3 ) Empuje (3, 4) .
i=5, C[i]=0 ) Pop (3, 4) . Compruebe si (5-4)*3=3 es un nuevo mejor.
Pop (2, 1) . Compruebe si (5-1)*2=8 es un nuevo mejor.
Pop (1, 0) . Compruebe si (5-0)*1=5 es un nuevo mejor.
Fin. (De acuerdo, probablemente deberíamos agregar un término adicional C [cols] = 0 al final para una buena medida).