Fuera de la parte superior de mi cabeza, el algoritmo de fuerza bruta comienza en la esquina superior izquierda, avanza a través de columnas, luego baja una fila y otra vez, hasta que se queda sin filas. Sin embargo, encontrar la submatriz rectangular más grande de cada punto de inicio requiere un poco de trabajo:
En cada coordenada inicial, buscamos el valor 1. Si se encuentra, comenzamos a expandir para encontrar el tamaño de esta submatriz rectangular de la siguiente manera:
En un bucle, continúe hacia la derecha siempre que haya 1 adyacentes. Cuando alcances un cero, detente. Ahora tiene una matriz 1 x n , así que recuerde esa área, así como en qué columna se detuvo.
- ¿La operación Bitwise es importante en Python? Estoy aprendiendo esta parte en Codecademy y no entendí totalmente. ¿Qué es Base 2 y Base 10?
- ¿Cuáles son las principales estrategias para representar conceptos cualitativos como conceptos cuantitativos?
- ¿Cuáles son algunos de los divertidos libros de matemáticas que puede leer una persona de nivel secundario?
- ¿Un algoritmo 'clásico' de Shor esencialmente destruiría el interés en las computadoras cuánticas?
- ¿Los ingenieros de software necesitan saber matemáticas?
Ahora se expande hacia abajo una fila. Si hay un cero justo debajo de la coordenada inicial, hemos terminado con esta iteración (caer hasta el final del bucle interno a continuación). Sin embargo, si hay un 1 inmediatamente debajo del punto inicial, expanda hacia la derecha todo lo que pueda. hasta:
- Llega a la misma columna en la que se detuvo en la fila de arriba, o
- Llegaste a un cero. Si toca un cero, deje de expandirse hacia la derecha y recuerde esta columna como el nuevo punto de detención, en lugar de la columna final de la fila anterior. En otras palabras, no podemos extender la matriz secundaria tan a la derecha como la fila anterior sugirió que podríamos.
Ahora tenemos una matriz de filas de 2 x m . Si su área es mayor que la matriz 1 x n , esta es la nueva submatriz más grande. Sin embargo, si no es así, la matriz 1 x n era más grande en área, por lo que deberíamos ignorar la nueva por ahora.
Continúe expandiendo hacia abajo una fila a la vez si es posible, y luego en cada fila hacia la derecha si es posible (reduciendo las columnas hacia la izquierda hacia el inicio si es necesario, para mantener la forma rectangular) y siga buscando la submatriz más grande de esta primera coordenada inicial
Fin del bucle interno: cuando ya no pueda expandirse hacia la derecha o hacia abajo, sabrá cuál era la submatriz más grande desde ese punto de partida en particular.
Ahora repetimos todo el proceso para cada otra celda inicial en la matriz original. Mueva el punto de partida una columna hacia la derecha (o hacia abajo una fila, si está fuera de las columnas, comenzando desde la izquierda nuevamente) hasta que todas las celdas se hayan utilizado como punto de partida y la matriz secundaria más grande, utilizando cualquiera de esos puntos de partida, tenga ha sido encontrado
