La elección consecutiva de las células y en la matriz

Question

Una matriz es dado con $a$ filas y $b$ columnas. Algunas células están marcados. Podemos elegir algunas células con las siguientes condiciones:

• En cada fila, todos elegidos células son consecutivos.

• No hay dos células se encuentran en la misma columna.

Nuestra puntuación es entonces el menor número de células marcadas elegido en una fila, donde el mínimo es de entre todas las filas. Dado un array, lo que son rápidos algoritmos para el cálculo de la puntuación máxima posible de esa matriz?

Búsqueda por fuerza bruta toma una enorme cantidad de tiempo aquí, ya que hemos de probar todas las posibles filas para que se inicie desde la columna de la izquierda, todo lo posible el número de columnas a elegir las celdas de esa fila, y así sucesivamente. Podemos hacer algo mejor que esto?

Answer 1

Sí que lo podemos hacer mejor, pero no estoy seguro de cómo mucho mejor.

Pensando en voz alta aquí... vamos a empezar con algunas obvias observaciones:

1. En primer lugar, es bastante claro que se puede hacer sin vaciar columnas. Estos se pueden eliminar, ya que no afectan a la solución de cualquier manera: el supuesto es que cada colmn tiene al menos una célula marcada.

2. Si su puntuación es de a $S$, entonces no hay necesidad de seleccionar más de $S$ células marcadas por fila, si queremos llegar a que se une. Así que el problema es acerca de la posibilidad de seleccionar exactamente $S$ células marcadas en cada fila.

3. La selección tiene que ser contiguos como se requiere, por lo que puede que tenga que seleccionar no marcada de las células en general, pero no hay ninguna razón para seleccionar las celdas vacías en los bordes de una selección: i.e el inicio y final de las celdas seleccionadas de una fila determinada tiene que estar marcada. Todos en todos, Dada una puntuación de destino de $S$ podemos restringir la atención a selecciones consecutivas en una fila determinada, que contienen exactamente $S$ células marcadas y que inicio y de finalización de las celdas seleccionadas se marcan. Llamar a estos óptimo válido selecciones para $S$ (puede haber muchas).

4. En esta etapa, el problema se reduce a la ordenación de las filas:

   • El score no varían cuando el volteo de las filas.
   • Dada una óptima selección válida para $S$, llame a $F_{i}$ el índice de columna de la primera (y por lo tanto necesariamente marcado!) celda de la fila $i$ $L_{i}$ que el de la última celda seleccionada.
   • Asigna un puntaje $S$, se puede asociar una única fila de pedidos para cada una óptima selección válida como $rank(R_{i}) < rank(R_{j}) \Leftrightarrow \space F_{i} < F_{j}$.
   • Además si $rank(R_{i}) = rank(R_{j}) + 1$ $F_{i}$ es igual al índice de columna de la primera célula marcada después de la columna de $L_{j}$.

Todo esto es bastante obvio, pero va a demostrar que hay un uno-a-uno entre un orden de las filas y la asociada a la Óptima Selección Válida (VO) y que la selección se obtiene (dado un orden) en el tiempo lineal.

Umbral, hay $b!$ posible compra por lo que la complejidad es aún exponencial (en ~$b!$.#Las Puntuaciones posibles), PERO:

• Una cota superior para la puntuación es $Min(\left \lfloor \frac{a}{b} \right \rfloor, Min_{1 \leq i \leq b}(M_{i}))$ donde $M_{i}$ es el número de células marcadas en la fila $i$.
• Para cada fila $i$ y para cada puntuación $S$ calcular el índice de $I_{i}$ de la $(M_{i} - S)^{th}$ de células marcadas. Cuando la comprobación de si un pedido se produce un VO, dada una fila $R_{i}$, debemos tener $L_{i} + 1 \leq Min(I_{j} : Rank(R_{j}) > Rank(R_{i}))$. Esta es una condición de parada que pueden reducir el cálculo de forma considerable aunque yo claramente no creo que sea el polinomio (no dar a esta pensado mucho).